Школа179: /Сборы//Сборы / Архив?/2007Весна ...

 
Это старая версия Сборы/Архив/2007Весна за 2007-04-05 17:36:30..

Дорешивание


21 марта – тренировочный тур AВходРезультатыУсловия: DOC
21 марта – тренировочный тур BВходРезультатыУсловия: DOC
21 марта – тренировочный тур CВходРезультатыУсловия: DOC

21 марта, среда

09–30 – 10–00 регистрация участников, открытие сборов
10–00 – 15–00 тренировочный практический тур (второй завтрак во время тура)
Вход для участников: тур А тур B тур C
Результаты: тур А тур B тур C
15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция А. Длинная арифметика возвращается
1. Алгоритм Карацубы

  1. Идея, сложность
  2. Реализация, оптимизации

2. Дискретное преобразование Фурье

  1. Теория
    1. Введение (комплексные числа, комплексная экспонента, корни из единицы и прочие простые сущности из математики)
    2. Многочлены
    3. Дискретное преобразование Фурье (формальное определение, терминология)
    4. Обратное преобразование
  2. Алгоритмы
    1. Алгоритм Cooley-Tukey
    2. Разбор реализации
    3. Подключение к длинной арифметике

3. Разбор задач

  1. Летние учебно-тренировочные сборы кандидатов в сборную России по информатике, Малоярославец, 27 июня 2006 года, Задача A “Дырявая лента”
  2. St. Petersburg SU Contest, Petrozavodsk Summer Trainings, August 30, 2006, Problem H “Robot's DNA”

4. Литература


Лекция B. C++ Standard Template Library (STL)
1. Понятие шаблона (template)
2. Контейнеры и итераторы

  1. Что такое итератор
  2. Стандартные контейнеры
    1. vector< >
    2. set< >
    3. map< >
    4. stack< >
    5. queue< >
    6. priority_queue< >
  3. Применения контейнеров

3. Обобщённые алгоритмы (<algorithm>)

  1. Принципы работы обобщённых алгоритмов
  2. Сортировка: sort(), stable_sort(), nth_element()
  3. Бинарный поиск: binary_search(), equal_range(), lower_bound(), upper_bound()
  4. Перестановки: next_permutation(), prev_permutation()
  5. Прочие алгоритмы: min(), max(), swap(), reverse(), copy(), max_element(), min_element(), for_each(), search(), find_if().
  6. Использование обобщённых алгоритмов

4. Bitset< >
5. Объекты-функции (“функторы”) и их использование

  1. Понятие объекта-функции
  2. Стандартные объекты-функции (<functional>)

6. Эффективное использование STL: реализация алгоритма Дейкстры с кучей
7. Чего нет в STL


Лекция C. Задачи поиска
1. Поиск в неупорядоченных массивах
2. Порядковые статистики за O(Nlog N?)
3. Бинарный поиск в упорядоченном массиве.
4. Бинарный поиск для монотонных функций. Разбор задачи «Кубический
корень».
5. Бинарный поиск по ответу.
6. Разбор задачи «Очень легкая задача» (Москва, 10–11 класс, 2007)
7. Разбор задачи «Автобус» (Украинская, 2000)

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

10–00 – 15–00 практический тур (второй завтрак во время тура)
Вход для участников: тур А тур B тур C
Результаты: тур А тур B тур C
15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция
Лекция А. Теория групп
1. Группа, смежные классы, теорема Лагранжа
2. Группа перестановок, циклическая группа, группа преобразований
3. Действия групп, орбиты, стабилизаторы
4. Формула Бернсайда, примеры.


Лекция B. Алгоритмы на строках
1. Алгоритм Кнута-Морриса-Пратта

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

2. Алгоритм Ахо-Корасик

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

Лекция C. Структуры данных
1. Битовые операции (кратко)
2. Стеки (обзорно, на одномерном массиве)
3. Очереди (обзорно, зацикленная очередь)
4. Деки (зацикленные, с проверкой на отрицательные индексы)
5. Кучи
6. Динамически расширяемые массивы (реализация за N log N расширений)
7. Списки. Сравнение производительности динамических структур.
8. Хеш-таблицы и хеш-функции
9. Механизм вызова функций и рекурсивные функции (использование стека)

23 марта, пятница

10–00 – 15–00 отборочный практический тур (второй завтрак во время тура)
Вход для участников: тур АBC
Результаты: тур АBC
15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция А. O полноте систем функций алгебры логики
1. Способы задания функций алгебры логики
2. Основные функции алгебры логики (дизъюнкция, конъюнкция, отрицание, сумма
по модулю 2, медиана)
3. Представление любой функции с помощью совершеной ДНФ и с помощью
совершенной КНФ
4. Представление функций полиномами Жегалкина
5. Замкнутые классы и полные системы.
6. Определение классов T 0, T 1, L, S, M
7. Доказательство теоремы Поста о полноте системы функций алгебры логики
8. Доказательство предполноты классов T 0, T 1, L, S, M.


