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

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

Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле

Метод динамического программирования (время: O∗(2n), память: O∗(2n)).

Метод включений-исключений (время: O∗(2n), память: O∗(1)).

Матрица Татта и перманент, решение для двудольного графа за O∗(2n/2) времени и O∗(1) памяти.

Страница лекции на сайте 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