Крупский В.Н. - Введение в сложность вычислений

Автор(ы)

Методы современной математики

Год

2006

Язык

rus

ISBN

5-88688-083-6

Теги

Математика Программирование

Аннотация

Введение в сложность вычислений Год издания : 2006 Автор : Крупский В.Н. Жанр или тематика : Учебное пособие Издательство : M.: Факториал Пресс ISBN : 5-88688-083-6 Серия : Методы современной математики; Вып. 2 Язык : Русский Формат : PDF/DjVu Качество : Отсканированные страницы + слой распознанного текста Интерактивное оглавление : Да Количество страниц : 128 Тираж : 1000 экз. Описание : Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете МГУ им. М.В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности «Защита информации». Излагаются основные идеи и методы теории сложности вычислений. Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов. Примеры страниц Оглавление Оглавление 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.