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