Дела на миллион: математические «Задачи тысячелетия» простым языком

1.

ГБПОУ КК «СКПО»
Дела на миллион:
математические
«Задачи тысячелетия»
простым языком
Петрова Полина 22НК

2.

Алгоритмически
неразрешимая задача
- это задача, для которой невозможно
построить алгоритм решения.

3.

Задачи тысячелетия — семь
математических проблем, определённых
Математическим институтом Клэя в 2000 году как
«важные классические задачи, решение которых
не найдено вот уже в течение многих лет», за
решение каждой из которых обещано
вознаграждение в 1 млн долларов США.
Существует историческая параллель между
задачами тысячелетия и списком проблем
Гильберта 1900 года, оказавшим существенное
влияние на развитие математики в XX веке; из 23
проблем Гильберта большинство уже решены, и
только одна — гипотеза Римана — вошла в список
задач тысячелетия.

4.

В 1900 г. на Международном математическом
конгрессе в Париже немецкий математик
Д.Гильберт сформулировал 23
математические проблемы.
Сегодня решение (даже
частичное) какой-либо проблемы
Гильберта расценивается как
высшее математическое
достижение,

5.

10-ая проблема Гильберта
Задано произвольное алгебраическое уравнение с
целыми коэффициентами P(x1,x2,…,xn)=0
(Например, ax12+bx22+cx33=0).
Требуется выяснить,
существует ли у данного
уравнения решение в целых
числах.

6.

В 1970 г. математик
Ю.В.Матиясевич (СССР) доказал
невозможность
построения
алгоритма
решения этой задачи.

7.

Равенство классов P и NP
Область: теория алгоритмов
Предположено в начале 1970-х, остается
нерешенным
Представьте, что вам надо закупить офисной техники, мебели и канцтоваров на 500 тыс.
рублей – и вы просматриваете прайс-лист поставщика. Вы можете выбрать, что хотите,
но в списке обязательно должны быть два принтера, одно кресло руководителя, 50
шариковых ручек, остальное по желанию. Сколько комбинаций возможно? Это вариант
«задачи о ранце», которая в классическом виде состоит в том, чтобы уложить в объем
рюкзака как можно больше вещей определенного объема и стоимости. Проверить
конечный вариант легко, но найти его сложно. К этим задачам, кстати, относится и
«вскрытие» чужого пароля, который шифруется таким образом, что система может легко
проверить его корректность, но взломщику практически невозможно вычислить
правильный вариант в море альтернативных решений зашифрованной строки.

8.

Равенство
классов P и NP
Такие проблемы в теории алгоритмов относятся
классу сложности NP: их решение можно быстро
проверить. Часть из них входят в класс P – те,
решение которых еще и легко находится (за
«обозримое», или, строже говоря, полиномиальное
время). Вопрос состоит в том, всегда ли существуют
простые алгоритмы решения NP-задач – то есть,
равны ли классы NP и Р. Сегодня предполагается,
что ответ на него будет отрицательным: далеко не
все задачи, решения которых легко проверяемы,
могут быть легко решаемы. Математик из NASA
Субит Чакрабарти прогнозирует, что окончательный
ответ может быть получен в течение ближайших 50
лет.

9.

Какое
вознаграждение
предполагает
решение «задачи
тысячелетия»?
Математический институт
Клэя обещает
вознаграждение в 1 млн
долларов США за решение
каждой из «задач
тысячелетия»

10.

СПАСИБО ЗА ВНИМАНИЕ!