Лекции, прочитанные на сборах

20 марта

Лекция D: Структуры данных – 1 (Алексей Гусаков)


  1. Списки. Односвязные и двусвязные. Добавление/удаление. Кольцевые списки.
  2. Стеки. Стеки на массивах и списках. Примеры простейших задач на стеки.
  3. Очереди. Очереди на списках. Очереди на массивах в виде циклического буфера.
  4. Деки. Задачи на деки. Лабиринты.
  5. Сортированные массивы. Бинарный поиск.
  6. Хэш-таблицы.

Лекция С: Структуры данных – 1 (Андрей Шестимеров)


  1. Простые структуры данных.
    1. Очереди и стеки.
    2. Списковые структуры, представление списков в массиве.
    3. Списки в динамической паматью
  2. Бинарный поиск, поиск k-го по величине в массиве
  3. Heap, Heap-sort и очередь с приоритетами
  4. Дерево отрезков
    1. Обзор
    2. Init
    3. Update
    4. Запросы
    5. Обобщение на многомерный случай
  5. Двойчные деревья поиска
    1. Поиск
    2. Добавление и удаление
    3. Сбалансированные деревья.

Лекция B: Геометрия (Дмитрий Королев)


  1. Систематизация подходов к решению задач на вычислительную геометрию
    1. Метод границ
    2. Метод деления пополам
    3. Примеры
      1. Пример 1 – Задача о самолётах (см. ниже)
      2. Пример 2 – Задача о бассейне (см. ниже)
    4. Теорема Хэлли и её использование
  2. Разбиения плоскости
    1. Двоичное деление пространства (BSP-Trees)
      1. Построение BSP-Tree
      2. Алгоритмы на BSP-Tree и их эффективность
      3. Пример использования : точки, отдалённые от данной не более, чем на R
    2. Области Вороного
      1. Определение
      2. Свойства
      3. Использование областей Вороного в задачах
      4. Разбор задачи "Области Вороного на плоскости при использовании Матхэттенской метрики расстояния"
    3. Триангуляции
      1. Определение триангуляции
      2. Триангуляция Делоне
      3. Свойства триангуляции Делоне
      4. О двойственности триангуляции Делоне областям Вороного
      5. Алгоритмы построения триангуляции Делоне
      6. Алгоритм "Разделяй и Властвуй" для построения триангуляции Делоне : разбор
      7. Разбор задачи "Стол в колоннах"
  3. Стереометрия
    1. Эффективное использование скалярного и векторного произведений в пространстве
    2. Yet another алгоритм решения задачи об объёме общей части выпуклых тел 
    3. Подробный разбор решения задачи "Пересечение кубов"

Задача о самолётах. Над единичным квадратом пролетели по прямым N самолётов. Каждый самолёт "видит" на расстояние K. Определить, остались ли в этом квадрате точки, которые не увидел ни один самолёт. Вариант: найти минимальное K, для которого таких точек не осталось.

Задача о бассейне. В единичном квадрате имеется несколько колонн (окружностей) одинакового радиуса. В этот квадрат хочется поместить круглый бассейн. Найти максимальный радиус этого бассейна.

Лекция A: Суффиксные деревья. Алгоритм Мак-Крейта построения суффиксного дерева за линейное время (Борис Василевский)

  1. Суффиксное дерево, наивный алгоритм
  2. Сжатое суффиксное дерево, детали реализации
  3. Суффиксные ссылки
  4. Общий шаг алгоритма Мак-Крейта
  5. Добавление следующего суффикса, «скачок по счетчику»
  6. Сохранение структуры суффиксных ссылок
  7. Оценка количества действий O(n)
  8. Использование суффиксных деревьев
    1. Поиск подстроки в строке
    2. Обобщенное суффиксное дерево
    3. Количество различных подстрок в строке
    4. Наибольшая общая подстрока
    5. Поиск максимальных повторов

21 марта

