Просмотр исходного текста страницы Lectures.htm

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

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