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