Теория сложности I ------------------ Модели вычислений: RAM, машина Тьюринга decision vs search задачи DTime, формулировка теоремы временной иерархии Определения классов P, EXP P != EXP Класс NP (два определения, через н.м.т. и через подсказку) NP subset EXP Полиномиальное сведение, классы NP-hard, NP-complete Определение класса coNP Теория сложности II ------------------- Доказательство что множество 2^{натуральные числа} несчётно. Доказательство теоремы о временной иерархии Понятие алгоритмически неразрешимой задачи, задача Halting Problem (без доказательства неразрешимости) Доказательство теоремы Кука (CIRCUIT-SAT это np-трудная задача) Вероятностные алгоритмы: классы RP, coRP, BPP. Понижение ошибки в RP Понижение ошибки в BPP (без доказательства) Связь RP и NP: RP subset NP Класс ZPP *Алгоритм Миллера-Рабина (без доказательства оценки на ошибку) ZPP = RP пересечь coRP (на практике через неделю) Хеширование и Хеш-Таблица ------------------------- Хеш-Таблица с закрытой адресацией (separate chaining) Хеш-Таблица с открытой адресацией (open addressing) Удаление в Х.Т. с открытой адресацией Переаллокация в Хеш-таблицах Универсальное хеширование: Определение, д-во гарантии для separate chaining *Универсальное хеширование: доказательство что (ax+b)%p%m универсально Хеширование строк: Хеш подстроки. *Хеширование строк: сравнение строк на меньше/больше Хеширование строк: Оценка вероятности ошибки если p выбрано случайно. Perfect Хеширование, паросочетание ---------------------------------- Perfect хеширование, квадратичное число ячеек Perfect хеширование, Двух-уровневая схема Парадокс дней рождений. Оценка снизу вероятности что sqrt(n) случайных семплов из n поколизятся. Парадокс дней рождений. Оценка сверху вероятности что sqrt(n) случайных семплов из n поколизятся. Двудольные паросочетания. Удлиняющая цепочка и лемма о ней Двудольные паросочетания. Алгоритм Куна. Теорема Кёнига (доказательство на след паре). Потоки ------ Определение потока Определение потока с обратными рёбрами Алгоритм Форда-Фалкерсона Задача про min cut. Слабая двойственность (любой поток <= любой разрез) Доказательство теоремы Форда-Фалкерсона Следствие про max поток = min разрез, алгоритм поиск мин разреза. Алгоритм Эдмондса-Карпа (алгоритм) Алгоритм Эдмондса-Карпа (расстояния растут) Алгоритм Эдмондса-Карпа (конец оценки на время работы, на следующей паре). На практике: Декомпозиция потока за O(E^2), *за O(VE) На практике: Решение задачи про Supply-Demand (b-поток) Потоки II --------- Алгоритм Диница. Формулировка, корректность. Алгоритм Диница. Реализация за O(V^2E) Mincost потоки. Критерий оптимальности mincost потока размера k. Алгоритм Successive Shortest Paths. Анализ времени работы. Лемма о том что толкание по кратчайшему пути переводит оптимальный поток в оптимальный Следствие о корректности Successive Shortest Paths Сведение mincost k-flow к mincost циркуляции. Алгоритм Клейна поиска циркуляции. *Алгоритм Min Mean Cycle Cancelling (доказательство пропущено). Capacity Scaling (алгоритм). Capacity Scaling (корректность -- получаем минкост поток) Capacity Scaling (время работы -- на следующей паре). Дерево отрезков, RMQ -------------------- разреженные таблицы дерево отрезков Сведение RMQ к lca Решение rmq за O(n), O(1) Дерево отрезков, Бинарные деревья поиска ---------------------------------------- дерево отрезков с массовыми операциями бинарные деревья поиска (наивно без балансировки) декартово дерево (merge, split, add, delete. Но без доказательства глубины) AVL (только добавление) *на практике: удаление в AVL, merge в AVL. Линейное программирование, Взвешенное Пар. соч, Приближенные алгоритмы ---------------------------------------------------------------------- Линейное и целочисленное программирование. Определения. Элиминация Фурье Теория двойственности. Доказательство слабой двойственности. Сильная двойственность (без доказательства). Двойственная нежёсткость. Взвешенное паросочетание Определения приближенных алгоритмов 2-приближение для вершинного покрытия 2-приближение для TSP На практике: доказательство теоремы линейного программирования *На практике: log приближение Set Cover *На практике: k приближение Set Cover если частота элементов <= k *На практике: 1.5-приближение TSP.