Программа спецкурса

1. Введение. - 2ч.

1.1. Понятие алгоритма. Алгоритмически разрешимые и неразрешимые задачи.

1.2. Сложность алгоритма. Временная и емкостная сложность. Сложность в среднем и сложность в худшем случае. Асимптотические оценки сложности. Символ O(.).

1.3. Сложность задачи. Теорема Блюма об ускорении.

2. Класс DTIME - 6 ч.

2.1. Детерминированная МТ.

2.2. Моделирование МТ (универсальная МТ, моделирование многоленточной МТ с помощью одноленточной).

2.3. Определение класса DTIME. Теорема об иерархии.

3. Класс NTIME - 4 ч.

3.1. Недетерминированная МТ.

3.2. Теорема о моделировании НМТ с помощью ДМТ.

3.3. Два определения класса NTIME: через НМТ и через "сертификаты". Теорема об эквивалентности этих определений.

3.4. Иерархия по временной сложности. P, NP, co-NP.

4. Иерархия по емкостной сложности. - 1 ч.

4.1. Задачи с полиномиально ограниченной памятью (PSPACE).

4.2. Соотношение классов PSPACE, NPSPACE, PTIME, NPTIME.

5. Сводимость и полнота. - 7 ч.

5.1. Типы задач: оптимизационные, вычислительные, распознавательные.

5.2. Распознавание языков. Преобразование задач разных типов к задаче распознавания.

5.3. Сводимость и полнота. NP-полные и NP-трудные задачи. Проблема P =? NP.

5.4. Примеры NP-полных задач и сведения одних NP-полных задач к другим (SAT, 3-SAT, CLIQUE).

6. Вероятностные алгоритмы.- 4 ч.

6.1. Алгоритмы типа "Монте-Карло" (RP, co-RP, BPP).

6.2. Алгоритмы типа "Лас-Вегас" (ZPP).

7. Приложение теории сложности алгоритмов в криптографии. - 10 ч.

7.1. Криптосистемы с открытым ключом. Односторонние функции.

7.2. Псевдослучайные генераторы.

7.3. Интерактивные доказательства.

Вопросы к экзамену или зачету по спецкурсу расположены здесь.

Полезные ссылки

Ниже приведены ссылки на Интернет-ресурсы, которые были использованы при подготовке спецкурса. Загрузка списка ссылок может занять некоторое время. Если Вы так и не увидели ссылки - значит, Ваш браузер почему-то некорректно обрабатывает команды JavaScript :(