Лэнс Фортноу | Золотой билет. P, NP и границы возможного (2016) [EPUB, FB2, MOBI]

Предисловие
Глава 1. Золотой билет
Задача о разбиении
Немного о руках
P против NP
В поисках билета
Долгая дорога
Решение задачи о разбиении
Глава 2. Совершенный мир
Урбанский алгоритм
Компьютеры – рак – 1: 0
Пост-урбанский бейсбол
Бритва Оккама
Автоматизация творческого процесса
Первоклассный детектив
Обратная сторона медали
С небес на землю
Глава 3. Классы P и NP
Заклятые друзья
Шесть степеней отчуждения
Задача о числе паросочетаний
В поисках клики
Передай скипетр
Раскраска домов
На первый-второй рассчитайсь!
P против NP
За границей королевства
--Биология
--Физика
--Экономика
--Математика
Решение головоломки «Путешествие по додекаэдру»
Глава 4. Самые трудные задачи класса NP
Первая NP-полная задача
Двадцать плюс одна
Что в имени?
После Карпа
--Доминирующее множество
--Разбиение на треугольники
--Гигантские судоку
--Цепочка из почек
Мастера конспирации
--Изоморфизм графов
--Простые числа. Разложение на множители
Линейное программирование
Глава 5. Хроника предшествующих событий
На Западе
--Алан Тьюринг
--Вычислительная сложность
--Классы P и NP
На Востоке
--Сергей Всеволодович Яблонский
--Андрей Николаевич Колмогоров
--Леонид Анатольевич Левин
Письмо Гёделя
Правило марсианина
Глава 6. Преодолевая трудности
Полный перебор
Эвристические методы
Иголка в стоге сена
Приближенные методы
Другая задача
Время смириться
Весь боевой арсенал
Глава 7. Как доказать, что P ≠ NP
Парадокс лжеца
Схемы
Как не доказать, что P ≠ NP
Текущее положение дел
Глава 8. Совершенно секретно
Очень краткая история классической криптографии
Современная криптография
Криптография в совершенном мире
Судоку с нулевым разглашением
Криптография в играх
Облако секретных вычислений
В поисках случайности
Проблемы разрастаются
Глава 9. Его величество квант
Квантовый видеорекордер
Квантовая криптография
Квантовая телепортация
Квантовое будущее
Глава 10. Будущее вычислений
Параллельные вычисления
Большие данные
Интернет вещей
На пути научно-технического прогресса
И снова про P и NP
Благодарности
Примечания и список литературы