Цель и задачи курса: познакомить студентов с основными подходами и методами решения вычислительно сложных (NP-сложных и NP-трудных) задач. В результате освоения материалов курса студенты смогут проводить обоснованный анализ различных подходов к решению конкретной задачи, выбирать наиболее подходящий метод решения и эффективно реализовывать выбранный метод в виде программы.
От слушателей курса требуются знания в области теории сложности алгоритмов, методов построения эффективных алгоритмов, а также базовые знания численных методов и дискретной математики.
Курс включает в себя следующие разделы:
-
Переборные методы решения (метод "грубой силы", метод ветвей и границ).
-
Параметризованные алгоритмы.
-
Приближённые алгоритмы с оценкой точности.
-
Вероятностные и эвристические алгоритмы.