«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию. Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.
Предисловие 5
Глава 1. Золотой билет 9
Задача о разбиении 12
Немного о руках 13
P против NP 15
В поисках билета 17
Долгая дорога 17
Решение задачи о разбиении 19
Глава 2. Совершенный мир 21
Урбанский алгоритм 21
Компьютеры – рак – 1 : 0 25
Пост-урбанский бейсбол 26
Бритва Оккама 31
Автоматизация творческого процесса 36
Первоклассный детектив 38
Обратная сторона медали 40
С небес на землю 41
Глава 3. Классы P и NP 43
Заклятые друзья 43
Шесть степеней отчуждения 44
Задача о числе паросочетаний 48
В поисках клики 52
Передай скипетр 53
Раскраска домов 58
На первый-второй рассчитайсь! 60
P против NP 62
За границей королевства 64
Биология 64
Физика 65
Экономика 66
Математика 67
Решение головоломки «Путешествие по додекаэдру» 68
Глава 4. Самые трудные задачи класса NP 69
Первая NP-полная задача 69
Двадцать плюс одна 74
Что в имени? 77
После Карпа 79
Доминирующее множество 79
Разбиение на треугольники 79
Гигантские судоку 80
Цепочка из почек 85
Мастера конспирации 86
Изоморфизм графов 86
Простые числа. Разложение на множители 88
Линейное программирование 90
Глава 5. Хроника предшествующих событий 93
На Западе 94
Алан Тьюринг 94
Вычислительная сложность 97
Классы P и NP 99
На Востоке 102
Сергей Всеволодович Яблонский 102
Андрей Николаевич Колмогоров 104
Леонид Анатольевич Левин 108
Письмо Гёделя 111
Правило марсианина 112
Глава 6. Преодолевая трудности 114
Полный перебор 115
Эвристические методы 117
Иголка в стоге сена 124
Приближенные методы 127
Другая задача 133
Время смириться 136
Весь боевой арсенал 137
Глава 7. Как доказать, что P ? NP 138
Парадокс лжеца 140
Схемы 143
Как не доказать, что P ? NP 149
Текущее положение дел 153
Глава 8. Совершенно секретно 155
Очень краткая история классической криптографии 155
Современная криптография 158
Криптография в совершенном мире 162
Судоку с нулевым разглашением 164
Криптография в играх 170
Облако секретных вычислений 173
В поисках случайности 174
Проблемы разрастаются 176
Глава 9. Его величество квант 178
Квантовый видеорекордер 178
Квантовая криптография 184
Квантовая телепортация 186
Квантовое будущее 191
Глава 10. Будущее вычислений 193
Параллельные вычисления 194
Большие данные 196
Интернет вещей 198
На пути научно-технического прогресса 200
И снова про P и NP 201
Благодарности 203
Примечания и список литературы 205
Предметный указатель 213
Название: Золотой билет. P, NP и границы возможного
Автор: Лэнс Фортноу
Язык: Русский
Издательство: Лаборатория знаний
Жанр: Научно-популярная литература
Год выхода: 2016
Формат: pdf
Страниц: 250
Размер: 21.1 Мб
Скачать Лэнс Фортноу - Золотой билет. P, NP и границы возможного
