Теория алгоритмов

Последнее изменение: 03/12/2025 07:42:12

1. Введение в теорию алгоритмов, вопросы, изучаемые теорией алгоритмов. Актуальность и современное состояние.

2. Понятие машины Тьюринга. Детерминированные и недетерминированные машины Тьюринга. Эквивалентность машины Тьюринга и компьютера.

3. Кодировка машин Тьюринга. Язык диагонализации. Многоленточные машины Тьюринга. Эквивалентность одноленточных и многоленточных МТ. Многодорожечные машины Тьюринга. Память в состоянии.

4. Стековые машины. Счетчиковые машины. Эквивалентность машины Тьюринга двухсчетчиковой и трехсчетчиковой машинам.

5. Теория вычислимости. Понятие вычислимой функции. Языки, распознаваемые машинами Тьюринга. Алгоритмически-неразрешимая проблема. Рекурсивные и рекурсивно-перечислимые языки. Иерархия классов языков, вычислимых на машинах Тьюринга. Операции над языками, распознаваемые машинами Тьюринга.

6. Рекурсивные функции: простейшие функции, операторы суперпозиции и примитивной рекурсии, примитивно-рекурсивные функции, оператор минимизации. Общерекурсивные и частично-рекурсивные функции. Тезисы Черча и Тьюринга.

7. Универсальный язык МТ. Неразрешимость универсального языка МТ. Свойства рекурсивно-перечислимых языков. Теорема Райса.

8. Понятие машины Минского. Эквивалентность машин Минского и машин Тьюринга.

9. Теория вычислительной сложности. Сложность по времени, сложность по памяти. Псевдополиномиальные алгоритмы. Параметрическая сложность. NP-полный класс проблем. Альтернативные определения класса NP. Равенство P = NP.

10. Полиномиальная сводимость задач. Проблема выполнимости булевой формулы (SAT). Теорема Кука.

11. NP-полнота проблемы существования гамильтонова пути в графе.

12. NP-полнота проблемы 3-раскрашиваемости графа.

13. NP-полнота проблемы независимое множество.

14. NP-полнота проблемы трехмерное сочетание.

Литература по курсу

1. Immerman N. Descriptive complexity. 1999.

2. Papadimitriou C. Computational complexity. 1995.

3. Брагилевский В.Н. Лекции по теории алгоритмов. 2019 г.

4. Верещагин Н.К., Шень А. Вычислимые функции. Лекции по математической логике и теории алгоритмов. 2012.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. 1982.

6. Крупский В.Н., Плиско В.Е. Теория алгоритмов. 2009.

7. Мальцев А. И. Алгоритмы и рекурсивные функции. 1986.

8. Поляков В.И., Скорубский В.И. Основы теории алгоритмов. Учебное пособие по дисциплине «Математическая логика и теория алгоритмов». 2012.

9. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. 1972.

10. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. 2002.