СНМ и Остовные деревья (12 марта 2018)

  1. [30 минут] DSU (СНМ)
    1. Постановка задачи (join, get)
    2. Пример использования (для каждой пары вершин [a,b] найти путь: max вес на пути минимален)
    3. Решение списками: join суммарно за O(nlogn), get за O(1)
    4. Решение деревьями
      1. join за O(1), get за длину пути
      2. Эвристика "меньшее к большему". Варианты с ранками и размерами. Доказательство O(logn) для get.
      3. Эвристика сжатия путей. Доказательство O(logn) для этой эвристики (смотрим на количество тяжёлых рёбер).

  2. [20 минут] DSU: крутые оценки
    1. [15 минут] O(mlog*n)
    2. [5 минут] O(m + nlog*n)
− Перерыв −
  1. [35 минут] MST (минимальные остовы)
    1. [10 минут] Основы доказательства: лемма о тяжёлом ребре (лемма о разрезе)
    2. [5 минут] Краскал = sort + DSU. Разрез: компоненты концов ребра.
    3. [5 минут] Прим = Дейкстра с функцией "max входящий вес" (с доказательством). Разрез: дерево и оставшаяся часть графа.
    4. [10 минут] Борувка = итеративное сжатие графа. Добавляем рёбра по одному в правильном порядке.
− Перерыв −
  1. [15 минут] Алгоритм Йена'71 поиска k-го объектра
    1. k-й путь за O(Vk*Dijkstra)
    2. k-й остов за O(Ek*MST)

  2. [30 минут] DSU: обратная функция Аккермана
    1. Доказываем log*(log*n) + 2, log*(log*(log*n)) + 3...
    2. Получаем "сколько раз нужно взять log*x, чтобы число итераций было больше результата"
    3. Вводим функцию Аккермана и обратные ей. Показываем основные свойства.
    4. Доказываем функцию Аккермана.