Эффективные алгоритмы

Общая информация
ЛекторА. С. Куликов
Семестросень 2007
Дата начала23.09.2007
Количество пар21
Язык курсарусский
Аннотация Дополнительные главы к курсу базовых алгоритмов.
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Приближённые алгоритмы
(23.09.2007 - 17:55)

Приближенные алгоритмы для задач о вершинном покрытии и о покрытии множествами.
2. Приближённые алгоритмы
(30.09.2007 - 17:30)

Приближенный алгоритм для задачи о кратчайшей надпоследовательности.
3. Приближённые алгоритмы
(07.10.2007 - 17:30)

Приближенный алгоритм для задачи о коммивояжере в метрическом пространстве, полностью полиномиальная приближенная схема для задачи о рюкзаке.
4. Приближённые алгоритмы
(14.10.2007 - 17:35)

Задача о взвешенном вершинном покрытии, задача о минимальном множестве представителей.
5. Приближённые алгоритмы
(11.11.2007 - 17:35)

Постановка задачи полуопределённого программирования, приближённый алгоритм для задачи о максимальном разрезе, раскраска 3–раскрашиваемого графа.
6. Вероятностные алгоритмы
(11.11.2007 - 17:45)

Проверка перемножения матриц, сравнение строк, корни многочлена, эквивалентность ветвящихся программ.
7. Вероятностные алгоритмы
(18.11.2007 - 17:50)

Минимальный разрез, проверка простоты числа.
8. Вероятностные алгоритмы
(18.11.2007 - 18:00)

Поиск расстояний в графе, поиск виновников в умножении булевых матриц, поиск кратчайших путей в графе.
9. Вероятностные алгоритмы
(25.11.2007 - 18:20)

Линейный вероятностный алгоритм нахождения минимального покрывающего дерева. Алгоритм и оценки времени его работы в худшем и среднем случае.
10. Дерандомизация
(25.11.2007 - 18:25)

Метод условных вероятностей, метод малых пространств событий.
11. Задача выполнимости
(02.12.2007 - 18:25)

Сведения японских кроссвордов, игры Eternity и задачи о максимальном разрезе к задаче выполнимости.
12. Алгоритмы для задачи выполнимости
(02.12.2007 - 18:25)

Расщепляющие алгоритмы (DPLL, PPSZ), случайные блуждания.
13. Подходы к решению NP–трудных задач
(17.02.2008 - 18:40)

Расщепление, случайный порядок перебора, локальный поиск, динамическое программирование, сведение к простой задаче, случайное сведение к простой задаче, умный перебор.
14. Задача линейного программирования
(24.02.2008 - 18:35)

Потоки в сетях, максимальное паросочетания в двудольном графе, двойственность, симплекс–метод.
15. Полиномиальный алгоритм для задачи линейного программирования
(09.03.2008 - 14:55)

Алгоритм Кармаркара.
16. Динамическое программирование
(09.03.2008 - 18:35)

Наибольшая возрастающая подпоследовательность, стоимость редактирования, рюкзак, перемножение нескольких матриц, кратчайшие пути, независимые множества в деревьях.
17. Жадные алгоритмы
(16.03.2008 - 18:35)

Задача о выборе заявок, коды Хаффмена, покрытие множествами, вершинное покрытие, локальный поиск для задачи выполнимости.
18. Нахождение максимального потока
(16.03.2008 - 18:55)

Метод Форда–Фалкерсона, алгоритм проталкивания предпотока, алгоритм «поднять-и-в–начало».
19. Потоки в сетях с несколькими веществами
(23.03.2008 - 18:30)

Вероятностное округление для задачи о потоке в сетях с несколькими веществами.
20. Максимальное паросочетания
(30.03.2008 - 19:00)

Дополняющие пути, случай двудольных графов, общий случай.
21. Алгоритмы, обрабатывающие вход по мере поступления
(06.04.2008 - 18:30)

Задача кэширования, задача о покрытии множествами.
Ваша оценка: Пусто Средняя: 4.5 (8 votes)
Share |
Александр Куликов