Информатика и вычислительная техника
Презентация
  • формат pdf
  • размер 543,39 КБ
  • добавлен 10 ноября 2012 г.
Жадные алгоритмы в задачах о покрытии
Кузюрин Н.Н., Фомин С.А.
- М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 15 слайдов.
Содержание:
Приближенный алгоритм с гарантированной точностью.
Покрытие множества.
Жадный алгоритм в задаче о покрытии.
Покрытие на каждом шаге.
Точность жадного алгоритма: верхняя оценка.
Как обмануть жадный алгоритм? Нижняя оценка.
k-покрытие множества.
Вершинное покрытие.
«Ленивый» алгоритм для вершинного покрытия.
«Карта памяти» лекции.
Похожие разделы