Лекция D: Структуры данных – 2 (Алексей Лахно)

  1. Двоичные деревья поиска
    1. Основные определения
    2. Обход дерева и печать элементов в неубывающем порядке
    3. Поиск элемента по ключу
    4. Нахождение минимального и максимального элементов
    5. Нахождение следующего и предыдущего
    6. Добавление элемента
    7. Удаление элемента
  2. Вектор (саморасширяющийся массив)
    1. Понятие вектора
    2. Оценка времени добавления элемента двумя способами
  3. Двоичная куча (Heap)
    1. Понятие двоичной кучи и ее основное свойство
    2. Процедура Heapify поддержания основного свойства кучи
    3. Построение кучи. Линейная оценка сложности
    4. Heap Sort — сортировка с помощью кучи
    5. Приоритетная очередь: операции добавления и извлечения максимального элемента
    6. Разбор задачи «Тупики» с Московской Городской олимпиады

Лекция С: Структуры данных – 2 (Андрей Шестимеров)

  1. Декартовы деревья
  2. Хеш-таблицы
    1. Хеш-функции
    2. Методы разрешения коллизий
    3. Хеширование с открытой адресацией
    4. Двойное хеширование
  3. Системы непересекающихся множеств
    1. Операции
    2. Реализация с помощью массивов
    3. Реализация с помощью списков
    4. Лес непересекающихся множеств

Лекция AB: LCA и RMQ за O(1) (Александр Чернов)

  1. Манипуляции с битами: обнуление/установка единичных битов справа и т. п., округление к ближайшей степени 2, подсчет единичных и нулевых битов в слове.
  2. Постановка задачи LCA: Least common accessor в дереве, постановка задачи RMQ: Range Minimum Query, сведение задачи LCA к RMQ за O(n), где n – число узлов в дереве.
  3. Решение задачи RMQ с предвычислением за O(n log n) (n – размер массива) и стоимостью запроса O(1) методом динамического программирования.
  4. Задача ±1 RMQ, решение задачи с предвычислением за O(n) и стоимостью запроса O(1). Таким образом получаем алгоритм решения LCA с предвычислением O(n) и запросом O(1).
  5. Сведение задачи RMQ к задаче LCA за O(n). В итоге получаем RMQ с предвычислением O(n) и запросом O(1).

Литература:
  1. Генри Уоррен, мл., Алгоритмические трюки для программстов.
  2. Michael A. Bender, Martin Farach-Colton, The LCA Problem Revisited

22 марта

Лекция D: Длинная арифметика (Вадим Антонов)


  1. Хранение длинных чисел.
  2. Сравнение длинных чисел.
  3. Арифметические операции над длинными числами:
    а. Сложение
    б. Вычитание
    в. Умножение
    г. Деление длинного числа на короткое
    д. Деление длинного числа на длинное

Лекция С: Базовые строковые алгоритмы (Борис Василевский)


  1. Алгоритм Кнута-Морриса-Пратта
    1. Введение, обозначения, наивный алгоритм
    2. Префикс – функция
    3. КМП 
    4. Интерпретация с использованием конечного автомата
  2. Алгоритм Ахо-Корасик
    1. Бор, сжатый бор 
    2. Построение бора по набору слов
    3. Интерпретация с использованием конечного автомата, суффиксные ссылки
    4. Ахо-Корасик

Лекция AB: Теорема Геделя о неполноте (Алексей Семенов)

23 марта

Лекция D: Вычислительная геометрия на плоскости (Сергей Шедов)


  1. Векторы
    1. Понятие вектора
    2. Координаты вектора
    3. Операции над векторами
    4. Скалярное произведение векторов
    5. Векторное (косое) произведение векторов
  2. Нахождение полярного угла
  3. Типы данных для программирования задач вычислительной геометрии
  4. Взаимное расположение точек и фигур
    1. Принадлежность точки прямой
    2. Принадлежности точки лучу
    3. Принадлежность точки отрезку
    4. Расстояние от точки до прямой
  5. Определение факта пересечения двух отрезков
  6. Уравнение прямой
  7. Уравнение окружности
  8. Уравнение биссектрисы угла
  9. Уравнение касательной к окружности (геометрический метод)
  10. Нахождение точек пересечения окружности и прямой (геометрический метод)
  11. Нахождение точек пересечения двух окружностей (алгебраический и геометрический методы)
  12. Нахождение площади простого многоугольника
  13. Определение принадлежности точки простому многоугольнику
  14. Примеры решения задач прошлых Всероссийских олимпиад рассмотренными методами
    1. Задача «Лесной пожар»
    2. Задача «Раздел царства»

