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

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

Расписание на 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: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы



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