Статья
  • формат pdf
  • размер 420,02 КБ
  • добавлен 23 ноября 2012 г.
Спецкурс Эффективные алгоритмы. Часть 2
СПб.: Санкт-Петербургский государственный университет (СПбГУ); Санкт-Петербургское отделение Математического института им. В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2001 г.
Спецкурс прочитан в Санкт-Петербургском государственном университете (СПбГУ) в 2001 г. Материал включает в себя конспекты 6 лекций по указанному спецкурсу.
Минимальное сечение, минимальное остовное дерево, детерминированный поиск подстроки.
Линейное программирование.
Проверка простоты числа. Рисование планарного графа. Параллельный алгоритм для задачи о максимальном независимом множестве.
Приближенные алгоритмы для задач о рюкзаке, покрытии множествами, раскраске графа и задачи о коммивояжере в метрическом пространстве.
Вероятностный алгоритм для 3-SAT. Приближенный алгоритм для минимального вершинного покрытия. Вычисление максимального потока.
Приближенный подсчет количества наборов, выполняющих формулу в дизъюнктивной нормальной форме (ДНФ).
Похожие разделы