Алгоритмы 3 2016/17 осень
Материал из SEWiki
Содержание
Отчётность
- Теоретический зачёт/экзамен в конце курса
- Еженедельные задачи в контест на реализацию
Информация от 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)
- (Тест, на котором симплекс работает за экспоннету)
- (Взвешенное паросочетание в произвольном графе)
- (Реализация и подробное описание алгоритма поиска взвешенного паросочетания в произвольном графе)
