Школа179: /Сборы//Сборы / Архив?//Сборы / Архив / 2006 Весна/ПрочитанныеЛекции ...

 
Это старая версия Сборы/Архив/2006Весна/ПрочитанныеЛекции за 2006-03-24 17:43:59..

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

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. Регулярность итерации регулярного языка
    4. Регулярность объединения двух регулярных языков
    5. Регулярность пересечения двух регулярных языков
    6. Распознавание эквивалентности автоматов
  3. Минимизация автомата
    1. Удаление недоcтижимых вершин
    2. Создание одного стока
    3. Определение остаточного языка
    4. Эквивалентность состояний
    5. Склейка эквивалентных состояний
    6. Невозможность дальнейшего уменьшения минимизированного автомата
    7. Различимость состояний экспериментом длины не более N 
    8. Лемма о разрастании
    9. Нерегулярность языка O^n 1^n
    10. Незамкнутость класса регулярных языков относительно взятия подмножества
  4. Грамматики
    1. Определение грамматики, продукции, язык, задаваемый грамматикой, примеры
    2. Контекстно-свободные грамматики
    3. Правосторонние грамматики
    4. Регулярность правосторонних грамматик
    5. Эквивалентность правосторонних грамматик и автоматов
  5. Регулярные выражения
    1. Определение регулярных выражений
    2. Регулярность регулярных языков
    3. Эквивалентность регулярных выражений и автоматов (без доказательства)
  6. Разбор арифметических выражений
    1. Разбор регулярных языков
    2. Выделение лексем
    3. Формулы Бэкуса-Наура для арифметических выражений
    4. Написание программы методом рекурсивного спуска

 
Файлов нет.[Показать файлы/форму]
2006-03-24 17:43:59 | Владелец: Denis Kirienko | Версия для печати | Поиск:
Портал | Каталог | Изменения | Комментарии | Пользователи | Регистрация | Вход:   Пароль: