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