SEWiki - Вклад участника [ru]

Алгоритмы 1 2015/16 весна

2019-04-21T14:50:39Z

Burunduk:

== Преподаватели ==

* Копелиович Сергей Владимирович (burunduk30@gmail.com, [https://vk.com/burunduk1 vk.com/burunduk1])

* Колганов Роман Александрович (roman.kolganov@gmail.com, [https://vk.com/rokolgan vk.com/rokolgan], комн. 301 в новом корпусе общежития)

* Тимофеев Антон Александрович (at1.030@gmail.com, [https://vk.com/at_one vk.com/at_one])

== Информация ==

[[algo_1_2015/16_spring_groups | Деление на группы]]

[https://docs.google.com/spreadsheets/d/1y3YSd-G0skS0BWJ_aAYAiJCyQzry_guhZrib5RrQYI8/edit#gid=0 Результаты практики]

Дедлайны:

* практика, сдача контест: 8 дней (дедлайн в понедельник в 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/ TeX исходники конспекта]

[http://acm.math.spbu.ru/~sk1/mm/au-download/conspect/0208-Kopeliovich.tex Пример оформления главы конспекта]

[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|Тест]]

Алгоритмы 1MIT весна 2018

2018-05-23T14:13:10Z

Burunduk: /* Домашние задания */

== Преподаватели ==

* Копелиович Сергей Владимирович (burunduk30@gmail.com, [https://vk.com/burunduk1 vk.com/burunduk1])

* Гардер Антон Владимирович (algo-au17@garder.me, [https://t.me/avgarder t.me/avgarder])

* Колганов Роман Александрович (roman.kolganov@gmail.com, [https://vk.com/rokolgan vk.com/rokolgan], аналогичный телеграм)

== Информация ==

[https://docs.google.com/spreadsheets/d/e/2PACX-1vSaHymqm6cL24Gi3k-1w-QHvdimt0srf9Jt62_SkMrpzMs6uTXil_hJJHhgps8atFvkEjeUdVBpJCYV/pubhtml Результаты проверки домашних заданий]

Дедлайны (предварительная версия):

* практика, контест: среда 24:00

* теория в tex: суббота 24:00, исправления -- понедельник до 24:00

== Лекции ==

[http://acm.math.spbu.ru/~sk1/courses/1718s_au/conspect/conspect.pdf Конспект]

Билеты к [http://acm.math.spbu.ru/~sk1/courses/1718s_au/questions-algo-2017s-exam1.pdf коллоквиуму]

[http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections Краткие планы лекций]

* 02.12 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-02-12-complexity.html Сложность]: NP-hard, сведения, гипотезы)

* 02.19 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-02-19-random.html Рандом]: RP, ZPP, BPP, примеры, 3-SAT, поллард)

* 02.26 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-02-26-bfs.html Кратчайшие пути]: bfs, 0-1-k-версия, Дейкстра, A*, Флойд)

* 03.05 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-03-05-fb.html Кратчайшие пути]: Форд-Беллман, отрицательные циклы)

* 03.12 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-03-12-mst.html DSU/MST]: DSU за log*, Краскал/Прим/Борувка)

* 03.19 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-03-17-greedy.html Жадность]: Хаффман, коммивояжёр и гамильтонов путь, компаратор)

* 03.26 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-03-24-centroid.html Рюкзаки и центроиды]: PTAS/FPTAS, partition/knapsack/bin-packing, построение центроидной декомпозиции)

* 04.10 (вт) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-04-10-bst.html Деревья поиска 1]: BST, ABL, B, B*, 2-3, RB, AA, Неявный ключ)

* 04.16 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-04-16-bst.html Деревья поиска 2]: Treap, RBST, Персистентные структуры данных)

* 05.07 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-05-07-range-tree.html Деревья отрезков]: Снизу/сверху, сканлайн, 2D-деревья)

* 05.14 (вт) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-05-14-rmq-lca.html RMQ/LCA]: Sparse Table, Фарах-Колтон-Бендер, <math>RMQ \rightarrow LCA \rightarrow RMQ \pm 1</math>, LA, Вишкин)

* 05.21 (вт) ([http://acm.math.spbu.ru/~sk1/courses/1718s_au/lections/2018-05-21-hld-lct-mst.html HLD]: Heavy-Light-Decomposition, Link-Cut-Tree, MST за O(n))

== Доплекции ==

* 02.26 (пн) Квадратный корень по модулю. Перебор с отсечением по ответу.

* 03.05 (пн) Алгоритм Гольдберга поиска кратчайшего пути.

* 03.12 (пн) Алгоритм Йена. Обратная функция Аккермана: доказательство O((n+m)α).

== Домашние задания ==

[http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/ TeX исходники практик]

[http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/ Условия теорзадачек]

[http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/ Условия контестов]

* '''10 февраля.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180210_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180210_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180210 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180210_au.pdf условия] Сложная задача по сложности

* '''14 февраля.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180214_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180214_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180214 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180214_au.pdf условия (прошлый семестр)] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180214.pdf Сложность] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180214/ TeX:src]

* '''21 февраля.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180221_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180221_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180221 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180221_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180221.pdf Рандом, Поллард] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180221/ TeX:src] +[http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180228_au.pdf условия контеста по рандому]

* ''' 28 February. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180228_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180228_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180228 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180228_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180228.pdf bfs/dijkstra] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180228/ TeX:src]

