Алгоритмы 1 2015/16 весна — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
 
(не показано 50 промежуточных версий этого же участника)
Строка 28: Строка 28:
  
 
== Лекции ==
 
== Лекции ==
 +
 +
[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 Студенческий конспект]
Строка 40: Строка 44:
  
 
* 02.12 (пт) (Treap, implicit key, дополнительные операции на дереве)
 
* 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|Гаусс]]
 +
  
−
* '''8 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m160208_au.dat результаты] [http://acm.math.spbu.ru/trains/160208_au.pdf условия] Теорзадачи: [[Медиа:160208.pdf|Centroid Decomposition]]
+
[[Медиа:160411x.pdf|Тест]]
−
* '''15 февраля .''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m160215_au.dat результаты] [http://acm.math.spbu.ru/trains/160215_au.pdf условия] Теорзадачи: [[Медиа:160215.pdf|AVL, Treap]]
+

Текущая версия на 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

Лекции

Билеты коллоквиума

Программа курса

Студенческий конспект

TeX исходники конспекта

Пример оформления главы конспекта

Планы лекций

  • 02.12 (пт) (Treap, implicit key, дополнительные операции на дереве)
  • 05.06 (пт) FFT
  • 05.13 (пт) FFT

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

Результаты контестов


Тест

Источник — «http://mit.spbau.ru/sewiki/index.php?title=Алгоритмы_1_2015/16_весна&oldid=15962»