Скачать с ютуб Алгоритмы и структуры данных 3. Экспоненциальное ДП: по маске, по профилю. NP-трудные задачи в хорошем качестве

Алгоритмы и структуры данных 3. Экспоненциальное ДП: по маске, по профилю. NP-трудные задачи

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 17 февраля 2022 года Лектор: Степанов Илья Даниилович Оператор: Ирина Жулябина Монтаж: Жильцов Игорь 0:00 - ДП по маске (по подмножеству) 3:40 - Операции над масками 4:00 - Извлечение бит, проверка наличия элемента в множестве 7:55 - Объединение множеств 8:58 - Пересечение 9:35 - Разность множеств 11:45 - Задача 1. Самый дешевый гамильтонов путь в полном взвешенном графе 25:44 - Асимптотика 27:00 - Завершение решения задачи 1 27:53 - Упражнение: поиск гамильтонова пути в произвольном графе за O(2^n * n) 30:00 - Задача 2. О максимальной клике 32:14 - Решение за O(2^n * n^2) [полный перебор] 33:27 - Решение 2 за O(2^n * n) 35:40 - Оптимизация перехода до О(1) [решение 2,5 за O(2^n)] 37:55 - Решение 3 за O(2^n) 47:30 - Решение 4 за O(2^(n/2) * n). Meet-in-the-middle 1:02:10 - Ещё одна оптимизация из зала [решение 4,5 за O(2^(n/2))] 1:04:40 - Продолжение более общего решения 1:12:50 - Улучшается ли асимптотика засчёт разбиения на большее кол-во подмн-в? 1:14:00 - ДП по профилю. Задача 3. О доминошках 1:22:55 - Асимптотика