АиСД S02E15. Сложность задач. Классы сложности.
Алгоритмы и структуры данных. Семестр 2. Лекция 15.
На последней лекции мы поговорили о том, какие задачи решаются за полиномиальное время, какие за неполиномиальное, и какие не решаются совсем. Также обсудили, как одни задачи сводятся к другим, и показали, что задача о рюкзаке является NP-полной
Университет ИТМО, 2021 г.
Видео АиСД S02E15. Сложность задач. Классы сложности. канала Pavel Mavrin
На последней лекции мы поговорили о том, какие задачи решаются за полиномиальное время, какие за неполиномиальное, и какие не решаются совсем. Также обсудили, как одни задачи сводятся к другим, и показали, что задача о рюкзаке является NP-полной
Университет ИТМО, 2021 г.
Видео АиСД S02E15. Сложность задач. Классы сложности. канала Pavel Mavrin
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
АиСД S02E02. Дерево отрезков. Операции на отрезке
АиСД S03E01. Графы. Обход в глубину. Топологическая сортировка
A&DS S02E13. Centroid Decomposition
АиСД S03E08. Еще раз про минимальное остовное дерево
АиСД S02E14. Алгоритмы во внешней памяти
АиСД S04E06. Кососимметрические потоки
АиСД S04E13. Приближенные алгоритмы
A&DS S03E10. Finite State Automata
A&DS S04E09. Linear Programming
A&DS S04E01. Maximum Matchings in Bipartite Graphs
АиСД S04E14. Приближенные алгоритмы
Evening Stream 30.07.21. ABC 169, 170
A&DS S03E03. Bridges, Articulation Points, Euler Cycle
АиСД S03E13. Суффиксное дерево. Алгоритм Укконена
A&DS. Time Complexity of Union-Find (inverse Ackermann function)
АиСД S01E07. Связные списки. Pointer Machine
A&DS S03E05. Minimum Spanning Tree
АиСД S02E13. Центроидная декомпозиция
АиСД S04E05. Потоки. Динамические деревья. Алгоритм Хопкрофта-Карпа
АиСД S01E07. Связные списки. Pointer Machine