Лекция С: Перебор (Алексей Лахно)


  1. Игровые задачи. Альфа-бета отсечение
  2. Задачи на перебор с возвратом. Метод ветвей и границ
  3. Отсечение по времени на C и Паскале
  4. Оптимизационные задачи и эвристические методы их решения
    1. Метод локальных улучшений
    2. Случайный поиск
    3. Метод отжига

Лекция AB: Игры и стратегии (Антон Фонарев)

  1. Игры на графах
    1. выигрышные/проигрышные позиции
    2. игры на ациклических графах
    3. игры на циклических графах, ничья
  2. Число Спрага-Гранди
    1. определение
    2. теорема Спрага-Гранди
    3. примеры (Grundy's game, Withoff's game, Euclid, Nim, Hackenbush)
  3. Теория игр 
    1. антагонистические игры в нормальной форме
    2. матричные игры
    3. максмин и минимакс
    4. значение игры и оптимальные стратегии
    5. смешанные стратегии
    6. существование решения матричной игры в смешанных стратегиях
    7. итеративный метод решения матричных игр 
  4. Позиционные игры n игроков в общем случае
    1. существование решения конечной игры n лиц с полной информацией (центральная теорема)

24 марта

Лекция D: Динамическое программирование (Александр Мамонтов)

  1. Общие понятия (что такое динамика, для чего и когда используется)
  2. Принцип динамики (подзадача, разбиение задачи на подзадачи)
  3. Примеры и пояснения
    1. Числа Фибоначи
    2. Гвоздики
    3. Биномальные коэффициенты (колво способов добраться в таблице)
    4. Минимальный путь в таблице.
    5. Наибольшая возрастающая подпоследовательность
    6. Лесенки.
    7. Восстановление скобок

Лекция C: Геометрия (Сергей Шедов)


  1. Повторение базовых понятий вычислительной геометрии на плоскости (векторы, скалярное и векторное (косое) произведение векторов, полярный угол, способы описания прямой и окружности на плоскости)
  2. Особенности программирования задач вычислительной геометрии
  3. Определение взаимного расположения геометрических объектов и нахождение точек пересечения
    1. Расположение точки относительно прямой, луча или отрезка
    2. Взаимное расположение прямых, отрезков, лучей
    3. Взаимное расположение окружности и прямой
    4. Взаимное расположение двух окружностей
  4. Многоугольники
    1. Проверка выпуклости многоугольника
    2. Проверка принадлежности точки внутренней области простого многоугольника
    3. Вычисление площади простого многоугольника
    4. Построение выпуклой оболочки для множества из N точек плоскости
    5. Особые точки многоугольников и множеств N точек плоскости
  5. Эффективный алгоритм нахождения ближайшей пары из N точек плоскости
  6. Примеры задач всероссийских олимпиад прошлых лет на методы вычислительной геометрии

Лекция AB: Языки и автоматы (Александр Шень)


  1. Конечные автоматы
    1. Определение детерминированного конечного автомата (DFA)
    2. Автомат, распознающий язык
    3. Определение и примеры регулярных языков
    4. Недетерминированный конечный автомат (NFA)
    5. Детерминизация NFA 
  2. Операции над автоматами
    1. Регулярность дополнения к регулярному языку
    2. Регулярность конкатенации двух регулярных языков
    3. Регулярность итерации регулярного языка

28 марта, вторник

