#| ||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. Инвариант в игре ним.
Метод динамического программирования как построение инварианта. Связь между инвариантом и функцией динамики на примере задачи "Покупка билетов". Задача о выборе подмножества элементов массива с максимальной суммой, в котором никакие два элемента не являются смежными.
Метод деления пополам. Минимальная теория, детали реализации. Задача "Провода".
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. Пара слов о синтаксическом разборе. Формализация понятия "число".
=====Лекция 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, электронная подпись, открытое распределение ключей.
---- адрес оригинала: ((/Сборы/Архив/2006Осень/РасписаниеПрошедшихДнейСборов))