=^_^= Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 08 - Про разрезы (Коля Мальковский, Сергей Копелиович)

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции "Про разрезы"

  1. Рандомизированный алгоритм Каргера-Штейна (поиск глобального разреза в графе за O(n^2*P(log)))
  2. Алгоритм Хао-Орлина (поиск глобального разреза в графе за O(n^3))
  3. Алгоритм Штор-Вагнера (http://e-maxx.ru/algo/stoer_wagner_mincut)
  4. Задача о поиске K-й порядковой статистики на отрезке за O((logn)^2)
  5. B-Tree
  6. Задача 10 с Всесиба = Алгоритм Евклида

Полный план лекции

  1. Алгоритмы поиска глобального разреза
    1. Рандомизированный алгоритм Каргера-Штейна (поиск глобального разреза в графе за O(n^2*P(log)))
      1. Условие = единичная сеть без кратных ребер
      2. Простейший алгоритм за O(n^4*P(log))
      3. Модификация = каждую 1/2 вероятности создаем 2 ветки рекурсии
      4. Оценка вероятности как O(1/logn) (решим диффур)
      5. Способ за O(n) выбрать случайное ребро (с учетом кратности)
    2. Алгоритм Хао-Орлина (поиск глобального разреза в графе за O(n^3))
      1. s = rand(), t = rand(), h[v != t] = 1, h[t] = 0
      2. S = D[0] = {s}, W = V-s
      3. Ищем поток алгоритмом preflow push, push делаем только в W
      4. ReLabel(v) = если вершина оставит после себя дырку в высотной функции => добавить D[k++] = {x : h[x] >= h[v]}, если вершины не имеет ненасыщенных ребер идущих в W (из нее уже не достижим t) => D[k++] = {v}
      5. Нашли поток между t и s. Теперь склеить t и s. Для этого из t весь избыток вытолкнем по обратным ребер, и поместим эту вершину в S (D[0]).
      6. Выбор нового стока : (W = empty => W := D[--k]), t = вершина в W минимальной глубины
      7. В процессе работы алгоритма h[t] = 0,1,2,3... => h[v] <= 0+n, 1+(n-1), 2+(n-2)... <= n
      8. Время работы = O(времени preflow-push)
    3. Алгоритм Штор-Вагнера (http://e-maxx.ru/algo/stoer_wagner_mincut)
      1. Собственно алгоритм
      2. Реализации за O(V^3), O(VElogV), O(V^2logV + VE)
      3. Доказательство
  2. Задача о поиске K-й порядковой статистики на отрезке
    1. [O(n), O(sqrt(n)*logn)]
    2. [O(n), O(n^{eps}*logn)]
    3. [O(nlogn), O((logn)^2)]
    4. [O(n^2), O(logn)]
    5. [O(n^3), O(1)]
    6. Случай, когда отрезок меняется, [O(nlogn), O((logn)^3)]
  3. Дополнительно
    1. Поиск обратного к x mod 2^n за O(logn)
    2. B-Tree
    3. 2D-Dynamic-Interval-Tree + BS-Tree inside
  4. * Задачка с всесиба (подробно, с доказательствами)
    1. * (4) = Хэши + Паросочетание
    2. * (6) = Динамика
    3. * (7) = Квадродерево
    4. (10) = Алгоритм Евклида