Главная » 2018»Ноябрь»24 » Лэнс Фортноу - Золотой билет. P, NP и границы возможного
11:53
Лэнс Фортноу - Золотой билет. P, NP и границы возможного
«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь.
«Золотой билет» – великолепное введение в 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
Информация о книге: Автор: Лэнс Фортноу Язык: русский Издательство: Лаборатория знаний Жанр: Научно-популярная литература Год: 2016 Формат: pdf Качество: OCR без ощибок Размер: 21.1 Мб
Скачать Лэнс Фортноу - Золотой билет. P, NP и границы возможного