Алгоритмы 3 2016/17 осень — различия между версиями
Материал из SEWiki
Burunduk (обсуждение | вклад) (→Планы лекций) |
(→Информация от 01.12.2016) |
||
| (не показано 16 промежуточных версий 2 участников) | |||
| Строка 3: | Строка 3: | ||
* Теоретический зачёт/экзамен в конце курса | * Теоретический зачёт/экзамен в конце курса | ||
* Еженедельные задачи в контест на реализацию | * Еженедельные задачи в контест на реализацию | ||
| + | |||
| + | === Информация от 01.12.2016 === | ||
| + | Взято из группы и немного переписано: | ||
| + | |||
| + | * Недифференцированный зачёт. При этом сдаём дифференцировано и 2-3 выражается в незачёт, а 4-5 в зачёт. | ||
| + | * На зачёте сдаём теорию без конспекта. | ||
| + | * 8-го последняя пара, 15-го утром консультация, 17-го в субботу зачёт. | ||
| + | * Задачи из контеста можно будет сдавать до 22-го декабря 23:59. | ||
| + | * 23-го по плану у вас должен стоять зачёт. Если зачёт сдан хотя бы на три и в контесте сдано строго больше половины, то до 29-го можно досдать практику и получить зачёт. Если условия не выполняются - результат получения зачёта неопределён. | ||
== Контест == | == Контест == | ||
* [http://acm.math.spbu.ru/tsweb/ Тестирующая система] | * [http://acm.math.spbu.ru/tsweb/ Тестирующая система] | ||
| − | * [http://acm.math.spbu.ru/ | + | * [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/160901_au.pdf Условия задач] |
* [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160901_au.dat Результаты] | * [http://acm.math.spbu.ru/cgi-bin/monitor_au.pl/m160901_au.dat Результаты] | ||
| Строка 13: | Строка 22: | ||
[http://acm.math.spbu.ru/~sk1/courses/1617f_au3/program.pdf Программа курса] | [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/program.pdf Программа курса] | ||
| + | |||
| + | [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/questions-algo3-2016f-exam.pdf Вопросы к экзамену] | ||
* 08.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0908-FFT.html FFT и длинная арифметика] (конспект: Надя Бугакова) | * 08.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0908-FFT.html FFT и длинная арифметика] (конспект: Надя Бугакова) | ||
| Строка 19: | Строка 30: | ||
* 29.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0929-Matching.html Паросочетания в произвольном графе] (конспект: Дима Лапшин) | * 29.09 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/0929-Matching.html Паросочетания в произвольном графе] (конспект: Дима Лапшин) | ||
* 06.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1006-LP.html Линейное программирование и симплекс метод] (конспект: Юра Ребрик) | * 06.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1006-LP.html Линейное программирование и симплекс метод] (конспект: Юра Ребрик) | ||
| − | * 13.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1013-LP.html Линейное программирование, продолжение] (конспект: Суворов Егор) | + | * 13.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1013-LP.html Линейное программирование, продолжение] (конспект: Суворов Егор) |
* 20.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1020-LP.html Линейное программирование, часть 3] (конспект: ?) | * 20.10 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1020-LP.html Линейное программирование, часть 3] (конспект: ?) | ||
| + | * 01.11 (вт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1101-Planar.html Планарные графы] (конспект: Дима Лапшин) | ||
| + | * 17.11 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1117-Planar-random.html Окончание планарных графов, рандомизированные алгоритмы] (конспект: Глеб Валин) | ||
| + | * 24.11 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1124-Planes-random.html Полуплоскости, рандомизированные алгоритмы] (конспект: Лабутин Игорь) | ||
| + | * 01.12 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1201-Polygons.html Выпуклые многоугольники, динамическая выпуклая оболочка] (конспект: Никонов Миша) | ||
| + | * 08.12 (чт) [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/lections/1208-Math.html Диагарамма Вороного за <math>n^2</math>, корни многочленов в R, C, <math>F_p</math>, факторизация чисел Крайчиком] (конспект: Подгузов Никита) | ||
| + | * 15.12 (чт) '''Консультация''' | ||
| + | * 17.12 (сб) '''Теорзачёт''' | ||
| + | == Литература, статьи == | ||
| − | = | + | === Линейное программирование === |
| + | * [http://www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf (Эллипсоиды)] | ||
* [http://cs.brown.edu/courses/csci1490/notes/day9.pdf (Bland's rule proof)] | * [http://cs.brown.edu/courses/csci1490/notes/day9.pdf (Bland's rule proof)] | ||
* [http://www-math.mit.edu/~goemans/notes-lp.ps (LP: Duality, Interior Point Ye's algorithm)] | * [http://www-math.mit.edu/~goemans/notes-lp.ps (LP: Duality, Interior Point Ye's algorithm)] | ||
| Строка 30: | Строка 50: | ||
* [http://old.compsciclub.ru/courses/linearprogramming (CS-Club, Максим Бабенко, видео)] | * [http://old.compsciclub.ru/courses/linearprogramming (CS-Club, Максим Бабенко, видео)] | ||
* [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture06.pdf (MaxFlow-MinCut duality)] | * [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture06.pdf (MaxFlow-MinCut duality)] | ||
| + | * [https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube (Тест, на котором симплекс работает за экспоннету)] | ||
| + | * [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture11.pdf (Взвешенное паросочетание в произвольном графе)] | ||
| + | * [http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)] | ||
| + | |||
| + | === Планарные графы === | ||
| + | |||
| + | * [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/O(n)_new.pdf Ulrik Brandes'2011, алгоритм за O(n)] | ||
| + | * [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/demoucron-lucie-martinet.pdf Алгоритм Демукрона] | ||
| + | * [http://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/schnyder-grid-embedding.pdf Шнайдер'1989, укладка на гриде] | ||
Текущая версия на 19:06, 25 декабря 2016
Содержание
Отчётность
- Теоретический зачёт/экзамен в конце курса
- Еженедельные задачи в контест на реализацию
Информация от 01.12.2016
Взято из группы и немного переписано:
- Недифференцированный зачёт. При этом сдаём дифференцировано и 2-3 выражается в незачёт, а 4-5 в зачёт.
- На зачёте сдаём теорию без конспекта.
- 8-го последняя пара, 15-го утром консультация, 17-го в субботу зачёт.
- Задачи из контеста можно будет сдавать до 22-го декабря 23:59.
- 23-го по плану у вас должен стоять зачёт. Если зачёт сдан хотя бы на три и в контесте сдано строго больше половины, то до 29-го можно досдать практику и получить зачёт. Если условия не выполняются - результат получения зачёта неопределён.
Контест
Планы лекций
- 08.09 (чт) FFT и длинная арифметика (конспект: Надя Бугакова)
- 15.09 (чт) Суффиксный автомат (конспект: Оля Черникова)
- 22.09 (чт) Суффиксный автомат и алгоритм Хопкрофта (конспект: Оля Черникова, Дима Лапшин)
- 29.09 (чт) Паросочетания в произвольном графе (конспект: Дима Лапшин)
- 06.10 (чт) Линейное программирование и симплекс метод (конспект: Юра Ребрик)
- 13.10 (чт) Линейное программирование, продолжение (конспект: Суворов Егор)
- 20.10 (чт) Линейное программирование, часть 3 (конспект: ?)
- 01.11 (вт) Планарные графы (конспект: Дима Лапшин)
- 17.11 (чт) Окончание планарных графов, рандомизированные алгоритмы (конспект: Глеб Валин)
- 24.11 (чт) Полуплоскости, рандомизированные алгоритмы (конспект: Лабутин Игорь)
- 01.12 (чт) Выпуклые многоугольники, динамическая выпуклая оболочка (конспект: Никонов Миша)
- 08.12 (чт) Диагарамма Вороного за , корни многочленов в R, C, , факторизация чисел Крайчиком (конспект: Подгузов Никита)
- 15.12 (чт) Консультация
- 17.12 (сб) Теорзачёт
Литература, статьи
Линейное программирование
- (Эллипсоиды)
- (Bland's rule proof)
- (LP: Duality, Interior Point Ye's algorithm)
- (Кормен 2013.djvu)
- (CS-Club, Максим Бабенко, видео)
- (MaxFlow-MinCut duality)
- (Тест, на котором симплекс работает за экспоннету)
- (Взвешенное паросочетание в произвольном графе)
- (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)
