Сложность алгоритмов

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор Алексеев Валерий Борисович.

Программа курса

Примеры задач с оценкой временной сложности по порядку.

Сложность распознавания симметрии на машине Тьюринга. Сложность распознавания полноты системы булевых функций на машине Тьюринга.

Некоторые общие результаты о сложности алгоритмов.

Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду. Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

Метод динамического пpогpаммиpования.

Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

Метод "pазделяй и властвуй" для построения быстрых алгоритмов.

Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

Метод pасшиpения модели для построения быстрых алгоритмов.

Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам. Верхние оценки сложности распознавания полноты в множестве булевых и частичных булевых функций.

Некоторые классы сложности.

Определение классов DLOG, NLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач.

Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.

Лектор: В.Б. Алексеев, осень 2014 года.

В билете 2 вопроса – один из части А и один из части В.

Часть А – ответ без подготовки, но по любым материалам (конспекты, книжки и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки утверждений – без конспектов.

1. Метод «разделяй и властвуй». Теорема о скорости роста функции, заданной рекуррентным неравенством.
2. Алгоритм Тоома для умножения чисел.
3. Алгоритм Штрассена для умножения матриц.
4. Алгоритмы обычного и булевского умножения матриц с битовыми операциями.
5. Сложность распознавания принадлежности функции, заданной векторно, классам, определяемым двухместными предикатами.
6. Сложность распознавания принадлежности булевой функции, заданной векторно, классу FmU(Rm).
7. Вычислимые функции, их нумерация. Теоремы о существовании трудно вычислимой общерекурсивной функции.
8. Теорема Барздиня о распознавании симметрии.
9. Теорема о совпадении классов регулярных языков и языков, распознаваемых автоматами.
10. Теорема о регулярности языка, распознаваемого со следом константной длины.
11. Теорема о регулярности языка, распознаваемого со слаборастущими длиной следа или временем.
12. Теорема об NP-полноте языка ГАМИЛЬТОНОВ ЦИКЛ.
13. Жадный алгоритм для задачи о кратчайшем остовном дереве.
14. Задача коммивояжера, ее NP-трудность, теоремы о приближенных алгоритмах для нее.
15. Теорема о PSPACE-полноте задачи о квантифицированных булевских формулах.
16. Теорема об иерархии по памяти. Несовпадение классов DLOG и PSPACE.

Часть В – ответ без конспектов и почти без подготовки (с доказательствами).

17. Сложность алгоритма бинарного поиска в упорядоченном массиве.
18. Нижние оценки сложности поиска в упорядоченном массиве.
19. Нижняя оценка сложности сортировки. Сложность алгоритма сортировки вставкой.
20. Сложность алгоритма сортировки слиянием.
21. Алгоритм динамического программирования для задачи об оптимальном порядке умножения матриц.
22. Алгоритм динамического программирования для поиска кратчайших путей между всеми парами вершин в графе.
23. Алгоритм Карацубы для умножения чисел.
24. Алгоритм транзитивного замыкания графа.
25. Верхние оценки сложности распознавания принадлежности булевой функции, заданной векторно, предполным классам Поста T0, T1, S, L, M.
26. Леммы о максимальной длине и сумме длин различных слов.
27. Классы P и NP. Примеры языков из NP. Замкнутость класса P относительно полиномиального сведения.
28. Теоремы об NP-полноте языков КЛИКА, Независимое Множество Вершин, Вершинное Покрытие.
29. Полиномиальный алгоритм для построения эйлерова цикла.
30. Задача о минимальном вершинном покрытии, ее NP-трудность, жадный и 1-приближенный алгоритмы для нее.
31. Класс PSPACE. Соотношение между классами NP и PSPACE. Верхняя оценка времени работы для задач из PSPACE.
32. Теорема о принадлежности задачи о квантифицированных булевских формулах классу PSPACE.
33. Класс DLOG. Соотношение между классами DLOG и P.

Литература

1. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отдел ф-та ВМиК МГУ, 2002.
2. Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
3. Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
4. Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
6. Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.