|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2008/courses/pritykin.htm
Дата изменения: Sun Jun 8 22:34:42 2008 Дата индексирования: Sat Sep 6 18:53:12 2008 Кодировка: koi8-r Поисковые слова: п п п п п п п р п р п р п р п р п р п р п р п р п р п р п |
| На главную страницу ЛШСМ-2008 | К списку курсов ЛШСМ-2008 |
Юрий Львович ПритыкинЧто такое проблема P vs. NP ?Ю.Л.Притыкин планирует провести 4 занятия |
|
Проблема «P vs. NP» (равны ли P и NP) является одной из фундаментальных проблем теоретической информатики (theoretical computer science) и математики вообще, что подтверждается и разными внематематическими формальностями (например, это одна из семи «проблем тысячелетия», за решение каждой из которых присуждён приз в 1млн. долларов).
В курсе будет рассказано, в чём заключается формулировка проблемы, а также о разных понятиях и результатах вокруг неё. Никаких особых предварительных знаний не требуется.
Примерная программа курса:
- Неформальные разговоры. Формализация понятия вычисления: машины Тьюринга.
- Задачи, которые быстро решаются, и задачи, в которых можно быстро проверить ответ: классы P и NP.
P vs. NP и другие нерешённые проблемы теории сложности вычислений.- Самые сложные задачи в классе NP: полиномиальная сводимость и NP-полнота.
- Быстрые приближённые решения задач, которые сложно решить точно: вероятностные и приближённые алгоритмы.
