Деление, рекуррентные соотношения (12 сентября 2017)

  1. Быстрое деление
    1. Обращение формального ряда за O(nlogn)
    2. Деление многочленов с остатком за O(nlogn)
    3. Деление длинных чисел за O(nlogn)
    4. Извлечение корня из длинного числа за O(nlogn)

  2. Линейные рекуррентные соотношения
    1. Вычисление чисел Фибоначчи за O(logn)
    2. Вычисление линейной k-рекурренты F(n) за O(kn) и O(k3logn)
    3. Вычисление линейной k-рекурренты F(n) за O(nlogn) и O(klogklogn) (xn/(1+S(x)))
− Перерыв −
  1. Автоматы (эквивалентность, минимизация, детерминизация)
    1. Детерминизация за O(answer)
    2. Определение автомата, изоморфизма. Нахождение изоморфизма автоматов. Определение суффиксного автомата.
    3. Минимальность и правые контексты состояний автомата.
    4. Дан автомат A и минимальный автомат M, проверить, эквивалентны ли A и M за O(n+m). Следствие: проверка, является ли автомат суффиксным за O(n+m).
    5. Эквивалентность. Задача: даны два автомата из n вершин, над алфавитом k, проверить на эквивалентность.
      1. bfs за O(n2k) времени и O(n2) памяти
      2. Через минимизацию одного из двух
    6. Минимизация автоматов
      1. Через детерминизацию (Алгоритм Бржозовского): Amin = d(r(d(r(A)))) = drdrA. Подходит для недетрминированных. [paper].
      2. Алгоритм Хопкрофта за O(knlogn) расщеплением классов. Быстр.