Лектор: Александр Сергеевич Куликов
Язык курса: русский
Слайды лекций:
| Название | Слайды | Версия для печати | Видео | Содержание лекции |
|---|---|---|---|---|
| 1. Приближенные алгоритмы. | Приближенные алгоритмы для задач о вершинном покрытии и о покрытии множествами. | |||
| 2. Приближенные алгоритмы. | ч1, ч2, ч3 | Приближенный алгоритм для задачи о кратчайшей надпоследовательности. | ||
| 3. Приближенные алгоритмы. | Приближенный алгоритм для задачи о коммивояжере в метрическом пространстве, полностью полиномиальная приближенная схема для задачи о рюкзаке. | |||
| 4. Задача выполнимости. | ч1, ч2 | Сведения японских кроссвордов, игры Eternity и задачи о максимальном разрезе к задаче выполнимости. | ||
| 5. Алгоритмы для задачи выполнимости. | Расщепляющие алгоритмы (DPLL, PPSZ), случайные блуждания. | |||
| 6. Подходы к решению NP–трудных задач. | Расщепление, случайный порядок перебора, локальный поиск, динамическое программирование, сведение к простой задаче, случайное сведение к простой задаче, умный перебор. | |||
| 7. Задача линейного программирования. | Потоки в сетях, максимальное паросочетания в двудольном графе, двойственность, симплекс–метод. | |||
| 8. Приближенные алгоритмы. | Задача о взвешенном вершинном покрытии, задача о минимальном множестве представителей. | |||
| 9. Вероятностные алгоритмы. | Проверка перемножения матриц, сравнение строк, корни многочлена, эквивалентность ветвящихся программ. | |||
| 10. Вероятностные алгоритмы. | Минимальный разрез, проверка простоты числа. | |||
| 11. Вероятностные алгоритмы. | Поиск расстояний в графе, поиск виновников в умножении булевых матриц, поиск кратчайших путей в графе. | |||
| 12. Online–алгоритмы. | Задача кэширования, задача о покрытии множествами. |
Дополнительно: