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

Лекции группы A0 - Лекция 03 - про алгоритм 4-х русских

Краткий план лекции на тему "Алгоритм 4-х русских"

1. Перемножение матриц
2. Задача про построение булевой функции
3. Быстрые RMQ алгоритмы
4. Наибольшая общая подпоследовательность
5. СНМ
6. * Задача про добавляющиеся и удаляющиеся ребра
7. Сортировка Шелла
8. * Умножение чисел

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

1. Перемножение матриц
1. Алгоритм за O(n^3), стандартные не асимптотические оптимизации
2. Алгоритм Штрассена [r=2, a=7] за O(n^{2.807}), оптимизация Винограда (15 сложений вместо 18-и)
3. Алгоритм Пана [r=70, a=143640] за O(n^{2.796}), сложность = n^[log_r{a}], док-во
4. Алгоритм Копперсмита — Винограда за O(n^{2.375})
5. Использование теории групп для получения алгоритма за O(n^{2.48})
6. Использование битового сжатия для бинарных матриц - O(n^3 / logn)
7. Использование алгоритма 4-х русских для бинарных матриц - O(n^3 / (logn)^2)
8. Умножение матриц за O(n^2 / logn) :-D
9. Плюс по сравнению с обычным битывым сжатием - возможность умножать битовую на не битовую
10. Деление = Обращение = Решение систем >= Умножение
2. Задача про построение булевой функции
1. Решение за [2^n * n]. КНФ + предподсчитать ~x.
2. Решение за [2^(n+1)]. Раскрытие скобок в КНФ.
3. Применение идеи 4-х русских, O(2^n / n). Оптимайз с хэшированием ВСЕХ состояний.
3. Быстрые RMQ алгоритмы
1. За [O(logn), O(n)] с помощью дерева отрезков
2. За [O(1), O(nlogn)] с помощью таблички
3. За [O(loglogn), O(n)] и [O(log*n), (O(nlog*n)] комбинируя эти методы
4. Наибольшая общая подпоследовательность
1. Классическое решение за O(n^2)
2. Оптимизация с помощью 4-х русских до O(n^2 / (logn)^2)
5. СНМ
1. Простая реализация с color[v], [O(m), O(n^2)]
2. Оптимизация перекраски меньшего множества [O(m), O(nlogn)]
3. Подвешивание [O(mn), O(n)]
4. Подвешивание меньшего к большему [O(mlogn), O(n)], пример с =mlogn, док-во
5. Сжатие путей [O(mlogn), O(n)], пример с =mlogn, без док-ва того, что работает O(mlogn)
6. * Объединение двух эвристик, алгоритм за [O(m*), O(n)], док-во через крутые ребра
7. Реализация W за [O(m), O(n)] в предположении того, что дерево объединения известно заранее
1. Разбиение подвешенного дерева на куски размера [2..2k) с общим родителем. Добавление к лесу фиктивного корня.
2. Собственно идея 4-х русских : внутри куска запрос выполняется за O(1). Предподсчет = upp[tree, a]
3. Кусков n / k. Из их корней сделали дерево, на нем реализовали алгоритм [O(m), O(nlogn)]
4. Запрос get(a) = micro + macro + micro. Если micro(x) != micro(macro), нужно делать join в macro
5. Операция link(v, parent[v]) = добавить ребро в micro-tree с помощью битовых масок за O(1)
6. Хранение micro-tree. Строим лес [или переходим к следующей вершине, или вешаем на эту] => нужно 2k-2 бит. k = O(logn) => [O(m), O(n)]
8. Применение реализации W для получения LCA-Offline за O(n+m)
6. * Задача про добавляющиеся и удаляющиеся ребра
1. * Только добавление = СНМ
2. * Только удаление = СНМ (в обратном порядке => добавление)
3. * При фиксированном дереве получаем Add = Del = Get = O(logn) = запрос к дереву отрезков для суммы
4. * Добавление + Удаление = СНМ + корневая эвристика [O(V)]
7. Сортировка Шелла
1. Сортировка вставками. Число операций = O(n) + число инверсий
2. K-сортированный массив. A-сортированный массив после B-сортировки остается A-сортированным (swap-ы можно делать в любом порядке)
3. (A,B)=1, массив A,B-отсортирован => Время X сортировки = A*B*N / X
4. Результат про (AB - A - B + 1) / 2 чисел, которые нельзя получить, как Ax + By (x, y >= 0)
5. h[k] = 2^k - 1 => Time = O(n^{3/2})
6. Последовательность 2^s * 3^t дает время O(n(logn)^2)
8. * Умножение чисел
1. * За O(mlen^2) + O(nm) умножений + O(n+m) делений
2. * Карацуба = O(n^log3)
3. * Аццкий метод за O(n^{1+eps}) с интерполяцией и экстерполяцией за O(1)