Битовое сжатие и игры на графах (6 мая)

  1. Битовое сжатие (w = size of machine word)
    1. [было на практике] Рюкзак за (nS/w) (S − размер рюкзака)
    2. [было на практике] Транзитивное замыкание графа: решение Флойдом за O(n3/w), решение за O(m + nm/w)
    3. Транзитивное замыкание графа: решение за O(m + nm/w)
    4. Гаусс работает за O(nkm), а над F2 аж за O(nkm/w)
    5. Произведение многочленов над F2 за O(n2/w)
    6. Деление многочленов над F2 за O(n2/w)
    7. Наибольшая общая подпоследовательность (показать битовый массив, сказать общие слова).
  2. Игра на супер большом дереве
    1. Формулировка задачи, откуда берутся такие деревья
    2. Подсчёт результата игры динамикой за O(2n)
    3. Отсечение рандомом, оценка времени работы T(n) = 2T(n-2) + 0.5T(n-1) ≤ 1.687n
  3. Крестики нолики
    1. Решение функцией оценки
    2. Функция оценки + перебор
    3. Функция оценки + перебор с AB-отсечением
    4. Функция оценки + перебор с AB-отсечением + отсечение "самых крутых ходов"
  4. Метод четырёх русских
    1. Умножение матриц за O(n3 / w / logn) (умножение матриц размера не более w за O(n2/logn))
    2. Дана таблица значений булевой функции, построить схему, которая задаёт эту функцию
    3. Наибольшая общая подпоследовательность за O(n2 / log2)