Алгоритмы 1 2015 — различия между версиями
Материал из SEWiki
м |
Burunduk (обсуждение | вклад) (→Домашние задания) |
||
(не показана 51 промежуточная версия 3 участников) | |||
Строка 11: | Строка 11: | ||
[[algo_2015_1_groups | Деление на группы]] | [[algo_2015_1_groups | Деление на группы]] | ||
− | [https://docs.google.com/spreadsheets/d/ | + | [https://docs.google.com/spreadsheets/d/1AyGBZTQ4_Ztyt3fXd-KK9MTFJS8cppxVrKQ95Nl86vY/edit#gid=0 Результаты практики] |
Дедлайны: | Дедлайны: | ||
Строка 17: | Строка 17: | ||
* практика, сдача контест: 8 дней (дедлайн в понедельник в 23:59) | * практика, сдача контест: 8 дней (дедлайн в понедельник в 23:59) | ||
− | * теория в tex: 6 дней (дедлайн в субботу в 23: | + | * теория в tex: 6 дней (дедлайн в субботу в 23:59) |
== Лекции == | == Лекции == | ||
− | + | [http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/conspect.pdf Студенческий конспект] | |
− | * | + | [http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/ TeX исходники конспекта] |
+ | |||
+ | [http://acm.math.spbu.ru/~sk1/mm/au-lections/ Планы лекций] | ||
+ | |||
+ | * 04.09 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-09-04-Intro.pdf Введение. Разбор теста.] | ||
+ | |||
+ | * 07.09 (пн) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-09-07-Asymptoic.pdf Асимптотика, реккурентности.] | ||
+ | |||
+ | * 11.09 (пт) (скорость работы программ, структуры данных: массив, список, стек/очередь/дек, динамический массив, амортизация) | ||
+ | |||
+ | * 14.09 (пн) (структуры данных: очередь с минимумом) | ||
+ | |||
+ | * 18.09 (пт) (структуры данных: два указателя, бинпоиск, хеш-таблица) | ||
+ | |||
+ | * 21.09 (пн) (структуры данных: избавлении от амортизации, кучи, аллокаторы) | ||
+ | |||
+ | * 25.09 (пт) (структуры данных: пополняемые структуры данных, разбор выражений) | ||
+ | |||
+ | * 28.09 (пн) (Сортировки: квадратичные сортировки, QuickSort, порядковые статистики) | ||
+ | |||
+ | * 10.02 (пт) (Сортировки: порядковые статистики, MergeSort, CountSort, DigitalSort, BucketSort) | ||
+ | |||
+ | * 10.05 (пн) (Сортировки: BucketSort, Kirckpatrick Sort, inplace merge) | ||
+ | |||
+ | * 10.09 (пт) (Кучи: minmax, leftist, skew, pairing, V.E.B) | ||
+ | |||
+ | * 10.12 (пн) (Кучи: биномиальная, bootstrapping, фибоначчиева, lower bound on heap-build) | ||
+ | |||
+ | * 10.16 (пт) (Динамика: база) | ||
+ | |||
+ | * 10.19 (пн) (Динамика: квадратная, подотрезки, измельчение перехода, выбор состояния) | ||
+ | |||
+ | * 10.23 (пт) (Динамика: деревья. Кучи: концовка) | ||
+ | |||
+ | * 10.26 (пн) (Динамика: подмножества, профиль, два указателя) | ||
+ | |||
+ | * 10.30 (пт) (Динамика: подмножества, профиль, два указателя) | ||
+ | |||
+ | * 11.09 (пн) (dfs: база, двудольность, циклы) | ||
+ | |||
+ | * 11.13 (пт) (dfs: topsort, ксс, эйлеровость) | ||
+ | |||
+ | * 11.16 (пн) (dfs: 2-связность, 2-SAT, цикл де брюина) | ||
+ | |||
+ | * 11.20 (пт) (кратчайшие пути: bfs, dijkstra, $A^{*}$) | ||
+ | |||
+ | * 11.23 (пн) (кратчайшие пути: fb, floyd) | ||
+ | |||
+ | * 11.27 (пт) (Карп, Гольдберг) [http://webcourse.cs.technion.ac.il/236359/Spring2013/ho/WCFiles/MMC.ps Карп] | ||
+ | |||
+ | * 11.30 (пн) (Radix Heap, алгоритм Йена) [https://en.wikipedia.org/wiki/Yen%27s_algorithm Йен], [http://acm.math.spbu.ru/~sk1/download/books/ds/heaps/ahuja-heap.pdf Two Level Radix Heap] | ||
+ | |||
+ | * 12.04 (пт) (DSU: списки, деревья, док-во log(log*)) | ||
+ | |||
+ | * 12.07 (пн) (MST: Краскал, Прим, Борувка; функция Аккермана и СНМ) [http://acm.math.spbu.ru/~sk1/download/books/DSU-Cormen.pdf DSU из Кормена] | ||
+ | |||
+ | * 12.11 (пт) (Хаффман и жадность) | ||
+ | |||
+ | * 12.14 (пн) (Приближённые алгоритмы) | ||
== Домашние задания == | == Домашние задания == | ||
− | [http://acm.math.spbu.ru/~sk1/algo/input-output/ | + | [http://acm.math.spbu.ru/~sk1/examples/tex/ Примеры работы с TeX] |
+ | |||
+ | [http://acm.math.spbu.ru/~sk1/algo/input-output/cpp_common.html Быстрое считывание в c++] | ||
[http://acm.math.spbu.ru/~sk1/algo/memory.cpp.html Быстрая аллокация памяти в c++] | [http://acm.math.spbu.ru/~sk1/algo/memory.cpp.html Быстрая аллокация памяти в c++] | ||
− | [http://acm.math.spbu.ru/~sk1/mm/au-download Все решения | + | [http://acm.math.spbu.ru/~sk1/mm/au-download Все решения всех закончившихся контестов] |
* '''01 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150901_au.dat результаты] [http://acm.math.spbu.ru/trains/150901_au.pdf условия]. | * '''01 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150901_au.dat результаты] [http://acm.math.spbu.ru/trains/150901_au.pdf условия]. | ||
− | * '''07 сентября''' Контест: | + | * '''07 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150907_au.dat результаты] [http://acm.math.spbu.ru/trains/150907_au.pdf условия] Теорзадачи: [[Медиа:15f_x1.pdf|Асимптотика]] |
+ | |||
+ | * '''14 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150914_au.dat результаты] [http://acm.math.spbu.ru/trains/150914_au.pdf условия] Теорзадачи: [[Медиа:15f_x2.pdf|Циклы for]], [[Медиа:15f_x3.pdf|Простейшие структуры данных]] | ||
+ | |||
+ | * '''21 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150921_au.dat результаты] [http://acm.math.spbu.ru/trains/150921_au.pdf условия] Теорзадачи: [[Медиа:15f_x4.pdf|Кучи, два указателя, бинпоиск]] | ||
+ | |||
+ | * '''28 сентября''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150928_au.dat результаты] [http://acm.math.spbu.ru/trains/150928_au.pdf условия] Теорзадачи: [[Медиа:15f_x5.pdf|Бинпоиск, сортировки]] | ||
+ | |||
+ | * '''05 октября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151005_au.dat результаты] [http://acm.math.spbu.ru/trains/151005_au.pdf условия] Теорзадачи: [[Медиа:15f_x6.pdf|Бинпоиск, 1D и 2D функции]] | ||
+ | |||
+ | * '''12 октября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151012_au.dat результаты] [http://acm.math.spbu.ru/trains/151012_au.pdf условия] Теорзадачи: [[Медиа:15f_x7.pdf|Кучи]] (контест про STL) | ||
+ | |||
+ | * '''19 октября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151019_au.dat результаты] [http://acm.math.spbu.ru/trains/151019_au.pdf условия] Теорзадачи: [[Медиа:15f_x8.pdf|Динамика]] ([http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151019_au2.dat Результаты практики]) | ||
+ | |||
+ | * '''26 октября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151026_au.dat результаты] [http://acm.math.spbu.ru/trains/151026_au.pdf условия] Теорзадачи: [[Медиа:15f_x9.pdf|Динамика 2]] | ||
+ | |||
+ | * '''9 ноября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151109_au.dat результаты] [http://acm.math.spbu.ru/trains/151109_au.pdf условия] Теорзадачи: [[Медиа:15f_xA.pdf|Динамика по подмножествам]] | ||
+ | |||
+ | * '''16 ноября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151116_au.dat результаты] [http://acm.math.spbu.ru/trains/151116_au.pdf условия] Теорзадачи: [[Медиа:15f_xB.pdf|dfs]] | ||
+ | |||
+ | * '''23 ноября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151123_au.dat результаты] [http://acm.math.spbu.ru/trains/151123_au.pdf условия] Теорзадачи: [[Медиа:15f_xC.pdf|bfs, dijkstra]] | ||
+ | |||
+ | * '''30 ноября .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151130_au.dat результаты] [http://acm.math.spbu.ru/trains/151130_au.pdf условия] Теорзадачи: [[Медиа:15f_xD.pdf|графы]] | ||
+ | |||
+ | * '''7 декабря .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151207_au.dat результаты] [http://acm.math.spbu.ru/trains/151207_au.pdf условия] Теорзадачи: [[Медиа:15f_xE.pdf|DSU и MST]] | ||
+ | |||
+ | * '''14 декабря .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m151214_au.dat результаты] [http://acm.math.spbu.ru/trains/151214_au.pdf условия] Теорзадачи: [[Медиа:15f_xF.pdf|Жадность и приближённые алгоритмы]] |
Текущая версия на 09:32, 5 июля 2016
Содержание
Преподаватели
- Копелиович Сергей Владимирович (burunduk30@gmail.com, vk.com/burunduk1)
- Колганов Роман Александрович (roman.kolganov@gmail.com, vk.com/rokolgan, комн. 301 в новом корпусе общежития)
- Тимофеев Антон Александрович (at1.030@gmail.com, vk.com/at_one)
Информация
Дедлайны:
- практика, сдача контест: 8 дней (дедлайн в понедельник в 23:59)
- теория в tex: 6 дней (дедлайн в субботу в 23:59)
Лекции
- 04.09 (пт) Введение. Разбор теста.
- 07.09 (пн) Асимптотика, реккурентности.
- 11.09 (пт) (скорость работы программ, структуры данных: массив, список, стек/очередь/дек, динамический массив, амортизация)
- 14.09 (пн) (структуры данных: очередь с минимумом)
- 18.09 (пт) (структуры данных: два указателя, бинпоиск, хеш-таблица)
- 21.09 (пн) (структуры данных: избавлении от амортизации, кучи, аллокаторы)
- 25.09 (пт) (структуры данных: пополняемые структуры данных, разбор выражений)
- 28.09 (пн) (Сортировки: квадратичные сортировки, QuickSort, порядковые статистики)
- 10.02 (пт) (Сортировки: порядковые статистики, MergeSort, CountSort, DigitalSort, BucketSort)
- 10.05 (пн) (Сортировки: BucketSort, Kirckpatrick Sort, inplace merge)
- 10.09 (пт) (Кучи: minmax, leftist, skew, pairing, V.E.B)
- 10.12 (пн) (Кучи: биномиальная, bootstrapping, фибоначчиева, lower bound on heap-build)
- 10.16 (пт) (Динамика: база)
- 10.19 (пн) (Динамика: квадратная, подотрезки, измельчение перехода, выбор состояния)
- 10.23 (пт) (Динамика: деревья. Кучи: концовка)
- 10.26 (пн) (Динамика: подмножества, профиль, два указателя)
- 10.30 (пт) (Динамика: подмножества, профиль, два указателя)
- 11.09 (пн) (dfs: база, двудольность, циклы)
- 11.13 (пт) (dfs: topsort, ксс, эйлеровость)
- 11.16 (пн) (dfs: 2-связность, 2-SAT, цикл де брюина)
- 11.20 (пт) (кратчайшие пути: bfs, dijkstra, $A^{*}$)
- 11.23 (пн) (кратчайшие пути: fb, floyd)
- 11.27 (пт) (Карп, Гольдберг) Карп
- 11.30 (пн) (Radix Heap, алгоритм Йена) Йен, Two Level Radix Heap
- 12.04 (пт) (DSU: списки, деревья, док-во log(log*))
- 12.07 (пн) (MST: Краскал, Прим, Борувка; функция Аккермана и СНМ) DSU из Кормена
- 12.11 (пт) (Хаффман и жадность)
- 12.14 (пн) (Приближённые алгоритмы)
Домашние задания
Быстрая аллокация памяти в c++
Все решения всех закончившихся контестов
- 01 сентября Контест: результаты условия.
- 07 сентября Контест: результаты условия Теорзадачи: Асимптотика
- 14 сентября Контест: результаты условия Теорзадачи: Циклы for, Простейшие структуры данных
- 21 сентября Контест: результаты условия Теорзадачи: Кучи, два указателя, бинпоиск
- 28 сентября Контест: результаты условия Теорзадачи: Бинпоиск, сортировки
- 05 октября . Контест: результаты условия Теорзадачи: Бинпоиск, 1D и 2D функции
- 12 октября . Контест: результаты условия Теорзадачи: Кучи (контест про STL)
- 19 октября . Контест: результаты условия Теорзадачи: Динамика (Результаты практики)
- 26 октября . Контест: результаты условия Теорзадачи: Динамика 2
- 9 ноября . Контест: результаты условия Теорзадачи: Динамика по подмножествам
- 16 ноября . Контест: результаты условия Теорзадачи: dfs
- 23 ноября . Контест: результаты условия Теорзадачи: bfs, dijkstra
- 30 ноября . Контест: результаты условия Теорзадачи: графы
- 7 декабря . Контест: результаты условия Теорзадачи: DSU и MST
- 14 декабря . Контест: результаты условия Теорзадачи: Жадность и приближённые алгоритмы