Мир математики, Существуют ли неразрешимые проблемы, Математика, сложность и вычисление, Том 43, Луис Фернандо Ареан, 2014.
Как измерить сложность проблемы? Существуют ли простые решения сложных проблем? Эти и подобные вопросы лежат в основе теории сложности вычислений. От ответа на них зависят ее очевидные практические применения, такие, например, как криптография. Кроме того, теория проливает свет на глубокие математические и философские проблемы, связанные с интеллектом и познанием.
Выбрать лучший путь: теория алгоритмов.
К югу от Аргоса находится озеро Лерна, где, согласно мифу, Геракл выполнил второе из заданий, данных ему царем Еврисфеем: убить Гидру — змею с ядовитым дыханием и многочисленными головами, которую Гера послала, чтобы покончить с героем. Вначале Геракл пытался отсекать ей головы одну за другой, но, к его удивлению, каждый раз, когда он отсекал голову, на ее месте сразу же вырастало еще три. Было ясно, что таким образом задачу не решить, поскольку она постоянно усложняется. Итак, Геракл был первым человеком, который столкнулся с экспоненциальным ростом.
Если изначально у Гидры было три головы (не будем брать в расчет четвертую голову, которая была бессмертна), на следующем этапе (n = 1) у нас будет 9 голов; после восьмого этапа (n = 8) — 19683, а после семнадцатого — почти 40 миллионов.
Содержание.
Предисловие.
Глава 1. Как решить загадку.
Краткая история криптографии до Второй мировой войны.
Машина «Энигма» и польский криптоанализ.
Алан Тьюринг и Блетчли-парк.
Глава 2. «Это невычислимо, доктор Тьюринг»: введение в теорию автоматов.
Машины Тьюринга и вычислимость.
Вычислимость, проблема остановки и проблема разрешения (Entscheidungsproblem).
Глава 3. Выбрать лучший путь: теория алгоритмов.
Дети, постройтесь по росту.
Следуя по маршрутам: алгоритмы и теория графов.
Классы сложности.
Глава 4. Проблема коммивояжера: отношение p и Np.
Отношение p и Np и полнота Np.
Следствия из p = Np.
Другие классы сложности: ЕХp и NEXp.
Время и пространство.
Глава 5. Взбираясь на восьмитысячник: попытки доказать, что p = Np.
Техника диагонализации.
Булевы цепи и нижние границы.
Другие пути: произвольность, интерактивные доказательства, арифметизация.
Глава 6. Последняя граница?.
Средняя сложность, эвристики и pNp.
Квантовое вычисление и реальное вычисление.
Выводы.
Будущее.
Библиография.
Алфавитный указатель.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Мир математики, Существуют ли неразрешимые проблемы, математика, сложность и вычисление, том 43, Луис Фернандо Ареан, 2014 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - djvu - Яндекс.Диск.
Дата публикации:
Теги: учебник по математике :: математика :: Луис Фернандо Ареан :: криптография
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Мир математики, Специальный выпуск №2, Хранители времени, 2014
- Мир математики, Специальный выпуск №1, Неуловимое время, 2014
- Мир математики, математика и выборы, Принятие решений, том 45, Висенц Торра, 2014
- Мир математики, Бесконечная мозаика, Замощения и узоры на плоскости, том 44, Микель Альберти, 2014
Предыдущие статьи:
- Мир математики, Путешествие от частицы до Вселенной, математика газовой динамики, том 42, Эдуардо Арройо, 2014
- Мир математики, Шар бесконечного объема, Парадоксы измерения, том 41, Густаво Пиньейро, 2014
- Мир математики, Математическая планета, Путешествие вокруг света, том 40, Микель Альберти, 2014
- Мир математики, Математический клуб, Международные конгрессы, том 39, Гильермо Курбера, 2014