Lectures.htm
Материал из DISCOPAL
== Курс лекций «Сложность комбинаторных алгоритмов». == [http://docs.google.com/Doc?id=dfxc7f9q_33dpcdhs Доска курса] — самая актуальная информация по курсу: программа, обьявления, контакты и т.п. ---- === Download === ==== Студентам ==== Материалы к курсу — книга [[ru.book-advanced-algorithms.htm|Эффективные алгоритмы и сложность вычислений]] ==== Лекторам ==== Набор лекций в виде слайд-презентаций (гипертекстовые PDF-слайды): # «[[Несложно о сложности. Примеры алгоритмов]]». # «[[lectures/beam/algorithms-definitions.beam.pdf|«Формально об алгоритмах. Вычислительные модели»]]. # [[lectures/beam/algorithms-dtime-dspace.beam.pdf|«Временная и пространственная сложность алгоритмов»]]. # [[lectures/beam/p-reducibility-and-npc.beam.pdf|«Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC»]]. # [[lectures/beam/randomized-complexity.beam.pdf|«Вероятностные вычисления. Классы RP, coRP, ZPP, BPP»]]. # [[lectures/beam/probabilistically-checkable-proofs.beam.pdf|«Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема»]]. # [[lectures/beam/amplifying-reduction-non-approx.beam.pdf|«PCP и аппроксимируемость»]]. # [[lectures/beam/greedy-covering.beam.pdf|«Жадный алгоритм в задачах о покрытии»]]. # [[lectures/beam/greedy-covering-almost-ok.beam.pdf|«Жадный алгоритм покрытия для почти всех исходных данных»]]. # [[lectures/beam/christofides.beam.pdf|«Приближенный алгоритм для метрической задачи коммивояжера»]]. # [[lectures/beam/greedy-knapsack.beam.pdf|«Жадный алгоритм в задаче о рюкзаке»]]. # [[lectures/beam/dynamic-programming-knapsack.beam.pdf|«Динамическое программирование для задачи о рюкзаке»]]. # [[lectures/beam/ptas-knapsack.beam.pdf|«Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке»]]. # [[lectures/beam/packing-average.beam.pdf|«Полиномиальный в среднем алгоритм для задачи упаковки»]]. # [[lectures/beam/average-knapsack.beam.pdf|«Полиномиальный в среднем алгоритм для задачи о рюкзаке»]]. # [[lectures/beam/sat-average.beam.pdf|«Полиномиальный в среднем алгоритм для SAT»]]. # [[lectures/beam/dnf-counting.beam.pdf|«Вероятностный подсчет числа выполняемых наборов для ДНФ»]]. # [[lectures/beam/randomized-rounding.beam.pdf|«MAX-SAT: вероятностное округление»]]. # [[lectures/beam/derandomization-maxsat.beam.pdf|«MAX-SAT: дерандомизация»]]. # [[lectures/beam/derandomization-luby.beam.pdf|«Дерандомизация Люби»]]. # [[lectures/beam/max-cut-semidefinite.beam.pdf|«MAX-CUT: вероятностное округление»]]. # [[lectures/beam/maximal-independent-set.beam.pdf|«Параллельный алгоритм Люби для максимального по включению независимого множества»]]. ---- == Приблизительное содержание курса лекций == Элементы теории сложности 1.1 Примеры алгоритмов 1.1.1 Примеры задач на натуральных числах. 1.1.2 Примеры задач на графах. Кратчайшие пути, остовные деревья и задача коммивояжера. 1.1.3 Приближенные алгоритмы. Многопроцессорные расписания 1.1.4 Сортировка слиянием 1.1.5 Быстрая сортировка. Анализ в среднем и вероятностная версия. 1.2 Формально об алгоритмах 1.2.1 Машины с произвольным доступом к памяти 1.2.2 Машины Тьюринга и вычислимость 1.3 Сложность алгоритмов 1.3.1 Сложность в худшем случае 1.3.2 Полиномиальные алгоритмы 1.3.3 Классы DTIME, DSPACE 1.3.4 Полиномиальные сводимости и NP-полнота 1.3.5 Сводимость по Куку 1.3.6 Недетерминированные алгоритмы 1.3.7 Сводимость по Карпу 1.4 Вероятностные вычисления 1.4.1 Классы RP и coRP. Распознавание с односторонней ошибкой. 1.4.2 Класс BPP. Эффективное распознавание с двухсторонней ошибкой. 1.4.3 Класс PP. 1.4.4 Класс ZPP. Вероятностное распознавание без ошибок. 1.5 Вероятностно проверяемые доказательства 1.5.1 PCP и неаппроксимируемость 1.6 Схемы и схемная сложность 1.7 Диаграмма классов сложности 2 Приближенные алгоритмы с гарантированными оценками точности 2.1 Приближенные алгоритмы с фиксированными оценками точности 2.1.1 Жадный алгоритм в задаче о покрытии 2.1.2 Приближенные алгоритмы для задачи покрытия с минимальной суммой 2.1.3 Жадный алгоритм для задачи о рюкзаке 2.1.4 Алгоритм Кристофидеса для метрической задачи коммивояжера 2.2 Приближенные алгоритмы с выбираемыми оценками точности 2.2.1 Динамическое программирование для задачи о рюкзаке. Псевдополиномиальный алгоритм 2.2.2 Полностью полиномиальная приближенная схема для задачи о рюкзаке 3 Вероятностные алгоритмы и вероятностный анализ. 3.1 Полиномиальные в среднем алгоритмы 3.1.1 Анализ сложности в среднем 3.2 Задача упаковки 3.2.1 Точность жадного алгоритма для почти всех исходных данных 3.3 Полиномиальный в среднем алгоритм для задачи о рюкзаке 3.4 Вероятностные алгоритмы (Лас-Вегас и Монте-Карло). 3.4.1 Алгоритм Фрейвалда и проверка полиномиальных тождеств 3.5 Вероятностное округление и дерандомизация 3.5.1 Вероятностное округление 3.5.2 Дерандомизация и метод условных вероятностей. 4 Приложения 4.1 Глоссарий 4.2 Введение в Python ---- == Полезная сопутствующая литература по курсу. == * Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: [http://www.wisdom.weizmann.ac.il/%7Eoded/cc.html Introduction to Complexity Theory by Oded Goldreich] * Более краткий [http://www.cs.technion.ac.il/%7Ecs236313/ курс по классической теории сложности], университет Technion. * Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.] * ''А. Китаев, А. Шень, М. Вялый'', [http://www.mccme.ru/free-books/ Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.