СНМ и Остовные деревья (26 февраля 2021)

1. [35 минут] Краскал и DSU
   1. Алгоритм Краскала : жадность
   2. Доказательство
      1. Рассмотрим оптимальный ответ, сделаем замену
      2. Обобщение доказательства : лемма о разрезе (&exists; MST, содержащее всё уже выбранное и "e")
   3. Реализация Краскала, DSU
      1. Решение списками: меньшее к большему, join суммарно за O(nlogn), get за O(1)
      2. Решение деревьями. Эвристика "меньшее к большему" и ранговая версия.
      3. Решение деревьями. Эвристика "сжатие путей".
   
   
2. [35 минут] DSU. Доказательства
   1. Эвристика сжатия путей. Доказательство O(logn) для этой эвристики (смотрим на количество тяжёлых рёбер).
      1. Эвристика "меньшее к большему". Варианты с рангами и размерами. Доказательство O(logn) для get.

1. [35 минут] DSU. Доказательства
   1. Две эвристики O(mlog^*n)
      1. Две эвристики O(m + nlog^*n)
   
   
2. [20 минут] MST (минимальные остовы)
   1. Прим = Дейкстра с функцией "max входящий вес" (с доказательством). Разрез: дерево и оставшаяся часть графа.
   2. Борувка = итеративное сжатие графа. Добавляем рёбра по одному в правильном порядке.
   3. Борувка за min(V², ElogV)

Дополнительная лекция

1. [15 минут] Алгоритм Йена'71 поиска k-го объектра
   1. k-й путь за O(Vk*Dijkstra)
   2. k-й остов за O(Ek*MST)
   
   
2. Эппштейн для {unknown_variable:k}-го непростого пути
   1. Пример с динамикой
   2. Решение за O((n+m+k)log(nk))
   
   
3. [30 минут] DSU: обратная функция Аккермана
   1. Доказываем log^*(log^*n) + 2, log^*(log^*(log^*n)) + 3...
   2. Получаем "сколько раз нужно взять log^*x, чтобы число итераций было больше результата"
   3. Вводим функцию Аккермана и обратные ей. Показываем основные свойства.
   4. Доказываем функцию Аккермана.