* ''' 07 March. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180307_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180307_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180307 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180307_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180307.pdf Форд-Беллман] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180307/ TeX:src]

* ''' 14 March. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180314_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180314_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180314 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180314_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180314.pdf MST и DSU] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180314/ TeX:src]

* ''' 21 March. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180321_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180321_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180321 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180321_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180321.pdf Жадность] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180321/ TeX:src]

* ''' 28 March. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180328_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180328_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180328 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180328_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180328.pdf Приближения, центроиды] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180328/ TeX:src]

* ''' 11 April. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180411_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180411_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180411 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180411_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180411.pdf Деревья поиска] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180411/ TeX:src]

* ''' 18 April. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180418_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180418_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180418 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180418_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180418.pdf Персистентность] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180418/ TeX:src]

* ''' 25 April. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180425_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180425_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180425 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180425_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180425.pdf SQRT] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180425/ TeX:src]

* ''' 10 May. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180509_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180509_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180509 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180509_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180510.pdf Дерево отрезков] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180510/ TeX:src]

* ''' 16 May. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180516_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180516_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180516 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180516_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180516.pdf LCA] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180516/ TeX:src]

* ''' 23 May. ''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m180523_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=180523_au дорешка][http://acm.math.spbu.ru/~sk1/courses/1718s_au/solutions/180523 решения] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/statements/180523_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice/180523.pdf HLD, Link-Cut] [http://acm.math.spbu.ru/~sk1/courses/1718s_au/practice-src/180523/ TeX:src]

2017-10-23T11:57:18Z

Burunduk: /* Лекции */

== Преподаватели ==

* Копелиович Сергей Владимирович (burunduk30@gmail.com, [https://vk.com/burunduk1 vk.com/burunduk1])

* Подгузов Никита Владимирович (npodguzov@yandex.ru, [https://vk.com/nikitosh239 vk.com/nikitosh239])

* Колганов Роман Александрович (roman.kolganov@gmail.com, [https://vk.com/rokolgan vk.com/rokolgan], к.301 в общежитии)

== Информация ==

[[algo_2016_1_groups_spring | Деление на группы]]

[https://docs.google.com/spreadsheets/d/1fKOgMvImMJUqLiIuqHiuNchO4CqjsX7ImbPWwzn-qjs/edit#gid=0 Результаты практики]

* практика, контест (9 дней): суббота 24:00

* теория в tex (6 дней): среда 24:00

== Лекции ==

[http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/conspect.pdf Конспект] [https://acm.math.spbu.ru/~sk1/mm/au-download/conspect/conspect_15s.pdf (старая версия прошлых лет)]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections Краткие планы лекций]

* 04.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-09-04-Matching.html Паросочетания]: Кун, оптимизации, VC, IS)

* 11.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-09-11-Matching.html Паросочетания]: Stable matching, Венгерка, Раскраски)

* 18.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-09-18-Flows.html Потоки]: Форд-Фалкерсон, Эдмондс-Карп, Scaling)

* 25.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-09-25-Flows.html Потоки]: Диниц, Карзанов, Каргер-Штейн)

* 02.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-10-02-Mincost.html Mincost Потоки]: дополняющие пути, алгоритм Клейна, полиномиальный алгоритм)

* 09.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-10-09-Strings-Hash.html Строки]: префикс-фукнция, Z-функция, хеши...)

* 16.10 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-10-16-Suffarray.html Суффиксный массив]: за O(nlogn), за O(n), Касаи, поиск строки в тексте)

* 26.10 (чт) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-10-26-Sufftree.html Ахо-Корасик, Укконен]: всё про бор и алгоритмы с использованием бора)

== Клуб любителей алгоритмов ==

Понедельник, после 4-й пары, та же аудитория.

* 25.09 (пн) ([http://acm.math.spbu.ru/~sk1/courses/1718f_au2/lections/2017-09-25-Flows-bonus.html Быстрые потоки]: preflow push & relabel, highest vertex, global relabeling). [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/0925-preflow-push-3.pdf Конспект]

* 09.10 (пн) Быстрые mincost потоки: cost-scaling через push-relabel за <math>O(V^3 \log C)</math>

== Домашние задания ==

[[help_algosvn | svn для сдачи теордз]]

[http://acm.math.spbu.ru/cgi-bin/monitor_au.pl Результаты контестов]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/ TeX исходники практик]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/ Условия теорзадачек]

[http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/ Условия контестов]

* '''8 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170908_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170908_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/170908 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/170908_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/170908.pdf Паросочетания] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/170908/hw.tex исходник]

* '''15 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170915_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170915_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/170915 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/170915_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/170915.pdf Паросочетания-2] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/170915/hw.tex исходник]

* '''22 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170922_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170922_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/170922 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/170922_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/170922.pdf Потоки] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/170922/hw.tex исходник]

* '''29 сентября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m170929_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=170929_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/170929 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/170929_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/170929.pdf Потоки-2] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/170929/hw.tex исходник]

* '''6 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171006_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171006_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/171006 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/171006_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/171006.pdf Mincost потоки] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/171006/hw.tex исходник]

* '''13 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171013_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171013_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/171013 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/171013_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/171013.pdf Базовые алгоритмы на строках] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/171013/hw.tex исходник]

* '''20 октября.''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m171020_au.dat результаты] [http://acm.math.spbu.ru/tsweb/monitor?cid=171020_au дорешка] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/solutions/171020 решения] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/statements/171020_au.pdf условия] Теорзадачи: [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/171020.pdf Суффиксный массив, бор, хеши] [http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice-src/171020/hw.tex исходник]