Лекция B. Структуры данных
1. Дерево Фенвика

  1. Определение, Построение без использования дополнительной памяти
  2. Обновление
  3. Запрос
  4. Примеры задач
  5. Многомерное дерево Фенвика

2. Дерево отрезков

  1. Определение, примеры
  2. Реализация запроса и обновление снизу
  3. Реализация запроса и обновление сверху
  4. Реализация модификации на отрезке
  5. Задача поиска k-й порядковой статистики на отрезке
  6. Другие примеры задач
  7. Многомерное дерево отрезков

3. *Двойчные деревья поиска. Декартовы деревья.

  1. Определение.
  2. Поиск элемента.
  3. Вставка, удаление.

Лекция С. Игры-1
1. Комбинаторные игры. P-позиции, N-позиции.
2. Subtraction games. (Dynamic subtraction.)
3. Игра Ним. Ним в поддавки.
4. Игры на графах. Функция Шпрага-Гранди. Сумма игр.
5. Разбор задачи «Товарищеская игра».
6. Разбор задачи «Нечестная игра».
7. Задачи «Игра Ioiwari», «Игра Score», «Игра-2».


24 марта, суббота

10–00 – 15–00 тренировочный практический тур (второй завтрак во время тура)
Вход для участников: тур А тур B тур C
Результаты: тур А тур B тур C
15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция А. Игры-2
1. Немного повторения (игры на графах, функция Шпрага-Гранди)
2. Введение в математическую теорию игр

  1. Aнтагонистические игры
    1. Общие факты
    2. Матричные игры
    3. Смешанное расширение игры
    4. Компьютерные методы решения
  2. Позиционные игры
    1. Существование решения
  3. То, о чем вы не слышали в прошлом году
    1. ...
    2. ...
    3. ...
    4. ...

Лекция B. Геометрия
Геометрия.
1. Введение

  1. Уравнения фигур (представление прямой, окружности, плоскости).
  2. Вектор. Скалярное, векторное произведение.
  3. Расположение точки относительно прямой и плоскости.

2. Расстояния

  1. От точки до точки, прямой, отрезка, плоскости, окружности.
  2. Между отрезками в плоскости.

3. Проверка на пересечение.

  1. Прямых, отрезков, окружностей.
  2. Окружности с прямой и отрезком.

4. Отсечение выпуклого многоугольника полуплоскостью.

а. Простейший алгоритм нахождение областей Вороного (O(N3), каждая область за O(N2))
  1. Пересечение выпуклых многоугольников. (за O(N2) и за O(N))

5. Численные методы.

  1. Бинарный поиск
    1. Окружность наибольшего радиуса, свободная от точек (O(N2log N))
    2. «Поворот 2-х векторов»
  2. Тернарный поиск
    1. Выпуклая функция (f(tx + (1-t)y) <= tf(x) + (1-t)f(y))
    2. Сумма выпуклых функций выпукла.
    3. Нахождение наименее удаленной от множества точек в n-мерном пространстве.
    4. Решение, не гарантирующее правильный результат.

Лекция С. Графы-1
1. Понятие графа и основные определения.
2. Обходы графов

  1. BFS 
  2. DFS

25 марта, воскресенье

10–00 – 15–00 отборочный практический тур (второй завтрак во время тура)
Вход для участников: тур AB тур C
Результаты: тур AB тур C
15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция А. Линейное программирование

  1. Полиэдры – определения, свойства.
  2. Постановка задачи линейного программирования.
  3. Симплекс метод.
    1. Аналитическое обоснование.
    2. Табличная реализация.
  4. Двойственность в линейном программировании.
  5. Содержательные примеры.

Лекция B. Перебор
1. Классы P и NP.
2. Метод ветвей и границ.
3. Альфа-бета отсечения
4. Примеры задач и их возможных решений.


Лекция С. Сортировки
1. Сортировка пузырьком
2. Сортировка слиянием (MergeSort)
3. Пирамидальная сортировка (HeapSort)
4. Быстрая сортировка (QuickSort)
5. Сортировка подсчетом
6. Поразрядная сортировка
7. Сравнение производительности сортировок
8. Методы оптимизаций сортировок
9. Примеры задач, использующих сортировку


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

10–00 – 15–00 тренировочный практический тур (второй завтрак во время тура)
Условия задач: Тур ABC
Вход для участников: Тур АBC
Результаты: Тур АBC


15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция АB. Комбинаторная геометрия

  1. Построение выпуклой оболочки.
    1. 3 алгоритма построения (кратко)
    2. Сравнение эффективности и применимости этих алгоритмов
    3. Нижняя оценка сложности
  2. Объединение выпуклых оболочек
  3. Добавление точки в выпуклую оболочку
  4. Удаление точки из выпуклой оболочки (основные идеи)
  5. Построение диаметра множества точек
  6. Задача о картинной галерее
    1. Триангуляция и оценка n/2
    2. Оценка n/3
    3. Оптимальность алгоритма в худшем случае
    4. Двойственный граф
    5. Раскраска в 3 цвета (DFS)
    6. Y-монотонность
    7. Построение триангуляции в общем случае
  7. Разбор олимпиадных задач

