Сибилева Н.С., Файнштейн А.С., Файнштейн С.И. Алгоритмы и теория сложности

Учебное пособие. — Магнитогорск: Магнитогорский государственный технический университет им. Г.И. Носова, 2021. — 93 с. — ISBN 978-5-9967-2115-3.Содержит следующие разделы: детерминированная машина Тьюринга. Тезис Тьюринга; недетерминированная машина Тьюринга. Класс NP; самые трудные задачи из класса NP; переборные методы решения NP-полных задач. Алгоритмы с возвратом; приближённые методы решения оптимизационных задач. Для закрепления теоретического материала в каждом разделе приведены практические задания различного уровня сложности: порогового, среднего и высокого, а также контрольные вопросы.
Предназначено для студентов, обучающихся по направлению подготовки 09.03.01 «Информатика и вычислительная техника» при изучении дисциплин «Алгоритмы и теория сложности», «Алгоритмы на сетях и графах», «Структуры и модели данных», «Точные и эвристические алгоритмы».Детерминированная машина Тьюринга. Тезис тьюринга.
Определение алгоритма.
ДМТ и Тезис Тьюринга.
ДМТ как структурная схема или «белый ящик».
Тезис Тьюринга.
ДМТ как «чёрный ящик».
Функции, правильно вычислимые по Тьюрингу.
Числовые функции.
Операции над машинами Тьюринга.
Универсальная машина Тьюринга (U-машина).
Алгоритмически неразрешимые проблемы. Проблема остановки машины Тьюринга.
Проблема остановки машины Тьюринга.
Задания для самостоятельной работы (пороговый, средний, высокий уровни).
Контрольные вопросы.
Недетерминированная машина Тьюринга. Класс NP.
Классификация задач по степени сложности.
Вычислительная сложность алгоритма.
Три класса задач.
Класс P детерминированных полиномиальных алгоритмов.
Класс NP недетерминированных полиномиальных алгоритмов.
Недетерминированная полиномиальная машина Тьюринга (НДМТ).
Недетерминированная машина Тьюринга, модель «Черный ящик».
Временная сложность недетерминированной машины Тьюринга.
Взаимоотношения между классами P и NP.
Задачи, дополнительные к NP.
Взаимоотношения между классами P и NP.
Задания для самостоятельной работы (пороговый, средний, высокий уровни).
Контрольные вопросы.
Самые трудные задачи из класса NP.
Полиномиальная сводимость.
NP-трудные и NP-полные задачи.
Доказательство результатов о NP-полноте.
Метод сужения.
Применение теории NP-полноты для анализа подзадач.
Псевдополиномиальные алгоритмы. NP-полнота в сильном смысле.
Разумные схемы кодирования.
Псевдополиномиальные алгоритмы.
NP-полнота в сильном смысле. Доказательство результатов о сильной NP-полноте.
Решение псевдополиномиальных задач методами динамического программирования. Задача «СУММА РАЗМЕРОВ».
Решение псевдополиномиальных задач методами динамического программирования. Задача РЮКЗАК.
Общие принципы ДП. Принцип оптимальности Беллмана в задаче динамического программирования.
Задания для самостоятельной работы (пороговый, средний, высокий уровни).
Контрольные вопросы.
Переборные методы решения NP-полных задач. Алгоритмы с возвратом.
Общая схема алгоритма с возвратом.
Алгоритм с возвратом для задач на минимум. Задача коммивояжера.
Алгоритм с возвратом для задач на максимум. Принцип включения-невключения.
Отсечение повторяющихся решений. Генерация решений в лексикографическом порядке.
Задания для самостоятельной работы (пороговый, средний, высокий уровни).
Контрольные вопросы.
Приближённые методы решения оптимизационных задач.
Задача об упаковке в контейнеры. Точный алгоритм.
Приближённые алгоритмы. Основные обозначения.
Задача об упаковке в контейнеры. FF-алгоритм.
Абсолютная и относительная погрешности приближённого алгоритма. Оценки сверху.
Нижняя оценка относительной погрешности FF-алгоритма.
FFD-алгоритм. Оценка погрешности FFD-алгоритма.
Задания для самостоятельной работы (пороговый, средний, высокий уровни).
Контрольные вопросы.
Библиографический список.