StasFomin в 20:55, 25 ноября 2010

2010-11-25T20:55:58Z

Новая страница

== Курс лекций «Сложность комбинаторных алгоритмов». ==

[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/ Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.

Lectures.htm - История изменений

StasFomin в 20:55, 25 ноября 2010