Лекция D: Графы – 1 (Алексей Лахно)

  1. Понятие графа. Основные определения
  2. Способы представления графов
  3. Алгоритмы нахождения минимального остовного дерева
    1. Алгоритм Прима
    2. Алгоритм Краскала
  4. Поиск в глубину и его применение
    1. Общая схема
    2. Компоненты связности
    3. Топологическая сортировка
    4. Другие задачи, решаемые с помощью поиска в глубину: поиск мостов, точек сочленения, компонент сильной связности
  5. Эйлеровы циклы

Лекция C: Графы (Алексей Тимофеев)

  1. Неориентированные графы
    1. точки сочленения
    2. компоненты вершинной двусвязности
    3. мосты
    4. компоненты реберной двусвязности
  2. Ориентированные графы
    1. топологическая сортировка
    2. компоненты сильной связности
    3. алгоритм Дейкстры
      1. простая реализация
      2. релизация с помощью кучи
    4. алгоритм Флойда

Лекция AB: Потоки минимальной стоимости, задача о назначениях (Антон Фонарев)

  1. Потоки в сетях
    1. определения
    2. обозначения
  2. Задача о максимальном потоке
    1. остаточные сети
    2. дополняющие пути
    3. разрезы
    4. теорема Форда-Фалкерсона
    5. метод Форда-Фалкерсона
  3. Реализация метода Форда-Фалкерсона
    1. алгоритм Эдмондса-Карпа
    2. алгоритм масштабирования
  4. Поток заданной величины минимальной стоимости
    1. постановка задачи
    2. согласованная декомпозиция
    3. алгоритм нахождения потока заданной величины минимальной стоимости
    4. потенциалы Джонсона
  5. Задача о назначениях
    1. венгерский алгоритм
    2. нормальное решение

29 марта

Семинар D: Задачи на графы (Маргарита Трухина)

Семинар C: Задачи на графы (Виктор Матюхин, Александр Чернов)

Лекция AB: Динамика по профилю (Борис Василевский)

  1. Задача о замощении домино
    1. Профили, базовая линия
    2. Рекуррентное соотношение для задачи о замощении
    3. Решение задачи о замощении с использованием ДП по профилю
  2. Связь ДП по профилю и линейной алгебры
    1. Рекуррентное соотношение в ДП по профилю как умножение матрицы на вектор
    2. Быстрое возведение в степень
    3. Использование быстрого возведения матрицы в степень для существенно несимметричных задач
  3. Задача о симпатичных узорах
  4. Задача о расстановке королей
    1. Постановка задачи
    2. Эффективная нумерация профилей
  5. Задача о расстановке коней
    1. Постановка задачи
    2. Эффективное хранение разреженных матриц
    3. Графовая интерпретация ДП по профилю
  6. Быстрое ДП по профилю
    1. Изломанный профиль
    2. Правила перехода в быстром ДП по профилю для задачи о замощении домино

30 марта, четверг

Лекция CD: Динамическое программирование (Денис Кириенко)

  1. Что такое динамика. Когда нужна, а когда не нужна динамика.
  2. Основные применения динамики:
    1. Подсчет количества объектов. Пример: числа Каталана.
    2. Нахождение минимального (максимального) решения. Пример: задача "Банкомат".
    3. Позиционные игры. Пример: задача "Игра с датами".
  3. Задача "Ход конем".
  4. Задача "восстановление скобок": динамика по длине и балансу.
  5. Задача "пьяный студент": динамика по длине и балансу.
  6. Задача быстрого нахождения k-й правильной скобочной последовательности.
  7. Задача рюкзака и связные задачи (выбор камней по заданной суммарной массе, задача "Копилка").
  8. Задача умножения большого числа матриц – динамика по интервалам A(i..j).
  9. Задача получения максимального палиндрома из данной строки (динамика по подстрокам).
  10. Нахождение наибольшей общей подпоследовательности.
  11. Нахождение наибольшей возрастающей подпоследовательности за время O(n2) и O(n log n).
  12. Динамика от >2 параметров: задача покупки товаров с системой скидок.
  13. Метод динамики "сверху вниз" (рекурсия + memorization).

Лекция C++: STL (Дмитрий Королев)

План лекции?