Вычислимость и сложность

Читается: 3-4 модуль 2 курса 
Пререквизиты: нет
Трудоемкость: 5 кредитов

80 аудиторных часов:

• 40 часов лекций;
• 40 часов семинаров.

Формы контроля:

• экзамен;
• 1 контрольная работа;
• 2 домашних задания.

Преподаватели

Саватеев Юрий Вячеславович

Факультет математики: доцент

 

О курсе

Цели курса: знакомство с основными вычислительными моделями, используемыми в теории вычислений (машины Тьюринга, равнодоступные адресные машины, схемы из функциональных элементов, вероятностные варианты этих моделей), знакомство с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств. В курсе будут обсуждаться примеры неразрешимых проблем и сведение одних проблем к другим. Слушатели научатся быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели, различать различные виды трудности задач (трудность для наихудшего входа и трудность для случайно взятого входа).

Цели курса:

1. Познакомить с основными вычислительными моделями, используемыми в теории вычислений (многоленточные машины Тьюринга, равнодоступные адресные машины, схемы из функциональных элементов, вероятностные варианты этих моделей).
2. Познакомить с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств, нумерации вычислимых функций.
3. Привести примеры неразрешимых проблем и научить сводимости одних проблем к другим.
4. Научить быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели.
5. Научить различать различные виды трудности задач (трудность для наихудшего входа и трудность для случайно взятого входа).
6. Изучить известные методы установления вычислительной трудности задач различного типа (задач вычисления функции, поиска, оптимизации, апроксимации, подсчета, обращения функции): дать представление о том, как устанавливается "эталонных задач", и научить сводить данную задачу к одной из эталонных трудных задач.

Примерное содержание лекций:

1. Вычислительные модели: многоленточные машины Тьюринга, равнодоступные адресные машины. Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов. Тезис Чёрча.
2. Понятие вычислимой функции, разрешимого множества.
3. Перечислимые множества.
4. Перечислимость и разрешимость (теорема Поста, теорема о
5. проекции разрешимого множества).
6. Теорема о графике вычислимой функции.
7. Универсальные вычислимые функции.
8. Нумерации вычислимых функций. Главные универсальные функции.
9. Построение перечислимого неразрешимого множества.
10. Алгоритмически неразрешимые проблемы в теории алгоритмов. Неразрешим ость проблемы тождества в полугруппах.
11. Примеры других алгоритмически неразрешимых проблем в алгебре и теории чисел.
12. m-Сводимость, m-полные перечислимые множества.
13. Машины с оракулом и сводимость по Тьюрингу.
14. Существование неполных перечислимых неразрешимых множеств.
15. Полиномиальная эквивалентность по времени и памяти вычислительных моделей. Класс P функций, вычислимых за полиномиальное время.
16. Сводимость одной задачи к другой. Полные в данном классе задачи. Теорема о иерархии для временной сложности, как метод доказательства вычислительной трудности задач.
17. Доказуемо трудные алгоритмические проблемы: проверка эквивалентности расширенных регулярных выражений, выяснение истинности формул языка первого порядка в аддитивной группе действительных числах.
18. Класс NP. Задачи поиска и класс SearchP. Сведение задач поиска к задачам разрешения из класса NP. Задачи подсчета и класс #P.
19. NP-трудные и NP-полные задачи. Проблема перебора (P=NP?) и предположительная трудность NP-трудных задач.
20. Схемы их функциональных элементов. Теорема Кука-Левина об NP-полноте проблемы выполнимости схем из функциональных элементов.
21. NP-полнота других задач: 3-КНФ, 3-РАСКРАСКА, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ, РЮКЗАК, КОММИВОЯЖЕР, ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.
22. Задачи оптимизации и их сводимость к задачам из NP. Приближенное решение оптимизационных задач. Трудность задачи апроксимации хроматического числа данного графа.

Рекомендуемая литература:

1. Н. Верещагин и А. Шень. Вычислимые функции. МНЦМО, 1999.
2. M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
3. A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.
4. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоримты: построение и анализ. М.: МЦНМО, 2001.