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

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

  Как измерить сложность проблемы? Существуют ли простые решения сложных проблем? Эти и подобные вопросы лежат в основе теории сложности вычислений. От ответа на них зависят ее очевидные практические применения, такие, например, как криптография. Кроме того, теория проливает свет на глубокие математические и философские проблемы, связанные с интеллектом и познанием.




Как решить загадку.
Осень 1940 года. Битва за Францию выиграна. Немецкие войска сосредоточились на берегу Ла-Манша, от Кале до Шербура, в ожидании момента, чтобы атаковать с западного берега. Начинается блиц над британскими городами, во время которого, пользуясь численным превосходством, воздушные силы Люфтваффе ведут масштабные бомбардировки. Но несмотря на все разрушения, настоящая война разгорается в тысячах километров от Лондона, в Северной Атлантике. Именно там решается судьба Великобритании. Островное расположение королевства, которое давало огромные преимущества в течение веков, может сыграть отрицательную роль. Поставки боеприпасов происходят в основном из Соединенных Штатов медленным морским путем. Следуя давней стратегии Наполеона, Гитлер решил перерезать снабжение. В отличие от корсиканца, немцы располагают сильной армией, противостоящей Королевскому флоту: торговые суда страдают от беспощадных немецких лодок, которые месяц за месяцем топят сотни тонн грузов. Ситуация становится невыносимой.

Немецкий подводный флот связывается со штабом в Берлине по беспроводному телеграфу. Чтобы эти сигналы не попали в руки врага, используется мощная система шифрования, с которой успешно справляется машина с запоминающимся названием «Энигма». Ее разработчики уверены: шифр «Энигмы» настолько сложен, что не поддается расшифровке. Здесь и начинается наша история: группа блистательных профессоров, сливки британской науки, полны решимости доказать, что вермахт заблуждается.

Содержание.
Предисловие.
Глава 1. Как решить загадку.
Краткая история криптографии до Второй мировой войны.
Машина «Энигма» и польский криптоанализ.
Алан Тьюринг и Блетчли-парк.
Глава 2. «Это невычислимо, доктор Тьюринг»: введение в теорию автоматов.
Машины Тьюринга и вычислимость.
Вычислимость, проблема остановки и проблема разрешения (Entscheidungsproblem).
Глава 3. Выбрать лучший путь: теория алгоритмов.
Дети, постройтесь по росту.
Следуя по маршрутам: алгоритмы и теория графов.
Классы сложности.
Глава 4. Проблема коммивояжера: отношение p и Np.
Отношение p и Np и полнота Np.
Следствия из p = Np.
Другие классы сложности: ЕХp и NEXp.
Время и пространство.
Глава 5. Взбираясь на восьмитысячник: попытки доказать, что p = Np.
Техника диагонализации.
Булевы цепи и нижние границы.
Другие пути: произвольность, интерактивные доказательства, арифметизация.
Глава 6. Последняя граница?.
Средняя сложность, эвристики и pNp.
Квантовое вычисление и реальное вычисление.
Выводы.
Будущее.
Библиография.
Алфавитный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Мир математики, том 43, Существуют ли неразрешимые проблемы, математика, сложность и вычисление, Луис Фернандо Ареан, 2014 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




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