Школа179: /Сборы//Сборы / Архив?//Сборы / Архив / 2006 Осень/РасписаниеПрошедшихДнейСборов ...

 
Это старая версия Сборы/Архив/2006Осень/РасписаниеПрошедшихДнейСборов за 2006-11-09 18:59:59..

Расписание на 4 ноября (суббота)


10.00 Сбор участников, открытие сборов


10.30–16.00 Командный практический тур (с перерывом на обед)




16.30–18.00 Лекции (все лекции читаются параллельно)

Лекция С: Как эффективно и без ошибок решать олимпиадные задачи по информатике


1. Порядок решения олимпиадной задачи во время тура
2. Оптимальное использование типов данных
3. Программистские ошибки и способы их контроля
4. Эффективное управление директивами компилятора

Лекция B: Инварианты. Введение в numbers. Динамическое программирование и метод деления пополам.


Понятие инварианта. Инвариант в математике. Математическая задача о вещественных числах.


Понятие инварианта а программировании на примере задачи поиска K максимальных элементов в массиве, K кратчайших путей в графе. Расширение понятия инварианта в программировании. Задача о наибольшем произведении (выбор трёх чисел из N) в терминах инвариантов. Инвариант как инструмент доказательного программирования.


Операция XOR. Инвариант в игре ним.


Метод динамического программирования как построение инварианта. Связь между инвариантом и функцией динамики на примере задачи «Покупка билетов». Задача о выборе подмножества элементов массива с максимальной суммой, в котором никакие два элемента не являются смежными.


Метод деления пополам. Минимальная теория, детали реализации. Задача «Провода».

Лекция A: LCS & LIS: advanced algorithms


1. Нахождение lcs за O(nm).
2. Алгоритм Хиршберга для нахождения lcs в линейной памяти, O(nm).
3. Нахождение lcs длины не менее k за O((k – n)m).
4. Нахождение lis за O(n\log n).
5. Нахождение lcs за O(r\log n).


Расписание на 5 ноября (воскресенье)


10.00–15.30 Личный практический тур (с перерывом на обед)




16.00–17.30 Лекции (все лекции читаются параллельно)

Лекция С: Динамическое программирование

1. Подсчет числа сочетаний: факториалы, рекурсия, динамическое программирование.
2. Общие принципы построения динамического программирования.
3. Основные применения динамического программирования:

а. Подсчет количества объектов (задача на количество маршрутов на сетке).
б. Нахождение минимального (максимального) решения (задача на минимальную стоимость проезда на сетке).
  1. Позиционные игры (задача «Игра с датами»).

4. Задача «Банкомат».
5. «Рюкзак».

Лекция BС: Введение в геометрию


1. Координаты и векторы.
2. Ориентированная площадь.
3. Уравнения линий.

Лекция А: Приближение функций


1. Интерполяционные многочлены Лагранжа и Ньютона.
2. Вычисление многочлена Ньютона через разделенные разности.
3. Выбор узлов интерполяции для уменьшения погрешности.
4. Кусочная интерполяция. Сплайны – кубические, параболические.

Расписание на 6 ноября (понедельник)


10.00–15.30 командная олимпиада школьников (с перерывом на обед)


Легкий тур (по Кировской системе): сдача решений таблица результатов
Сложный тур (по системе ACM): сдача решений таблица результатов


16.00–17.30 Лекции (все лекции читаются параллельно)

Лекция С: О пользе и вреде рекурсии

1. О вреде рекурсии ;)
2. О пользе рекурсии :)
3. Backtracking (Перебор с возвратом)

Лекция B: Максимальный поток и максимальное паросочетание


1. Максимальный поток.

а) постановка задачи.
б) сети с несколькими источниками и стоками.
в) алгоритм Форда-Фалкерсона.
г) алгоритм Эдмонса-Карпа.

2. Максимальное паросочетание.

а) постановка задачи для двудольного графа.
б) сведение задачи о максимальном паросочетании в двудольном графе к задаче о нахождении максимального потока.

3. Решение задач сведения к задаче о построении максимального потока.

Лекция A: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы


Расписание на 7 ноября (вторник)


10.00–15.30 Личный практический тур (с перерывом на обед) сдача решений («одно окно») таблица результатов


16.00–17.30 Лекции (все лекции читаются параллельно)

Лекция С: Рекурсия и динамическое программирование: разбор задач

Лекция B: Дерево интервалов. (Система непересекающихся множеств)

1) Дерево интервалов.
2) Дерево максимумов.
3) Дерево отрезков.
4) Быстрый подсчет площади объединения прямоугольников.
5) Другие примеры использования.
(Система непересекающихся множеств)


Лекция A: Производящие функции

1. Что такое производящие функции.
2. Степенные производящие функции.
3. Экспоненциальные производящие функции.
4. Примеры задач.

Расписание на 8 ноября (среда)


10.00–15.30 Командный практический тур (с перерывом на обед)
Легкий тур: сдача решений таблица результатов
Сложный тур: сдача решений таблица результатов


16.00–17.30 Лекции (все лекции читаются параллельно)

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

1. Поиск кратчайших путей во взвешенных графах.
2. Алгоритм Дейкстры
3. Восстановление пути
4. Примеры
5. Дополнение: использование кучи в Алгоритме дейкстры.

Лекция B: Декартово дерево. Бор

1. Декартово дерево

a. Примеры решаемых с его помощью задач
b. Описание свойств
c. Конкретная реализация операций
d. Напоследок: когда не хватает set, map STL

2. Бор

a. Общая идея построения
b. Простейшая реализация
c. Оптимизация предыдущего метода
d. Сжатый бор
e. Разбор задачи «Файловый менеджер» с Всероссийской олимпиады 2006
f. Применение не для строк
g. Построение суффиксного дерева с линейной памятью (?)
h. Вкратце о применении суффиксного дерева (?)

Лекция A: Алгоритмы проверки чисел на простоту и факторизации

1. Тест Соловея-Штрассена.
2. Тест Рабина-Миллера

Расписание на 9 ноября (четверг)


10.00–15.30 Личный практический тур (с перерывом на обед)
Легкий тур: сдача решений таблица результатов
Сложный тур: сдача решений таблица результатов


16.00–17.30 Лекции (все лекции читаются параллельно)

Лекция C: Метод рекурсивного спуска

1. Задача о вычислении значения арифметического выражения
2. Формулы Бэкуса-Науэра для арифметического выражения
3. Написание программы методом рекурсивного спуска.
4. Обощения (отслеживание ошибок, вычисление логических выражений,
вычисление переменных, функций, возведение в степень).
5. Пара слов о синтаксическом разборе. Формализация понятия «число».

Лекция B: Геометрия

Вычислительная планиметрия. Векторы. Площадь. Полярный угол. Построение выпуклой оболочки – алгоритмы Грэхема, Джарвиса.

Лекция A: Минимальный разрез в графе

1. Минимальный s-t разрез в графе, связь с максимальным потоком
2. Постановка задачи, наивный алгоритм
3. Решение за O(n) поисков минимальных s-t разрезов
4. Алгоритм проталкивания предпотока, его выгодная модификация
5. Алгоритм поиска минимального разреза в графе
6. Временные оценки для различных реализаций



 
Файлов нет.[Показать файлы/форму]