===Результаты и условия задач===
#|
||4 ноября - командный легкий тур|((http://server.179.ru/ejudge/standings/000045.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000045.ps PS))||
||4 ноября - командный сложный|((http://server.179.ru/ejudge/standings/000046.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000046.ps PS))||
||5 ноября - личный легкий тур|((http://server.179.ru/ejudge/standings/000048.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000048.doc DOC))||
||5 ноября - личный сложный тур|((http://server.179.ru/ejudge/standings/000047.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000047.ps PS))||
||6 ноября - командная олимпиада Санкт-Петербурга и Кирова, легкий тур - Киров|((http://server.179.ru/ejudge/standings/000050.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000050.ps PS))||
||6 ноября - командная олимпиада Санкт-Петербурга и Кирова, сложный тур - ACM|((http://server.179.ru/ejudge/standings/000049.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000049.ps PS))||
||7 ноября - личный тур (задачи A-G - легкие, следующие - сложные)|((http://server.179.ru/ejudge/standings/000052.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000052.doc DOC))||
||8 ноября - легкий командный тур|((http://server.179.ru/ejudge/standings/000053.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000053.ps PS))||
||8 ноября - сложный командный тур|((http://server.179.ru/ejudge/standings/000054.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000054.ps PS))||
||9 ноября - легкий личный тур|((http://server.179.ru/ejudge/standings/000055.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000055.doc DOC))||
||9 ноября - сложный личный тур|((http://server.179.ru/ejudge/standings/000056.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000056.doc DOC))||
||11 ноября - легкий командный тур|((http://server.179.ru/ejudge/standings/000057.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000057.rtf RTF))||
||11 ноября - сложный командный тур|((http://server.179.ru/ejudge/standings/000051.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000051.ps PS))||
||12 ноября - легкий личный тур на структуры данных|((http://server.179.ru/ejudge/standings/000058.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000058.doc DOC))||
||12 ноября - сложный личный тур|((http://server.179.ru/ejudge/standings/000060.html Результаты))|Условия: ((http://server.179.ru/ejudge/statements/000060.doc DOC))||
|#
===Программы лекций===
====4 ноября (суббота)====
=====Лекция С: Как эффективно и без ошибок решать олимпиадные задачи по информатике=====
1. Порядок решения олимпиадной задачи во время тура
2. Оптимальное использование типов данных
3. Программистские ошибки и способы их контроля
4. Эффективное управление директивами компилятора
=====Лекция B: Инварианты. Введение в нимберсы. Динамическое программирование и метод деления пополам.=====
Понятие инварианта. Инвариант в математике. Математическая задача о вещественных числах.
Понятие инварианта а программировании на примере задачи поиска 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 ноября (воскресенье)====
=====Лекция С: Динамическое программирование=====
1. Подсчет числа сочетаний: факториалы, рекурсия, динамическое программирование.
2. Общие принципы построения динамического программирования.
3. Основные применения динамического программирования:
а. Подсчет количества объектов (задача на количество маршрутов на сетке).
б. Нахождение минимального (максимального) решения (задача на минимальную стоимость проезда на сетке).
в. Позиционные игры (задача "Игра с датами").
4. Задача "Банкомат".
5. "Рюкзак".
=====Лекция BС: Введение в геометрию=====
1. Координаты и векторы.
2. Ориентированная площадь.
3. Уравнения линий.
=====Лекция А: Приближение функций=====
1. Интерполяционные многочлены Лагранжа и Ньютона.
2. Вычисление многочлена Ньютона через разделенные разности.
3. Выбор узлов интерполяции для уменьшения погрешности.
4. Кусочная интерполяция. Сплайны - кубические, параболические.
====6 ноября (понедельник)====
=====Лекция С: О пользе и вреде рекурсии=====
1. О вреде рекурсии ;)
2. О пользе рекурсии :)
3. Backtracking (Перебор с возвратом)
=====Лекция B: Максимальный поток и максимальное паросочетание=====
1. Максимальный поток.
а) постановка задачи.
б) сети с несколькими источниками и стоками.
в) алгоритм Форда-Фалкерсона.
г) алгоритм Эдмонса-Карпа.
2. Максимальное паросочетание.
а) постановка задачи для двудольного графа.
б) сведение задачи о максимальном паросочетании в двудольном графе к задаче о нахождении максимального потока.
3. Решение задач сведения к задаче о построении максимального потока.
=====Лекция A: Динамика по профилю. Динамика по изломанному профилю. Трудные задачи на графы=====
====7 ноября (вторник)====
10.00-15.30 Личный практический тур (с перерывом на обед) ((http://server.179.ru/cgi-bin/team?contest_id=52 сдача решений)) ("одно окно") ((http://server.179.ru/ejudge/standings/000052.html таблица результатов))
16.00-17.30 Лекции (все лекции читаются параллельно)
=====Лекция С: Рекурсия и динамическое программирование=====
1. Разбор задач прошедшего тура.
=====Лекция B: Дерево интервалов. (Система непересекающихся множеств)=====
1. Дерево интервалов.
2. Дерево максимумов.
3. Дерево отрезков.
4. Быстрый подсчет площади объединения прямоугольников.
5. Другие примеры использования.
(Система непересекающихся множеств)
=====Лекция A: Производящие функции=====
1. Что такое производящие функции.
2. Степенные производящие функции.
3. Экспоненциальные производящие функции.
4. Примеры задач.
====8 ноября (среда)====
=====Лекция С: Поиск кратчайших путей в графах=====
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 ноября (четверг)====
=====Лекция C: Метод рекурсивного спуска=====
1. Задача о вычислении значения арифметического выражения
2. Формулы Бэкуса-Науэра для арифметического выражения
3. Написание программы методом рекурсивного спуска.
4. Обощения (отслеживание ошибок, вычисление логических выражений, вычисление переменных, функций, возведение в степень).
5. Пара слов о синтаксическом разборе. Формализация понятия "число".
=====Лекция B: Геометрия=====
Вычислительная планиметрия. Векторы. Площадь. Полярный угол. Построение выпуклой оболочки - алгоритмы Грэхема, Джарвиса.
=====Лекция A: Минимальный разрез в графе=====
1. Минимальный s-t разрез в графе, связь с максимальным потоком
2. Постановка задачи, наивный алгоритм
3. Решение за O(n) поисков минимальных s-t разрезов
4. Алгоритм проталкивания предпотока, его выгодная модификация
5. Алгоритм поиска минимального разреза в графе
6. Временные оценки для различных реализаций
====11 ноября (суббота)====
=====Лекция C: Структуры данных - 1=====
1. Списки: представление в массиве, списки в динамической памяти; добавление, удаление, поиск элемента; двусвязные и кольцевые списки.
2. Стеки: реализация на массивах, реализация на списках.
3. Очереди: реализация на массиве (циклический буфер), на списках.
4. Деки
5. Бинарный поиск в отсортированном массиве
6. Поиск k-го по величине элемента в массиве
=====Лекция C++: Использование библиотеки STL=====
1. Основные контейнеры: vector, stack, queue, map, set, multiset, priority_queue, back(), front() и top()
2. Работа с map/set: count, find, operator [] для map, удаление элементов, использование итераторов, *begin() и *rbegin()
3. Строка и строковый поток: string::substr, istringstream, ostringstream
4. Основные алгоритмы: min/max/swap, sort, stable_sort, next_permutation / prev_permutation, min_element, max_element, reverse, copy, generate, generate_n, find, count, find_first_of, count_if, accumulate, inner_product, binary_search, lower_bound, equal_range
5. Хитрости: vector::reserve, container.swap
6. Полезные мелочи: копирование объектов и const references, #include-файлы, ">>", typedef, make_pair, typeof в GNU
=====Лекция A: Дерево Фенвика. RMQ, LCA=====
1. Дерево Фенвика
2. Двумерное дерево Фенвика
3. Метод сжатия координат
4. задача о Парковке
5. FIND_LESS_THAN на отрезке
6. RMQ <O(n*log n), O(1)>
7. LCA <O(n*log n), O(log n)>
====12 ноября (воскресенье)====
=====Лекция C: Структуры данных - 2=====
1. Heap, Heap-sort и очередь с приоритетами
2. Хеш-таблицы: хеш-функции, методы разрешения коллизий, хеширование с открытой адресацией, двойное хеширование
(3. Двоичные деревья поиска: поиск, добавление и удаление, сбалансированные деревья.)
=====Лекция B: Методы решения геометрических задач=====
1. Теорема Хелли
2. Метод границ
3. Метод деления на 2^^dimension^^
Будут рассмотрены классические задачи
1. Разместить круглый бассейн максимального размера среди колонн.
2. В данном наборе линейных неравенств найти максимальное количество совместных.
=====Лекция A: Криптография=====
1. Постановка задачи. Криптография и стеганография.
2. Классические криптографические алгоритмы: шифры замены и перестановки.
3. Абсолютно стойкий шифр и почему им не пользуются.
4. Современная симметричная криптография: потоковые и блочные шифраторы (ГОСТ 28147-89).
5. Хэш-функция SHA1.
6. Современная криптография с открытым ключом: RSA, электронная подпись, открытое распределение ключей.