Изоморфизм Деревьев - Лекция

Это лекция, в рамках которой мы рассмотрели алгоритмы нахождения изоморфизма деревьев: подвешенных и неподвешенных (когда корень не фиксирован). Реализации алгоритмов на C++ посвящена вторая часть видео: https://www.youtube.com/watch?v=xZEuYi9k36w Материалы с лекции (включая все исходники и все ссылки на статьи): https://docs.google.com/document/d/1OQKS5O-OjvFfhukNQMHONdiE1JD863BNiGF1d-rOAmU/edit?usp=sharing в документе смотрите раздел "Изоморизм деревьев" Тайм-коды и разделы: 00:00:00 Введение 00:01:00 Vladosiya - виновник появления изоморфизма на Div3 контесте 00:03:15 Изоморфизм деревьев в ШАД на первом курсе 00:05:35 Лекции «Зимней компьютерной школы» - 2100 страниц олимпиадного программирования 00:09:00 Где дорешать задачи «Зимней компьютерной школы» 00:12:00 Лекция Сергея Копелиовича об изоморфизме деревьев, 2013, страница 264 00:12:54 Реклама лекции по терверу, 2014, страница 8 00:13:45 Задача «G. Симмеtreeя» - разбираем примеры из условия 00:21:10 Изоморфизм деревьев - определение 00:24:15 Классы эквивалентностей поддеревьев 00:35:15 Перерыв 70 секунд 00:36:25 Алгоритм нахождения классов эквивалентностей поддеревьев 00:45:20 Класс эквивалентности вершины через классы эквивалентностей прямых потомков 00:49:10 Работа алгоритма на конкретном примере по шагам 00:57:20 Более сложный пример по шагам 00:59:45 Сортировать потомков по их классам - обязательный шаг 01:01:10 Какие структуры данных понадобятся 01:02:45 Доказываем асимптотику: map из vector из int уже даёт O(n log(n)) 01:07:50 Доказываем асимптотику: все сортировки вместе дают O(n log(n)) 01:12:00 Четыре хеш-функции для поддеревьев 01:12:48 Полиномиальный хеш не работает 01:14:07 Добиваем решение задачи «G. Симмеtreeя» - проверка симметрии 01:16:55 Почему НЕЛЬЗЯ идти снизу-вверх, проверяя симметрию 01:18:18 Изоморфизм НЕподвешенных деревьев 01:24:00 Подвешиваем за центр дерева - их два или один и центр переходит в центр при изоморфизме 01:27:00 Как искать диаметр дерева и центр дерева 01:30:27 Находим центр алгоритмом «поджога» листьев 01:32:00 Ускорение в 4 раза от Копелиовича путём добавления фиктивной вершины между двумя центрами 01:34:00 Подвешиваем за центроид - их тоже два либо один 01:35:55 Нахождение центроида