Метод Гаусса. Изоморфизмы. (13 мая)

  1. Гаусс. Окончание.
    1. Поддерживаем базис векторов, инкрементальная версия Гаусса. Поддерживаем выражение базиса через исходные вектора.
    2. Проверка, лежит ли вектор в пространстве, линейно ли зависим с данными
    3. Нахождение проекции Гауссом
  2. Вероятности и матожидания
    1. В конечном графе задан Марковский процесс. В каком состоянии он стабилизируется?
    2. Моделирование. Когда-нибудь сойдётся.
    3. Решение возведением матрицы в степень (сойдётся быстрее!)
    4. Решение Гауссом
    5. Сравнение трёх методов (Гаусс − быстрее, но имеет большую погрешность)
  3. Анонс: алгоритм Видеманна для решения Ax = 0 за O(nk), алгоритм Бэрликэмпа-Мэсси за O(m2)
  4. Проверка изоморфности
    1. Для детерминированных автоматов
      1. Равенство с точностью до перестановки
      2. Поиск минимального эквивалентному данному
      3. Проверка двух на эквивалентность
    2. Для произвольных графов
    3. [не успеем] Для деревьев
      1. [не успеем] Тип = хеш сортированного вектора типов = map: sortedString → int
      2. [не успеем] Сортировка + хеширование → очередь + бор
      3. [не успеем] Бор нам тоже не нужен