Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М.В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности «Защита информации». Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.
Author(s): Крупский В.Н.
Series: Методы современной математики
Publisher: Факториал Пресс
Year: 2006
Language: Russian
Tags: Информатика и вычислительная техника;Теория алгоритмов;
Оглавление 6
Часть I. Модели вычислений 8
Глава 1. Машины Тьюринга 9
§1. Неформальное введение 9
§2. Модели Тьюринга 11
§3. Многоленточные машины Тьюринга 14
Глава 2. Время и память 19
§1. Время и зона машины Тьюринга 19
§2. Цена сокращения алфавита 21
§3. Цена сокращения количества лент 24
Глава 3. Универсальные машины Тьюринга 29
§1. MT, универсальная для класса С 29
§2. Конструкция универсальной машины 30
§3. Теоремы об иерархии 33
Глава 4. Моделирование других языков 37
§1. Схема моделирования других языков программирования машинами Тьюринга 37
§2. Моделирование RAM 38
§3. Моделирование булевых схем 41
Часть II. Сложностные классы 44
Глава 5. Класс Р 45
§1. Определение класса Р 45
§2. Примеры: целочисленная арифметика 47
§3. Примеры: арифметика остатков 48
§4. Примеры: сложение и умножение матриц 50
§5. Примеры: связность в графе 52
Глава 6. Класс P/Poly 53
§1. Распознавание языков последовательностями булевых схем 53
§2. Континуальность класса P/Poly 54
§3. Включение Р ⊂ P/Poly 55
Глава 7. Класс NP 59
§1. Определение класса NP 59
§2. О проблеме Р ≠ NP 62
§3. Примеры задач класса NP 63
Глава 8. Примеры NP-полных задач 67
§1. Сводимость ⩽ (Карп), NP-полнота 67
§2. NP-полнота задачи SAT 69
§3. NP-полнота задачи о клике 71
§4. NP-трудность целочисленного ЛП 72
Глава 9. Класс BPP 75
§1. Вероятностные вычисления за полиномиальное время 75
§2. Частотные распознаватели 76
§3. Включение BPP ⊂ P/Poly 79
Глава 10. Вероятностный алгоритм распознавания простых чисел 83
§1. Сведения из теории чисел 83
§2. Извлечение корней 84
§3. Вероятностный алгоритм 84
§4. Верификация алгоритма 85
§5. Оценка сложности 88
Глава 11. Конечные игры и класс РН 91
§1. Конечные игры 91
§2. Определение класса РН 92
§3. Замкнутость относительно ∩, ∪ и (·)ᶜ 96
Глава 12. Полиномиальная иерархия 99
§1. Классы полиномиальной иерархии 99
§2. Структурные свойства полиномиальной иерархии 101
§3. Пример 101
§4. Включение ВРР ⊂ Σᵖ₂∩Πᵖ₂ 104
Глава 13. Класс PSPACE 109
§1. Класс PSPACE и игры с полиномиальным числом ходов 109
§2. Моделирование игры 110
§3. Моделирование на полиномиальной памяти 111
§4. Игровая характеризация класса PSPACE 113
Глава 14. Полные задачи для класса PSPACE и классов полиномиальной иерархии 117
§1. Квантифицированные булевы формулы 117
§2. Полные задачи для классов полиномиальной иерархии 119
§3. Пример PSPACE-полной задачи 121
Список литературы 125
Предметный указатель 127
