Мир математики, Существуют ли неразрешимые проблемы, математика, сложность и вычисление, том 43, Луис Фернандо Ареан, 2014

Мир математики, Существуют ли неразрешимые проблемы, Математика, сложность и вычисление, Том 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 - Яндекс.Диск.




Теги: учебник по математике :: математика :: Луис Фернандо Ареан :: криптография