Лекция "P"
вторник, 14 апреля, 15:40, каб. 25

Алгоритм сортировки пузырьком имеет сложность O(n²).

• Понятие длины входных и выходных данных алгоритма.
• Понятие сложности алгоритма.
• Символы O, W.
• Класс P-алгоритмов, время работы которых не превосходит полинома от длины входных данных.
• Будет описано преимущество алгоритмов из этого класса перед остальными алгоритмами.

Лекция "NP"
вторник, 21 апреля, 15:40, каб. 25

Число (232 + 1) является составным, так как оно делится на 641.

• Понятие свидетелей решения - "подсказок", с помощью которых можно значительно ускорить время решения задачи.
• Класс NP-задач, в которых с помощью "подсказок" можно решить задачу за время, не превосходящее полинома от длины входных данных (т.е. "проверить ответ" за полиномиальное время).
• Неразрешенная проблема равенства классов P и NP.
• Последствия решения проблемы как в случае P != NP, так и в случае P = NP.

Лекция "NPC"
вторник, 28 апреля, 15:40, каб. 25

Если какую-то НП-полную задачу можно решить за полиномиальное время, то любую задачу из класса НП также можно решить за полиномиальное время.

• Понятие полиномиальной сводимости задач.
• Класс NPС (NP-полные) - задачи, к которым можно свести любую задачу из класса NP.
• Примеры NP-полных задач (задача о выполнимости булевых формул, задача коммивояжера, задача нахождения кратчайшего пути в игре "15", задачи возникшие из игр "сапер", "тетрис").

Также на лекциях будет кратко рассказано про:

• Приближенные алгоритмы
• Вероятностные алгоритмы