Теория сложности I 65;7000;1c------------------ Модели вычислений: 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). Двудольные паросочетания. Удлиняющая цепочка и лемма о ней Двудольные паросочетания. Алгоритм Куна. Теорема Кёнига (доказательство на след паре). Потоки ------ Определение потока Определение потока с обратными рёбрами Алгоритм Форда-Фалкерсона Задача про 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 (корректность и время работы на следующей паре). Дерево отрезков, RMQ -------------------- разреженные таблицы дерево отрезков Сведение RMQ к lca Решение rmq за O(n), O(1) Дерево отрезков, Бинарные деревья поиска ---------------------------------------- дерево отрезков с массовыми операциями бинарные деревья поиска (наивно без балансировки) декартово дерево (подробно, но без доказательства глубины) AVL (только добавление) на практике: удаление в AVL, merge в AVL.