Кружок по информатике, суббота 14:35, 2018-2019

  • Страница кружка в informatics

    15 сентября 2018 - алгоритмы со стеком.

    • Очередь с минимумом
    • Поиск ближайшего большего элемента
    • Поиск максимальной нулевой подматрицы
    • Решение задачек

    22сентября 2018 - строки.

    • Хэши
    • Z-функция
    • Поиск подпалиндромов алгоритмом Манакера
    • Префикс-функция
    • Замыкание префикс-функции до автомата
    • Решение задачек

    29 сентября 2018 - Тренеровочный контест.

    6 октября 2018 - алгоритм Ахо-Корасик.

    • Конечные автоматы
    • Бор
    • Суффиксные ссылки и массивы переходов, их построение
    • Применение Ахо-Корасик
    • Решение задачек
  • 13 октября - Тренеровочный контест.

    20 октября - дерево отрезков

    • Дерево отрезков
    • Дерево отрезков с массовыми операциями
    • Двумерное дерево отрезков
    • Применение: поиск максимальной возрастающей подпоследовательности, площадь объединения прямоугольников
    • Sparse table
    • Решение задачек

    10 ноября 2018 - Тренеровочный контест.

    17 ноября - СНМ и декартово дерево

    • СНМ
    • Остовное дерево
    • Декартово дерево по явному ключу
    • Запросы на подотрезках в декартовом дереве
    • Решение задачек

    24 ноября 2018 - День гимназии. Выложен тренеровочный контест.

    1 декабря - неявный ключ и персистентность

    • Декартово дерево по неявному ключу
    • Отложенные операции на декартовом дереве
    • Персистентность
    • Персистентное дерево отрезков и персистентный массив
    • Персистентное декартово дерево
    • СНМ с откатом
    • Решение задачек

    8 декабря 2018 - Тренеровочный контест.

    15 декабря - структуры данных на деревьях

    • Дерево Фенвика
    • Задачи lca и la, решение с помощью двоичный подъёмов
    • Сведение задачи lca к задаче rmq с помощью Эйлерова обхода
    • Сведение задачи rmq к задаче lca с помощью построения декартового дерева по неявному ключу
    • Алгоритм Тарьяна для решения lca offline за O((n + q)*α(n)), rmq offline за O((n + q)*α(n))
    • Решение задачи la за O(n), O(log n) с помощью ladder decomposition
    • Алгоритм Фараха-Колтона-Бендера lca и rmq за O(n), O(1)
    • Решение задачи la за O(n), O(1) с помощью метода четырёх русских
    • Применение lca - запросы на путях в дереве без изменений, heavy-light decomposition
    • Решение задачек

    22 декабря 2018 - Тренеровочный контест.

    29 декабря - жадные алгоритмы на графах

    • Матроиды, примеры матроидов
    • Теорема и алгоритм Радо-Эдмонса
    • Поиск минимального остовного дерева с помощью аглоритма Краскала
    • Поиск максимального парасочетания в двудольном графе с помошью алгоритма Куна, минимальное по весу вершин в одной доли максимальное парасочетание
    • Разбор задач на жадные алгоритмы
    • Решение задачек

    Новогодние каникулы - Тренеровочный контест.

    12 января 2019 - игры

    • Выигрышные и проигрышные позиции в играх на ациклических графах
    • Выигрышны, проигрышные и ничейные позиции в играх на произвольных графах
    • Функция Шпрага-Гранди, сумма игр.
    • Решение задачек

    Следующее занятие - 2 феврвля