СПб.: Санкт-Петербургский государственный университет (СПбГУ);
Санкт-Петербургское отделение Математического института им.
В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2003 г., 47 стр.
Настоящий файл отражает лекции спецкурса «Эффективные алгоритмы.
Часть I», читавшегося на математико-механическом факультете
Санкт-Петербургского государственного университета в 1999, 2001 и
2003 годах. Материал соответствует преимущественно лекциям 2001
года (с более поздними изменениями и дополнениями, в частности, из
других курсов).
Рекомендуется только для личного использования. Содержание:
Алгоритмы, обрабатывающие вход по мере поступления.
Задача кэширования (paging problem).
Задача о k официантах (k-server problem).
Задача о покрытии множествами (the online set cover problem).
Приближенные алгоритмы.
Оптимизационные задачи и приближенные алгоритмы.
Задача о покрытии множествами.
Задача о покрытии множествами (вариант с весами).
Задача о кратчайшей общей надпоследовательности.
Задача о максимальном сечении.
Задача о минимальном вершинном покрытии.
Задача о рюкзаке.
Задача о раскраске графа.
Задача об объединении множеств.
Метод Монте-Карло.
Мощность объединения множеств.
Задача о коммивояжере в метрическом пространстве.
Вероятностные алгоритмы.
Вероятностные алгоритмы.
Проверка результата алгоритма перемножения матриц.
Метод «отпечатков пальцев» в применении к задачам со строками.
Минимальное сечение (MIN-CUT).
Минимальное остовное дерево.
Проверка простоты числа.
Кратчайшие пути до всех вершин графа.
Предисловие: постановка задачи.
Поиск матрицы расстояний между вершинами.
Поиск «виновников» в умножении булевых матриц.
Объединяем все вместе.
Параллельные алгоритмы.
Параллельные вычисления.
Достижимость в графе.
Максимальное по включению независимое множество.
Задача о максимальном по включении независимом множестве.
Рекомендуется только для личного использования. Содержание:
Алгоритмы, обрабатывающие вход по мере поступления.
Задача кэширования (paging problem).
Задача о k официантах (k-server problem).
Задача о покрытии множествами (the online set cover problem).
Приближенные алгоритмы.
Оптимизационные задачи и приближенные алгоритмы.
Задача о покрытии множествами.
Задача о покрытии множествами (вариант с весами).
Задача о кратчайшей общей надпоследовательности.
Задача о максимальном сечении.
Задача о минимальном вершинном покрытии.
Задача о рюкзаке.
Задача о раскраске графа.
Задача об объединении множеств.
Метод Монте-Карло.
Мощность объединения множеств.
Задача о коммивояжере в метрическом пространстве.
Вероятностные алгоритмы.
Вероятностные алгоритмы.
Проверка результата алгоритма перемножения матриц.
Метод «отпечатков пальцев» в применении к задачам со строками.
Минимальное сечение (MIN-CUT).
Минимальное остовное дерево.
Проверка простоты числа.
Кратчайшие пути до всех вершин графа.
Предисловие: постановка задачи.
Поиск матрицы расстояний между вершинами.
Поиск «виновников» в умножении булевых матриц.
Объединяем все вместе.
Параллельные алгоритмы.
Параллельные вычисления.
Достижимость в графе.
Максимальное по включению независимое множество.
Задача о максимальном по включении независимом множестве.