Алгоритмы и структуры данных 14. Декомпозиция
0:00 - Вступление
1:22 - Алгоритм Фарах-Колтона и Бендера
14:04 - RMQ c предподсчетом за O(n) и ответом на запрос за O(1)
28:12 - Центроидная декомпозиция
34:10 - Задача: поиск числа пар вершин в дереве на расстоянии d
55:10 - Heavy-light декомпозиция
1:08:48 - Утверждение: путь между u и v пересекает не больше O(logN) тяжелых путей
1:12:27 - Ответ на запрос
Дата лекции 04.05.23
Лектор: Степанов И.Д.
Монтажер: Калинин Иван
Оператор: Сибиряков Михаил
Видео Алгоритмы и структуры данных 14. Декомпозиция канала Лекторий ФПМИ
1:22 - Алгоритм Фарах-Колтона и Бендера
14:04 - RMQ c предподсчетом за O(n) и ответом на запрос за O(1)
28:12 - Центроидная декомпозиция
34:10 - Задача: поиск числа пар вершин в дереве на расстоянии d
55:10 - Heavy-light декомпозиция
1:08:48 - Утверждение: путь между u и v пересекает не больше O(logN) тяжелых путей
1:12:27 - Ответ на запрос
Дата лекции 04.05.23
Лектор: Степанов И.Д.
Монтажер: Калинин Иван
Оператор: Сибиряков Михаил
Видео Алгоритмы и структуры данных 14. Декомпозиция канала Лекторий ФПМИ
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Дискретный анализ 1. Кнезеровские графы
Гармонический анализ 1. Ряды Фурье
Многомерный анализ, интегралы и ряды 1. Дифференцируемая функция. Дифференциал. Градиент.
Алгоритмы и структуры данных (базовый поток) 15. Вычислительная геометрия на плоскости.
Введение в топологию 11. Кусочно-линейное отображение. Теорема Брауэра.
Введение в математический анализ 29. Кривизна кривой и соприкасающаяся окружность.
Алгоритмы и структуры данных (продвинутый поток) 7. SoftHeap (продолжение). Деревья поиска
Дискретный анализ 14. Алгоритм AKS, часть 2
C++ 6. xvalues, RVO, copy elision, move_if_noexcept
C++ 13. Objects as non-type template parameters / consteval / std::is_constant_evaluated
Случайные процессы 11. Цепи Маркова
Дифференциальные уравнения 14. Геодезические задачи
Дифференциальные уравнения 13. Изопериметрические задачи
Дифференциальные уравнения 12. Необходимые условия экстремума функционала для разных задач
Алгоритмы (базовый поток) 13. Потоки-2
Функциональный анализ 13. Свёртка в L1(R)
Программирование основных алгоритмов 12. Суффиксный автомат (2). Быстрое преобразование Фурье (FFT)
Алгоритмы и структуры данных 13. Центры и центроиды
ОКТЧ 14. Последовательности де Брёйна
ОКТЧ 13. Эйлеровость графа. Гамильтоновость графа. Теорема Эрдеша-Хватала