Алгоритмы 3 2016/17 осень — различия между версиями
Материал из SEWiki
Burunduk (обсуждение | вклад) (→Литература по LP) |
Burunduk (обсуждение | вклад) (→Планы лекций) |
||
| Строка 21: | Строка 21: | ||
* 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 Окончание планарных графов, рандомизированные алгоритмы] (конспект: ?) | ||
=== Литература по LP === | === Литература по LP === | ||
| Строка 33: | Строка 35: | ||
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture11.pdf (Взвешенное паросочетание в произвольном графе)] | * [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture11.pdf (Взвешенное паросочетание в произвольном графе)] | ||
* [http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)] | * [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, укладка на гриде] | ||
Версия 00:26, 2 ноября 2016
Содержание
Отчётность
- Теоретический зачёт/экзамен в конце курса
- Еженедельные задачи в контест на реализацию
Контест
Планы лекций
- 08.09 (чт) FFT и длинная арифметика (конспект: Надя Бугакова)
- 15.09 (чт) Суффиксный автомат (конспект: Оля Черникова)
- 22.09 (чт) Суффиксный автомат и алгоритм Хопкрофта (конспект: Оля Черникова, Дима Лапшин)
- 29.09 (чт) Паросочетания в произвольном графе (конспект: Дима Лапшин)
- 06.10 (чт) Линейное программирование и симплекс метод (конспект: Юра Ребрик)
- 13.10 (чт) Линейное программирование, продолжение (конспект: Суворов Егор)
- 20.10 (чт) Линейное программирование, часть 3 (конспект: ?)
- 01.11 (вт) Планарные графы (конспект: Дима Лапшин)
- 17.11 (чт) Окончание планарных графов, рандомизированные алгоритмы (конспект: ?)
Литература по LP
- (Эллипсоиды)
- (Bland's rule proof)
- (LP: Duality, Interior Point Ye's algorithm)
- (Кормен 2013.djvu)
- (CS-Club, Максим Бабенко, видео)
- (MaxFlow-MinCut duality)
- (Тест, на котором симплекс работает за экспоннету)
- (Взвешенное паросочетание в произвольном графе)
- (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)