Лекция С. Поиск кратчайших путей в графе

  1. Алгоритм Дейкстры
  2. Алгоритм Флойда

28 марта, среда

10–00 – 15–00 тренировочный практический тур (второй завтрак во время тура)
Вход для участников: Тур А (по системе ACM) Тур B (по системе РОИ) Тур C (по системе РОИ)
Результаты: Тур A Тур B Тур C


15–00 – 15–30 обед
15–45 – 16–15 разбор задач
16–15 – 18–00 лекция


Лекция АB. Грамматики
1. Нотация BNF (язык описания грамматик).
2. Задача про сложные скобочки и два её решения

  1. решение, основанное на стеке
  2. решение, основанное на правилах вывода

3. Синтаксическое дерево разбора
4. Задача про расчет сопротивления схемы.
Отображение правил в программный код, осуществляющий синтаксический
разбор.
5. Задача про обобщённый калькулятор.
Приоритет операторов и тип ассоциативности операторов.
Линейный алгоритм построение синтаксического дерева разбора.
6*. Система Bison.


Лекция С. Динамическое программирование
1. Основные определения и принципы
2. Стандартные задачи динамического программирования

а. Наибольшая общая подпоследовательность
б. Наибольшая возрастающая подпоследовательность
в. Задача об оптимальной расстановке скобок
г. Оптимальная триангуляция выпуклого многоугольника

3. Разбор олимпиадных задач

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


Условия задач: Тур АB
Вход для участников: Тур АB Тур C
Результаты: Тур ABТур C


10–30 – 15–30 отборочный практический тур (второй завтрак во время тура)
15–30 – 16–00 обед
16–00 – 17–45 лекция


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


Лекция B. Динамическое программирование по профилю
1. Задача о замощении домино

  1. Профили, базовая линия
  2. Рекуррентное соотношение для задачи о замощении
  3. Решение задачи о замощении с использованием ДП по профилю

2. Связь ДП по профилю и линейной алгебры

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

3. Задача о симпатичных узорах
4. Задача о расстановке королей

  1. Постановка задачи
  2. Эффективная нумерация профилей

5. Задача о расстановке коней

  1. Постановка задачи
  2. Эффективное хранение разреженных матриц
  3. Графовая интерпретация ДП по профилю

6. Быстрое ДП по профилю

  1. Изломанный профиль
  2. Правила перехода в быстром ДП по профилю для задачи о замощении домино

Лекция C. Секретная геометрия, или простые способы решения геометрических задач
1. Выбор структур данных
2. Секретный смысл основных геометрических формул
3. Top secret, или чего не знают даже студенты


30 марта, пятница

ДЛЯ ГРУППЫ А и С
10–00 – 11–45 лекции


лекция A. Суффиксные автоматы (М.Бабенко)

  1. Строки, префиксы, суффиксы, факторы
  2. Боры строк
  3. Несжатые суффиксные деревья, оценки размера, алгоритм построения
  4. Два подхода к уменьшению размера: сжатие и склейка эквивалентных состояний
  5. Суффиксные ссылки на сжатом и несжатом суффиксном дереве
  6. Алгоритм построения сжатого суффиксного дерева за линейное время
  7. Правые контексты, отношение эквивалентности на факторах
  8. Суффиксная функция на факторах и классах эквивалентности
  9. Эволюция отношения эквивалентности
  10. Оценки размера суффиксного автомата
  11. Суффиксные ссылки и суффиксные пути
  12. Алгоритм построения суффиксного автомата за линейное время

лекция C. Комбинаторика (М.Трухина)

  1. Основные определения и правила.
  2. Перестановки.
  3. Генерация объектов
    1. k-элементные подмножества
    2. размещения с повторениями
    3. перестановки

12–00 – 17–30 тренировочный практический тур (второй завтрак и обед во время тура)
Вход для участников: Тур А Тур C
Результаты: Тур A Тур С
17–30 – 18–00 разбор задач двух дней окружной олимпиады (В.Гольдштейн)


ДЛЯ ГРУППЫ B
10–00 – 15–00 Отборочный практический тур (второй завтрак во время тура)
Вход для участников: Тур B
Результаты: Тур B
15–00 – 15–30 Обед
16–00 – 17–30 лекция B: «Потоки» (В.Гольдштейн)
17–30 – 18–00 разбор задач двух дней окружной олимпиады (В.Гольдштейн)

31 марта, суббота

10–00 – 15–00 Тренировочный практический тур (второй завтрак во время тура)
Вход для участников: Тур ABТур C
Результаты: Тур AB Тур С
15–00 – 16–00 Разбор задач, объявление состава команды
16–00 – 16–30 Обед


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