ЛекториумМедиатека
Поиск
Личный кабинет

Алгоритмы для NP-трудных задач (2013). Лекция 8

Точные алгоритмы для задачи раскраски графа

3-раскраска: время O∗(2n) и полиномиальная память с помощью перебора, улучшение до O∗(1.9n); вероятностный O∗(1.5n) алгоритм через сведение к задаче 2-выполнимости; O∗(1.45n) через использование максимальных по включению независимых множеств. Общая задача: время O∗(3n) и память O∗(2n) через динамическое программирование, улучшение до O∗(2.45n) через максимальные по включению независимые множества; время и память O∗(2n) через формулу включений-исключений и быстрое преобразование Фурье.

Страница лекции на сайте Computer Science Club

Лекции курса

13
  1. Алгоритмы для NP-трудных задач (2013). Лекция 1
  2. Алгоритмы для NP-трудных задач (2013). Лекция 2
  3. Алгоритмы для NP-трудных задач (2013). Лекция 3
  4. Алгоритмы для NP-трудных задач (2013). Лекция 4
  5. Алгоритмы для NP-трудных задач (2013). Лекция 5.1
  6. Алгоритмы для NP-трудных задач (2013). Лекция 5.2
  7. Алгоритмы для NP-трудных задач (2013). Лекция 6
  8. Алгоритмы для NP-трудных задач (2013). Лекция 7
  9. Алгоритмы для NP-трудных задач (2013). Лекция 8▶ Вы тут
  10. Алгоритмы для NP-трудных задач (2013). Лекция 9
  11. Алгоритмы для NP-трудных задач (2013). Лекция 10
  12. Алгоритмы для NP-трудных задач (2013). Лекция 11
Показать все 13 лекций
  1. Алгоритмы для NP-трудных задач (2013). Лекция 12

Онлайн-курсы по программированию

3