• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

Читается: 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.