Выбрать книгу по жанру
Фантастика и фэнтези
- Боевая фантастика
- Героическая фантастика
- Городское фэнтези
- Готический роман
- Детективная фантастика
- Ироническая фантастика
- Ироническое фэнтези
- Историческое фэнтези
- Киберпанк
- Космическая фантастика
- Космоопера
- ЛитРПГ
- Мистика
- Научная фантастика
- Ненаучная фантастика
- Попаданцы
- Постапокалипсис
- Сказочная фантастика
- Социально-философская фантастика
- Стимпанк
- Технофэнтези
- Ужасы и мистика
- Фантастика: прочее
- Фэнтези
- Эпическая фантастика
- Юмористическая фантастика
- Юмористическое фэнтези
- Альтернативная история
Детективы и триллеры
- Боевики
- Дамский детективный роман
- Иронические детективы
- Исторические детективы
- Классические детективы
- Криминальные детективы
- Крутой детектив
- Маньяки
- Медицинский триллер
- Политические детективы
- Полицейские детективы
- Прочие Детективы
- Триллеры
- Шпионские детективы
Проза
- Афоризмы
- Военная проза
- Историческая проза
- Классическая проза
- Контркультура
- Магический реализм
- Новелла
- Повесть
- Проза прочее
- Рассказ
- Роман
- Русская классическая проза
- Семейный роман/Семейная сага
- Сентиментальная проза
- Советская классическая проза
- Современная проза
- Эпистолярная проза
- Эссе, очерк, этюд, набросок
- Феерия
Любовные романы
- Исторические любовные романы
- Короткие любовные романы
- Любовно-фантастические романы
- Остросюжетные любовные романы
- Порно
- Прочие любовные романы
- Слеш
- Современные любовные романы
- Эротика
- Фемслеш
Приключения
- Вестерны
- Исторические приключения
- Морские приключения
- Приключения про индейцев
- Природа и животные
- Прочие приключения
- Путешествия и география
Детские
- Детская образовательная литература
- Детская проза
- Детская фантастика
- Детские остросюжетные
- Детские приключения
- Детские стихи
- Детский фольклор
- Книга-игра
- Прочая детская литература
- Сказки
Поэзия и драматургия
- Басни
- Верлибры
- Визуальная поэзия
- В стихах
- Драматургия
- Лирика
- Палиндромы
- Песенная поэзия
- Поэзия
- Экспериментальная поэзия
- Эпическая поэзия
Старинная литература
- Античная литература
- Древневосточная литература
- Древнерусская литература
- Европейская старинная литература
- Мифы. Легенды. Эпос
- Прочая старинная литература
Научно-образовательная
- Альтернативная медицина
- Астрономия и космос
- Биология
- Биофизика
- Биохимия
- Ботаника
- Ветеринария
- Военная история
- Геология и география
- Государство и право
- Детская психология
- Зоология
- Иностранные языки
- История
- Культурология
- Литературоведение
- Математика
- Медицина
- Обществознание
- Органическая химия
- Педагогика
- Политика
- Прочая научная литература
- Психология
- Психотерапия и консультирование
- Религиоведение
- Рефераты
- Секс и семейная психология
- Технические науки
- Учебники
- Физика
- Физическая химия
- Философия
- Химия
- Шпаргалки
- Экология
- Юриспруденция
- Языкознание
- Аналитическая химия
Компьютеры и интернет
- Базы данных
- Интернет
- Компьютерное «железо»
- ОС и сети
- Программирование
- Программное обеспечение
- Прочая компьютерная литература
Справочная литература
Документальная литература
- Биографии и мемуары
- Военная документалистика
- Искусство и Дизайн
- Критика
- Научпоп
- Прочая документальная литература
- Публицистика
Религия и духовность
- Астрология
- Индуизм
- Православие
- Протестантизм
- Прочая религиозная литература
- Религия
- Самосовершенствование
- Христианство
- Эзотерика
- Язычество
- Хиромантия
Юмор
Дом и семья
- Домашние животные
- Здоровье и красота
- Кулинария
- Прочее домоводство
- Развлечения
- Сад и огород
- Сделай сам
- Спорт
- Хобби и ремесла
- Эротика и секс
Деловая литература
- Банковское дело
- Внешнеэкономическая деятельность
- Деловая литература
- Делопроизводство
- Корпоративная культура
- Личные финансы
- Малый бизнес
- Маркетинг, PR, реклама
- О бизнесе популярно
- Поиск работы, карьера
- Торговля
- Управление, подбор персонала
- Ценные бумаги, инвестиции
- Экономика
Жанр не определен
Техника
Прочее
Драматургия
Фольклор
Военное дело
Мир математики. т.3. Простые числа. Долгая дорога к бесконечности - Грасиан Энрике - Страница 26
* * *
МАКСИМАЛЬНАЯ БЕЗОПАСНОСТЬ
Правительство США на своей территории и в Канаде допускает использование лишь определенных криптографических кодов. Также существует запрет на их продажу за пределами этих стран. Несанкционированный экспорт стандартов шифрования приравнивается к торговле оружием. Компании, производящие программы шифрования, хранят секретные коды в планшетах, оснащенных сложными устройствами безопасности. При взломе их содержимое превращается в бесформенную массу из-за контакта с кислородом. При попытке просканировать планшеты с помощью, например, рентгеновских лучей их содержимое преобразуется в нули.
* * *
Некоторые вычислительные задачи не могут быть решены с помощью детерминированного подхода — другими словами, с помощью процессов, выдающих уникальный и предполагаемый результат. Именно такими являются полиномиальные алгоритмы, работающие за полиномиальное время и выполняющие, например, операции сложения, умножения или решения систем уравнений. В большинстве случаев при использовании подходящих алгоритмов решение может быть найдено за разумное время. Задачи, которые могут быть решены таким образом, называются задачами класса сложности Р. С другой стороны, задачи класса сложности NP, для которых используются недетерминированные алгоритмы, решаются несколькими разными способами без гарантии получения одинакового результата.
Время, необходимое для решения такого рода проблем, намного больше чем для задач класса Р. Ясно, что любая проблема, которая допускает детерминированное решение за полиномиальное время, может быть также решена способом быстрой проверки. Другими словами, любая задача класса Р является также задачей класса NP. Однако на этом этапе нам следует уточнить понятие алгоритма.
Алгоритм можно сравнить с кулинарным рецептом. Он состоит из последовательности кристально ясных инструкций. Например, чтобы решить уравнение вида х — 2 = 8, можно использовать следующий алгоритм.
1. Отделить х (перенеся все члены, не содержащие х, в правую часть).
2. Выполнить сложение в правой части: 8 + 2 = 10.
3. Записать решение: х = 10.
Это задача класса Р, которую можно решить за полиномиальное время: она
очень проста и быстро решается.
Конечно, мы могли бы просто подставить значение, например х = 3, х = —2 и так далее, и времени на вычисления потребовалось бы меньше, так как единственное, что программа должна делать, — это подставлять значение вместо х и проверять равенство. Такой метод не является детерминированным, потому что всегда есть вероятность того, что решение будет неверным. (Мы предполагаем, что у нас есть определенные критерии для выбора диапазона возможных решений, например, условие, что все они должны находиться между 9 и 11.)
Можно поставить и обратный вопрос. Если у нас есть недетерминированный алгоритм, например, подстановки и проверки, можно ли гарантировать, что существует полиномиальный алгоритм, который позволяет решить задачу детерминировано? Другими словами, можем ли мы быть уверены в существовании алгоритма, решающего задачу за полиномиальное время?
Этот вопрос был поставлен независимо друг от друга Стивеном Куком и Леонидом Левиным в 1971 г.: если любая задача класса Р является также задачей класса NP, существуют ли задачи класса NP, которые не являются задачами класса Р?
Этот вопрос считается самой важной проблемой современной информатики и является одной из семи задач тысячелетия, за решение каждой из которых математическим институтом Клэя назначен приз в 1000 000 долларов США.
* * *
СЕМЬ ЗАДАЧ ТЫСЯЧЕЛЕТИЯ
Математический институт Клэя — частная некоммерческая организация, основанная Лэндоном Клэем, мультимиллионером и бизнесменом из Бостона. Цель института заключается в развитии и распространении математических знаний.
25 мая 2000 г. институт опубликовал список задач тысячелетия — наиболее сложных проблем математики XX в., за решение которых в общей сложности будет выплачено семь миллионов долларов. Задачи можно решать по одной; за решение каждой будет выдаваться приз в миллион долларов (это больше, чем Нобелевская премия). Институт не накладывает никаких ограничений на сроки решения и возраст кандидатов. Вот эти семь задач.
1. Равенство классов Р и NP.
2. Гипотеза Римана.
3. Теория Янга-Миллса.
4. Уравнения Навье-Стокса.
5. Гипотеза Бёрча-Свиннертон-Дайера.
6. Гипотеза Ходжа.
7. Гипотеза Пуанкаре.
Учитывая сложность и важность предложенных задач, финансовые консультанты господина Клэя сомневались в том, что Институту когда-нибудь придется выплачивать эти призы. Тем не менее, в 2006 г. российский математик Григорий Перельман к удивлению всего мира решил седьмую задачу, доказав гипотезу Пуанкаре. Однако по личным причинам он отказался от медали Филдса, присужденной ему на 25-м Международном конгрессе математиков в Мадриде. Он также отказался от награды института Клэя.
* * *
Очень часто случается так, что кто-нибудь, не имея специальной математической подготовки, вдруг решает, что он нашел (как правило, в интернете) систему или формулу, с помощью которой можно получить простое число, следующее за некоторым натуральным числом n. Однако следует иметь в виду, что такая новость не останется незамеченной. Тот, кто найдет магическую формулу, сразу попадет на первые страницы всех газет и журналов мира.
Существует много геометрических моделей для поиска простых чисел. Иногда они могут ввести в заблуждение неопытных новичков, так как представлены в виде формул, по которым можно найти все простые числа. Но в действительности эти модели являются не более чем решетом Эратосфена или другим представлением решета с помощью геометрических методов. Хотя некоторые из них действительно гениальны.
Одна из самых интересных моделей была разработана российскими математиками Юрием Матиясевичем (род. в 1947) и Борисом Стечкиным (1920–1995) с использованием параболы (см. ниже). Две ветви параболы разделены горизонтальной осью, на которой отмечена последовательность натуральных чисел. Затем проводятся перпендикуляры к оси в точках, соответствующих квадратам натуральных чисел. Например, в точке +4 проведен перпендикуляр, и точки его пересечения с ветвями параболы обозначены числом 2. Геометрический смысл перпендикуляра состоит в том, что он представляет собой произведение 2 x 2. Аналогично мы проводим другой перпендикуляр в точке 9, представляющий собой произведение 3 x 3, и так далее вдоль оси.
Когда все квадраты чисел на оси будут таким образом представлены точками на параболе, каждая точка на одной ветви параболы соединяется со всеми точками на другой ветви, то есть точка 2 верхней ветви параболы соединяется с точками 2, 3, 4, 5 и так далее на нижней. Каждый из этих отрезков пересечет ось в точке, соответствующей произведению двух соединенных чисел: например, отрезок, соединяющий числа 2 и 3, пересекает ось в точке 6. В конце концов натуральные точки на оси, через которые не проходит ни один из таких отрезков, будут являться простыми числами. Это очень показательный пример геометрического решета.
Алгебраические реализации решета более полезны для разработки быстрых вычислительных алгоритмов. Одной из таких реализаций является решето Аткина, предложенное Артуром Аткиным и Дэниелом Бернштейном. Этот алгоритм позволяет найти все простые числа, меньшие или равные данному натуральному числу.
- Предыдущая
- 26/30
- Следующая