Три дня чтения в подарок
Зарегистрируйтесь и читайте бесплатно

Золотой билет. P, NP и границы возможного

Золотой билет. P, NP и границы возможного
Книга в данный момент недоступна
Оценка читателей

«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.

Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.

В формате pdf A4 сохранен издательский дизайн.

Оглавление
  • Предисловие
  • Золотой билет
  • Задача о разбиении
  • Немного о руках
  • 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
  • Благодарности
  • Примечания и список литературы
  • Примечания