Несложно о сложности. Примеры алгоритмов

Кузюрин Н.Н., Фомин С.А.
- М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 28 слайдов. Содержание:
История алгоритмов.
Теория сложности.
Обозначения.
Тривиальное и разумное вычисления.
Дискретный логарифм.
Наибольший общий делитель.
Алгоритм Евклида.
Задача коммивояжера.
Переборный алгоритм для TSP.
Кратчайшие пути в графе.
Алгоритм Дейкстры.
Трудоемкость алгоритма Дейкстры.
Кратчайшие пути в графе с отрицательными весами.
Алгоритм Флойда-Уоршолла.
Минимальное остовное дерево.
Алгоритм Прима.
«Карта памяти» лекции.