Алгоритмы и теория сложности: Учебное пособие

1. ДЕТЕРМИНИРОВАННАЯ МАШИНА ТЬЮРИНГА. ТЕЗИС ТЬЮРИНГА 1.1. Определение алгоритма 1.2. ДМТ и Тезис Тьюринга 1.2.1. ДМТ как структурная схема или «белый ящик» 1.2.2. Тезис Тьюринга 1.2.3. ДМТ как «чёрный ящик» 1.3. Функции, правильно вычислимые по Тьюрингу 1.3.1. Числовые функции 1.4. Операции над машинами Тьюринга 1.5. Универсальная машина Тьюринга (U-машина) 1.6. Алгоритмически неразрешимые проблемы. Проблема остановки машины Тьюринга 1.6.1. Проблема остановки машины Тьюринга Задания для самостоятельной работы Задание 1 (пороговый уровень) Задание 2 (средний уровень) Задание 3 (высокий уровень) Контрольные вопросы 2. НЕДЕТЕРМИНИРОВАННАЯ МАШИНА ТЬЮРИНГА. КЛАСС NP 2.1. Классификация задач по степени сложности 2.1.1. Вычислительная сложность алгоритма 2.1.2. Три класса задач 2.2. Класс P детерминированных полиномиальных алгоритмов 2.3. Класс NP недетерминированных полиномиальных алгоритмов 2.3.1. Недетерминированная полиномиальная машина Тьюринга (НДМТ) 2.3.2. Недетерминированная машина Тьюринга, модель «Черный ящик» 2.4. Взаимоотношения между классами P и NP 2.4.1. Задачи, дополнительные к NP 2.4.2. Взаимоотношения между классами P и NP Задания для самостоятельной работы Задание 1 (пороговый уровень) Задание 2 (средний уровень) Задание 3 (высокий уровень) Контрольные вопросы 3. САМЫЕ ТРУДНЫЕ ЗАДАЧИ ИЗ КЛАССА NP 3.1. Полиномиальная сводимость 3.2. NP-трудные и NP-полные задачи 3.3. Доказательство результатов о NP-полноте 3.3.1. Метод сужения 3.4. Применение теории NP-полноты для анализа подзадач 3.5. Псевдополиномиальные алгоритмы. NP-полнота в сильном смысле 3.5.1. Разумные схемы кодирования 3.5.2. Псевдополиномиальные алгоритмы 3.5.3. NP-полнота в сильном смысле. Доказательство результатов о сильной NP-полноте 3.6. Решение псевдополиномиальных задач методами динамического программирования. Задача «СУММА РАЗМЕРОВ» 3.7. Решение псевдополиномиальных задач методами динамического программирования. Задача РЮКЗАК 3.8. Общие принципы ДП. Принцип оптимальности Беллмана в задаче динамического программирования Задания для самостоятельной работы Задание 1 (пороговый уровень) Задание 2 (средний уровень) Задание 3 (высокий уровень) Контрольные вопросы 4. ПЕРЕБОРНЫЕ МЕТОДЫ РЕШЕНИЯ NP-ПОЛНЫХ ЗАДАЧ. АЛГОРИТМЫ С ВОЗВРАТОМ 4.1. Общая схема алгоритма с возвратом 4.2. Алгоритм с возвратом для задач на минимум. Задача коммивояжера 4.3. Алгоритм с возвратом для задач на максимум. Принцип включения-невключения 4.4. Отсечение повторяющихся решений. Генерация решений в лексикографическом порядке Задания для самостоятельной работы Задание 1 (пороговый уровень) Задание 2 (средний уровень) Задание 3 (высокий уровень) Контрольные вопросы 5. ПРИБЛИЖЁННЫЕ МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ 5.1. Задача об упаковке в контейнеры. Точный алгоритм 5.2. Приближённые алгоритмы. Основные обозначения 5.3. Задача об упаковке в контейнеры. FF-алгоритм 5.4. Абсолютная и относительная погрешности приближённого алгоритма. Оценки сверху 5.5. Нижняя оценка относительной погрешности FF-алгоритма 5.6. FFD-алгоритм. Оценка погрешности FFD-алгоритма Задания для самостоятельной работы Задание 1 (пороговый уровень) Задание 2 (средний уровень) Задание 3 (высокий уровень) Контрольные вопросы БИБЛИОГРАФИЧЕСКИЙ СПИСОК