Алгоритмы 1 2015/16 весна — различия между версиями
Материал из SEWiki
Burunduk (обсуждение | вклад) (→Лекции) |
Burunduk (обсуждение | вклад) |
||
| (не показано 57 промежуточных версий 2 участников) | |||
| Строка 18: | Строка 18: | ||
* теория в tex: 6 дней (мягкий дедлайн с возможностью исправлений в пятницу в 23:59, жёсткий дедлайн в субботу в 23:59) | * теория в tex: 6 дней (мягкий дедлайн с возможностью исправлений в пятницу в 23:59, жёсткий дедлайн в субботу в 23:59) | ||
| + | |||
| + | Личное ДЗ: | ||
| + | |||
| + | * [https://docs.google.com/spreadsheets/d/1y3YSd-G0skS0BWJ_aAYAiJCyQzry_guhZrib5RrQYI8/edit#gid=162090631 Распределение, результаты] | ||
| + | |||
| + | * Выполняется индивидуально | ||
| + | |||
| + | * Первый дедлайн 25 февраля, 16:00; второй дедлайн 12 марта в 16:00 | ||
== Лекции == | == Лекции == | ||
| + | |||
| + | [http://acm.math.spbu.ru/~sk1/mm/au-lections/questions-algo-2016s-exam1.pdf Билеты коллоквиума] | ||
| + | |||
| + | [http://acm.math.spbu.ru/~sk1/mm/au-lections/program.pdf Программа курса] | ||
[http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/conspect_15s.pdf Студенческий конспект] | [http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/conspect_15s.pdf Студенческий конспект] | ||
[http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/ TeX исходники конспекта] | [http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/ TeX исходники конспекта] | ||
| + | |||
| + | [http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/0208-Kopeliovich.tex Пример оформления главы конспекта] | ||
[http://acm.math.spbu.ru/~sk1/mm/au-lections/ Планы лекций] | [http://acm.math.spbu.ru/~sk1/mm/au-lections/ Планы лекций] | ||
| − | * | + | * 02.09 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-02-09-BST.html (BST, AVL, persistent)] |
| − | * | + | * 02.12 (пт) (Treap, implicit key, дополнительные операции на дереве) |
| + | |||
| + | * 03.11 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-03-11-HLD-ET.html LCA.Offline; LA; Euler-Tour-Tree; HLD; Link-Cut] [https://pdfs.semanticscholar.org/973f/17392cb7b417271e9d482d17a44a8c70c70a.pdf LA1] [https://en.wikipedia.org/wiki/Level_ancestor_problem LA2] [https://habrahabr.ru/company/spbau/blog/216733/ Link-Cut] | ||
| + | |||
| + | * 03.15 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-03-15-MST.html Функции на путях дерева; MST за O(n+m)] | ||
| + | |||
| + | * 03.18 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-03-18-Matching.html Паросочетания] | ||
| + | |||
| + | * 03.22 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-03-22-Matching.html Паросочетания, раскраски] | ||
| + | |||
| + | * 03.25 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-03-25-Matching-Coloring.html Раскраски, Венгерка] | ||
| + | |||
| + | * 04.05 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-05-Flows.html Потоки, Потоки, Потоки!] | ||
| + | |||
| + | * 04.08 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-08-Flows.html Быстрые потоки] | ||
| + | |||
| + | * 04.12 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-12-Flows.html LR-поток, Глобальный разрез] | ||
| + | |||
| + | * 04.15 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-15-FlowMinCost.html Mincost поток] | ||
| + | |||
| + | * 04.19 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-19-Strings-Hash.html Строки: база, хеширование] | ||
| + | |||
| + | * 04.22 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-22-1-Strings-Hash-SA.html Строки: хеширование, начало суфф массивов] | ||
| + | |||
| + | * 04.22 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-22-2-Strings-SA.html Строки: суфф массивы] | ||
| + | |||
| + | * 04.26 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-26-Strings-Trie.html Строки: Ахо-Корасик, Укконен] | ||
| + | |||
| + | * 04.29 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-04-29-Hashing.html Конец Укконена, Хеширование] | ||
| + | |||
| + | * 05.05 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-05-05-Games-Numbers.html Игры, теория чисел] | ||
| + | |||
| + | * 05.06 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-05-06-Fourier.html FFT] | ||
| + | |||
| + | * 05.13 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-05-13-Fourier.html FFT] | ||
| + | |||
| + | * 05.17 (вт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-05-17-Complexity.html Классы сложности] | ||
| + | |||
| + | * 05.20 (пт) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2016-05-20-Gauss.html Гаусс] | ||
== Домашние задания == | == Домашние задания == | ||
| + | [http://acm.math.spbu.ru/cgi-bin/monitor.pl/ Результаты контестов] | ||
| + | * '''08 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160208_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160208_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160208 решения] [http://acm.math.spbu.ru/trains/160208_au.pdf условия] Теорзадачи: [[Медиа:160208.pdf|Centroid Decomposition]] | ||
| + | * '''15 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160215_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160215_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160215 решения] [http://acm.math.spbu.ru/trains/160215_au.pdf условия] Теорзадачи: [[Медиа:160215.pdf|AVL, Treap]] | ||
| + | * '''22 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160222_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160222_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160222 решения] [http://acm.math.spbu.ru/trains/160222_au.pdf условия] Теорзадачи: [[Медиа:160222.pdf|Persistent]] | ||
| + | * '''29 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160229_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160229_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160229 решения] [http://acm.math.spbu.ru/trains/160229_au.pdf условия] Теорзадачи: [[Медиа:160229.pdf|Дерево отрезков]] | ||
| + | * '''07 марта .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160307_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160307_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160307 решения] [http://acm.math.spbu.ru/trains/160307_au.pdf условия] Теорзадачи: [[Медиа:160307.pdf|LCA и Эйлеров обход]] | ||
| + | * '''14 марта .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160314_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160314_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160314 решения] [http://acm.math.spbu.ru/trains/160314_au.pdf условия] Теорзадачи: [[Медиа:160314.pdf|Euler-Tour-Tree, HLD]] | ||
| + | * '''21 марта .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160321_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160321_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160321 решения] [http://acm.math.spbu.ru/trains/160321_au.pdf условия] Теорзадачи: [[Медиа:160321.pdf|Паросочетания и контест на HLD]] | ||
| + | * '''04 апреля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160404_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160404_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160404 решения] [http://acm.math.spbu.ru/trains/160404_au.pdf условия] Теорзадачи: [[Медиа:160404.pdf|Паросочетания и венгерка]] | ||
| + | * '''11 апреля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160411_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160411_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160411 решения] [http://acm.math.spbu.ru/trains/160411_au.pdf условия] Теорзадачи: [[Медиа:160411.pdf|Потоки]] | ||
| + | * '''18 апреля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160418_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160418_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160418 решения] [http://acm.math.spbu.ru/trains/160418_au.pdf условия] Теорзадачи: [[Медиа:160418.pdf|Mincost потоки]] | ||
| + | * '''25 апреля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160425_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160425_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160425 решения] [http://acm.math.spbu.ru/trains/160425_au.pdf условия] Теорзадачи: [[Медиа:160425.pdf|Строки: база]] | ||
| + | * '''2 мая .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160502_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160502_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160502 решения] [http://acm.math.spbu.ru/trains/160502_au.pdf условия] Теорзадачи: [[Медиа:160502.pdf|Строки: бор]] | ||
| + | * '''9 мая .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160509_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160509_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160509 решения] [http://acm.math.spbu.ru/trains/160509_au.pdf условия] Теорзадачи: [[Медиа:160509.pdf|Строки, числа, игры]] | ||
| + | * '''16 мая .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160516_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160516_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160516 решения] [http://acm.math.spbu.ru/trains/160516_au.pdf условия] Теорзадачи: [[Медиа:160516.pdf|Фурье]] | ||
| + | * '''23 мая .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160523_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=160523_au дорешка][http://acm.math.spbu.ru/~sk1/mm/au-download/160523 решения] [http://acm.math.spbu.ru/trains/160523_au.pdf условия] Теорзадачи: [[Медиа:160523.pdf|Гаусс]] | ||
| + | |||
| − | + | [[Медиа:160411x.pdf|Тест]] | |
Текущая версия на 17:50, 21 апреля 2019
Содержание
Преподаватели
- Копелиович Сергей Владимирович (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, жёсткий дедлайн в субботу в 23:59)
Личное ДЗ:
- Выполняется индивидуально
- Первый дедлайн 25 февраля, 16:00; второй дедлайн 12 марта в 16:00
Лекции
Пример оформления главы конспекта
- 02.09 (вт) (BST, AVL, persistent)
- 02.12 (пт) (Treap, implicit key, дополнительные операции на дереве)
- 03.15 (вт) Функции на путях дерева; MST за O(n+m)
- 03.18 (пт) Паросочетания
- 03.22 (вт) Паросочетания, раскраски
- 03.25 (пт) Раскраски, Венгерка
- 04.05 (вт) Потоки, Потоки, Потоки!
- 04.08 (пт) Быстрые потоки
- 04.12 (вт) LR-поток, Глобальный разрез
- 04.15 (пт) Mincost поток
- 04.19 (вт) Строки: база, хеширование
- 04.22 (пт) Строки: хеширование, начало суфф массивов
- 04.22 (пт) Строки: суфф массивы
- 04.26 (вт) Строки: Ахо-Корасик, Укконен
- 04.29 (пт) Конец Укконена, Хеширование
- 05.05 (пт) Игры, теория чисел
- 05.06 (пт) FFT
- 05.13 (пт) FFT
- 05.17 (вт) Классы сложности
- 05.20 (пт) Гаусс
Домашние задания
- 08 февраля . Контест: результаты дорешкарешения условия Теорзадачи: Centroid Decomposition
- 15 февраля . Контест: результаты дорешкарешения условия Теорзадачи: AVL, Treap
- 22 февраля . Контест: результаты дорешкарешения условия Теорзадачи: Persistent
- 29 февраля . Контест: результаты дорешкарешения условия Теорзадачи: Дерево отрезков
- 07 марта . Контест: результаты дорешкарешения условия Теорзадачи: LCA и Эйлеров обход
- 14 марта . Контест: результаты дорешкарешения условия Теорзадачи: Euler-Tour-Tree, HLD
- 21 марта . Контест: результаты дорешкарешения условия Теорзадачи: Паросочетания и контест на HLD
- 04 апреля . Контест: результаты дорешкарешения условия Теорзадачи: Паросочетания и венгерка
- 11 апреля . Контест: результаты дорешкарешения условия Теорзадачи: Потоки
- 18 апреля . Контест: результаты дорешкарешения условия Теорзадачи: Mincost потоки
- 25 апреля . Контест: результаты дорешкарешения условия Теорзадачи: Строки: база
- 2 мая . Контест: результаты дорешкарешения условия Теорзадачи: Строки: бор
- 9 мая . Контест: результаты дорешкарешения условия Теорзадачи: Строки, числа, игры
- 16 мая . Контест: результаты дорешкарешения условия Теорзадачи: Фурье
- 23 мая . Контест: результаты дорешкарешения условия Теорзадачи: Гаусс
