Algo 2014 2 — различия между версиями
Материал из SEWiki
Burunduk (обсуждение | вклад) (→Лекции) |
Burunduk (обсуждение | вклад) (→Домашние задания) |
||
| Строка 62: | Строка 62: | ||
[https://www.dropbox.com/sh/j8ntjdb4cs7wyil/AABxbY5LzJilZ9q_sdPBJ09qa?dl=0 Решения и условия контестов] | [https://www.dropbox.com/sh/j8ntjdb4cs7wyil/AABxbY5LzJilZ9q_sdPBJ09qa?dl=0 Решения и условия контестов] | ||
| − | * '''11 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150211_au.dat результаты] [http://acm.math.spbu.ru/trains/150211_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''11 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150211_au.dat результаты] [http://acm.math.spbu.ru/trains/150211_au.pdf условия]. Теор задачи: [[Медиа:15s_x1.pdf|AVL, treap, неявный ключ]]. |
| − | * '''18 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150218_au.dat результаты] [http://acm.math.spbu.ru/trains/150218_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''18 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150218_au.dat результаты] [http://acm.math.spbu.ru/trains/150218_au.pdf условия]. Теор задачи: [[Медиа:15s_x2.pdf|STL, BST, RB, B, AA, Persistent]]. |
| − | * '''25 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150225_au.dat результаты] [http://acm.math.spbu.ru/trains/150225_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''25 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150225_au.dat результаты] [http://acm.math.spbu.ru/trains/150225_au.pdf условия]. Теор задачи: [[Медиа:15s_x3.pdf|Дерево отрезков, ScanLine, 2D-деревья]]. |
* '''2 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150302_au.dat результаты] [http://acm.math.spbu.ru/trains/150302_au.pdf условия]. Специальный контест про 2D деревья. | * '''2 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150302_au.dat результаты] [http://acm.math.spbu.ru/trains/150302_au.pdf условия]. Специальный контест про 2D деревья. | ||
| − | * '''4 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150304_au.dat результаты] [http://acm.math.spbu.ru/trains/150304_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''4 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150304_au.dat результаты] [http://acm.math.spbu.ru/trains/150304_au.pdf условия]. Теор задачи: [[Медиа:15s_x4.pdf|LCA, RMQ, Euler Tours]]. |
| − | * '''11 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150311_au.dat результаты] [http://acm.math.spbu.ru/trains/150311_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''11 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150311_au.dat результаты] [http://acm.math.spbu.ru/trains/150311_au.pdf условия]. Теор задачи: [[Медиа:15s_x5.pdf|Heavy-Light, Euler Tour Trees, задачи на деревьях]]. |
| − | * '''18 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150318_au.dat результаты] [http://acm.math.spbu.ru/trains/150318_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''18 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150318_au.dat результаты] [http://acm.math.spbu.ru/trains/150318_au.pdf условия]. Теор задачи: [[Медиа:15s_x6.pdf|Паросочетания]]. |
| − | * '''25 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150325_au.dat результаты] [http://acm.math.spbu.ru/trains/150325_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''25 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150325_au.dat результаты] [http://acm.math.spbu.ru/trains/150325_au.pdf условия]. Теор задачи: [[Медиа:15s_x7.pdf|Потоки]]. |
| − | * '''8 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150408_au.dat результаты] [http://acm.math.spbu.ru/trains/150408_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''8 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150408_au.dat результаты] [http://acm.math.spbu.ru/trains/150408_au.pdf условия]. Теор задачи: [[Медиа:15s_x8.pdf|Mincost Потоки]]. |
| − | * '''15 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150415_au.dat результаты] [http://acm.math.spbu.ru/trains/150415_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''15 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150415_au.dat результаты] [http://acm.math.spbu.ru/trains/150415_au.pdf условия]. Теор задачи: [[Медиа:15s_x9.pdf|Строки: база]]. |
| − | * '''22 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150422_au.dat результаты] [http://acm.math.spbu.ru/trains/150422_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''22 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150422_au.dat результаты] [http://acm.math.spbu.ru/trains/150422_au.pdf условия]. Теор задачи: [[Медиа:15s_xA.pdf|Строки: бор и палниндромы]]. |
| − | * '''29 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150429_au.dat результаты] [http://acm.math.spbu.ru/trains/150429_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''29 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150429_au.dat результаты] [http://acm.math.spbu.ru/trains/150429_au.pdf условия]. Теор задачи: [[Медиа:15s_xB.pdf|Строки: суффиксные структуры]]. |
| − | * '''6 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150506_au.dat результаты] [http://acm.math.spbu.ru/trains/150506_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''6 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150506_au.dat результаты] [http://acm.math.spbu.ru/trains/150506_au.pdf условия]. Теор задачи: [[Медиа:15s_xC.pdf|битовое сжатие + ретроанализ + Гранди]]. |
| − | * '''13 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150513_au.dat результаты] [http://acm.math.spbu.ru/trains/150513_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''13 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150513_au.dat результаты] [http://acm.math.spbu.ru/trains/150513_au.pdf условия]. Теор задачи: [[Медиа:15s_xD.pdf|Гаусс]]. |
| − | * '''20 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150520_au.dat результаты] [http://acm.math.spbu.ru/trains/150520_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''20 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150520_au.dat результаты] [http://acm.math.spbu.ru/trains/150520_au.pdf условия]. Теор задачи: [[Медиа:15s_xE.pdf|Фурье]]. |
| − | * '''27 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150527_au.dat результаты] [http://acm.math.spbu.ru/trains/150527_au.pdf условия]. Теор задачи: [[Медиа: | + | * '''27 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150527_au.dat результаты] [http://acm.math.spbu.ru/trains/150527_au.pdf условия]. Теор задачи: [[Медиа:15s_xF.pdf|Теория чисел]]. |
[[Category:1 курс. Весна 2015]] | [[Category:1 курс. Весна 2015]] | ||
Текущая версия на 14:19, 29 февраля 2016
Содержание
Преподаватели
- Копелиович Сергей (burunduk30@gmail.com, vk.com/burunduk1)
- Колганов Роман (roman.kolganov@gmail.com, vk.com/rokolgan)
- Мишунин Александр (alexander.mishunin@gmail.com, vk.com/amishunin)
Информация
Дедлайны:
- практика: 8 дней (дедлайн в среду в 23:59)
- теория: 6 дней (дедлайн в понедельник в 23:59), после этого можно до вторника 23:59 исправлять замечания.
Лекции
Билеты к коллоквиуму (новая версия)
Конспект (набранный силами студентов)
- 02.10 (вторник) BST
- 02.17 (вторник) BST
- 02.21 (суббота) Дерево отрезков
- 02.24 (вторник) Двухмерные деревья, ScanLine
- 03.03 (вторник) RMQ & LCA
- 03.04 (среда) Функции на путях дерева, MST за O(E)
- 03.10 (вторник) Heavy-Light-Decomposition, Euler-Tour-Trees, LA
- 03.18 (среда) Паросочетания-1
- 03.24 (вторник) Потоки-1
- 03.25 (среда) Паросочетания-2 и раскраски
- 03.26 (четверг) Потоки-2 (LR, Диниц)
- 04.07 (вторник) Потоки-3 (mincost, Венгерка) Конспект от Andrew Goldberg по потокам и mincost тоже
- 04.08 (среда) Потоки-4 (preflow-push, global cut) Конспект от Burunduk1 про preflow-push дополненная версия
- 04.14 (вторник) Строки-1 (КМП, Z, Боер-Мур, Хеши, LCP)
- 04.15 (среда) Строки-2 (алгоритм Манакера, дерево палиндромов) (ещё про палиндромы)
- 04.21 (вторник) Строки-3 (бор, суффиксное дерево, Ахо-Корасик)
- 04.22 (среда) Строки-4 (Укконен)
- 04.28 (вторник) Строки-5 (Cуффиксный массив)
- 04.29 (среда) Хеширование (5-й курс Hash1) (5-й курс Hash2) (Совершенное хеширование)
- 05.05 (вторник) Игры и битовое сжатие
- 05.06 (среда) Битовое сжатие и игры
- 05.12 (вторник) Гаусс и линейная алгебра
- 05.13 (среда) Автоматы и изоморфизмы
- 05.18 (вторник) Фурье и BigInteger
- 05.19 (среда) Фурье и BigInteger
- 05.27 (среда) Теория чисел
Домашние задания
Быстрая аллокация памяти в c++
- 11 февраля Контест: результаты условия. Теор задачи: AVL, treap, неявный ключ.
- 18 февраля Контест: результаты условия. Теор задачи: STL, BST, RB, B, AA, Persistent.
- 25 февраля Контест: результаты условия. Теор задачи: Дерево отрезков, ScanLine, 2D-деревья.
- 2 марта Контест: результаты условия. Специальный контест про 2D деревья.
- 4 марта Контест: результаты условия. Теор задачи: LCA, RMQ, Euler Tours.
- 11 марта Контест: результаты условия. Теор задачи: Heavy-Light, Euler Tour Trees, задачи на деревьях.
- 18 марта Контест: результаты условия. Теор задачи: Паросочетания.
- 25 марта Контест: результаты условия. Теор задачи: Потоки.
- 8 апреля Контест: результаты условия. Теор задачи: Mincost Потоки.
- 15 апреля Контест: результаты условия. Теор задачи: Строки: база.
- 22 апреля Контест: результаты условия. Теор задачи: Строки: бор и палниндромы.
- 29 апреля Контест: результаты условия. Теор задачи: Строки: суффиксные структуры.
- 6 мая Контест: результаты условия. Теор задачи: битовое сжатие + ретроанализ + Гранди.
- 13 мая Контест: результаты условия. Теор задачи: Гаусс.
- 20 мая Контест: результаты условия. Теор задачи: Фурье.
- 27 мая Контест: результаты условия. Теор задачи: Теория чисел.
