Алгоритмы и структуры данных 14. Convex Hull Trick, Дерево Ли-Чао, Вероятностные алгоритмы

Показать описание

Таймкоды:
00:00:00 - Convex Hull Trick со скалярным произведением
00:34:00 - Convex Hull Trick с прямыми
00:49:00 - дерево Ли-Чао
00:59:00 - унимодальная функция, тернарный поиск
01:13:00 - выпуклая функция
01:26:00 - унимодальность выпуклой функции
01:43:00 - примеры
01:44:00 - свойства выпуклых функций
01:51:00 - задача про расстояния
02:08:00 - задача про вписанную в многоугольник окружность
02:16:00 - пересечение полуплоскостей
02:45:00 - задача про две окружности, вписанные в многоугольник
02:46:00 - 2 типа вероятностных алгоритмов
02:56:00 - оценка времени работы QuickSort
03:10:40 - оценка времени работы QuickSelect
03:25:40 - монетка, математическое ожидание
03:31:47 - random tree game eval
03:53:45 - альфа-бета отсечения
04:11:16 - алгоритм Каргера
04:33:50 - алгоритм Каргера-Штейна
05:06:20 - минимальный остов за линию
06:00:56 - доказательство
06:33:00 - умножение булевых матриц
07:01:15 - восстановление свидетелей

Дата лекции: 06.12.23
Лектор: Рухович Филипп Дмитриевич

Оператор: Порай К.
Монтажёр: Алиев А.