С 21 марта 2007 года на базе школы №179 МИОО прошли Московские учебно-тренировочные сборы ко Всероссийской олимпиаде по информатике. По результатам сборов сформирована команда г. Москвы на Всероссийскую олимпиаду по информатике.

Команда г. Москвы успешно выступила на финале Всероссийской олимпиады школьников по информатике, завоевав 17 дипломов – рекордное количество для одного региона за всю историю проведения олимпиады. Поздравляем победителей:

Дипломы I степени
1. Новиков Константин (11 класс, СУНЦ МГУ) – 1 место
2. Колосов Андрей (11 класс, ЦО "57 школа") – 7 место
3. Кумок Аким (10 класс, школа-интернат "Интеллектуал") – 9 место

Дипломы II степени
1. Махлин Антон (11 класс, гимназия 1543)
2. Махлин Игорь (11 класс, гимназия 1543)
3. Богатый Иван (11 класс, школа-интернат "Интеллектуал")
4. Рощупкин Александр (11 класс, гимназия 1543)
5. Богатый Антон (9 класс, школа-интернат "Интеллектуал")
6. Ульянов Николай (11 класс, СУНЦ МГУ)
7. Пахомов Фёдор (11 класс, ЦО "57 школа")
8. Парамонов Сергей (10 класс, СУНЦ МГУ)

Дипломы III степени
1. Рухович Филипп (9 класс, МССМШ им. Гнесиных)
2. Аноховский Сергей (11 класс, СУНЦ МГУ)
3. Ткачёв Владимир (11 класс, ЦО 218)
4. Перту Алексей (11 класс, СУНЦ МГУ)
5. Игнатьев Олег (10 класс, СУНЦ МГУ)
6. Остроумов Олег (11 класс, лицей "Вторая школа")

Результаты олимпиады

Информация для включенных в состав команды о поездке на Всероссийскую олимпиаду?

Открыто дорешивание всех туров для участников сборов. Вход по ссылкам в архиве.

Сборы организовали и провели

Денис Кириенко – руководитель сборов, руководитель команды г. Москвы на Всероссийской олимпиаде по информатике (школа 179, МИОО).

Владимир Гуровиц – руководитель команды г. Москвы на Всероссийской олимпиаде по информатике (школы 218 и 2007, МЦНМО).

Иван Ященко – исп. директор Московского центра непрерывного математического образования, зав. кафедрой математики Московского института открытого образования, зам. председателя оргкомитета Московской олимпиады по информатике

Виктор Матюхин – научный руководитель команды г. Москвы на Всероссийской олимпиаде по информатике, председатель методической комиссии Московской олимпиады по информатике, председатель научного комитета Всероссийской олимпиады по информатике (до 2005 года), завуч Летней компьютерной школы (ВМК МГУ, гимназия 1543, МЦНМО)

Людмила Владимировна Стрельникова – ответственная за организацию питания и хозяйственную часть (школа 179).

Андрей Станкевич – председатель Научного комитета Всероссийской олимпиады по информатике, председатель жюри Всероссийской командной олимпиады школьников, преподаватель Летней компьютерной школы (СПбГУ ИТМО, Санкт-Петербург)

Елена Владимировна Андреева – председатель жюри Московской олимпиады по информатике, член жюри Всероссийской олимпиады по информатике, зав. кафедрой информатики СУНЦ МГУ

Виталий Гольдштейн – победитель Всероссийской олимпиады школьников, призер (золотая медаль) Международной олимпиады школьников, член Научного комитета Всероссийской олимпиады, преподаватель Летней компьютерной школы (Саратовский государственный университет)

Борис Василевский – призер Всероссийской олимпиады по информатике, член Научного комитета Всероссийской олимпиады по информатике (мехмат МГУ), преподаватель Летней компьютерной школы

Максим Бабенко – победитель Международной олимпиады школьников по информатике, тренер команды России на Международной олимпиаде, преподаватель Летней компьютерной школы (мехмат МГУ)

Михаил Густокашин – преподаватель ЦДО "Дистантное обучение", призер Всероссийской олимпиады по информатике (ВМК МГУ)

Антон Фонарёв – победитель Всероссийской олимпиады школьников по информатике (мехмат МГУ)

Алексей Гусаков – призер Всероссийской олимпиады по информатике (мехмат МГУ)

Вадим Антонов – победитель Всероссийской олимпиады по информатике (ВМК МГУ), член Научного комитета Всероссийской олимпиады по информатике, преподаватель Летней компьютерной школы

Маргарита Трухина – преподаватель Летней компьютерной школы (ВМК МГУ)

Илья Корнаков – победитель Всероссийской олимпиады по информатике (мехмат МГУ)

Андрей Шестимеров – преподаватель Мытищинской школы программистов (ВМК МГУ), преподаватель Летней компьютерной школы

Алексей Лахно – победитель Всероссийской олимпиады по информатике, член Научного комитета Всероссийской олимпиады по информатике (мехмат МГУ), преподаватель Летней компьютерной школы

Роман Жуйков – призер Всероссийской олимпиады по информатике (ВМК МГУ)

Артем Ворожцов – тренер студенческих команд МФТИ

Арсений Климовский – победитель Всероссийской олимпиады школьников (мехмат МГУ)

Сергей Грибовский – победитель Всероссийской олимпиады школьников (мехмат МГУ)

Владимир Батаев – призер Всероссийской олимпиады школьников (мехмат МГУ)

Дорешивание практических туров

Лекции

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

Лекция А. Длинная арифметика возвращается

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(NlogN)
3. Бинарный поиск в упорядоченном массиве.
4. Бинарный поиск для монотонных функций. Разбор задачи "Кубический корень".
5. Бинарный поиск по ответу.
6. Разбор задачи "Очень легкая задача" (Москва, 10-11 класс, 2007)
7. Разбор задачи "Автобус" (Украинская, 2000)

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

Лекция А. Теория групп

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 марта, пятница

Лекция А. O полноте систем функций алгебры логики

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

Лекция А. Игры-2

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

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

1. Введение
   1. Уравнения фигур (представление прямой, окружности, плоскости).
   2. Вектор. Скалярное, векторное произведение.
   3. Расположение точки относительно прямой и плоскости.
2. Расстояния
   1. От точки до точки, прямой, отрезка, плоскости, окружности.
   2. Между отрезками в плоскости.
3. Проверка на пересечение.
   1. Прямых, отрезков, окружностей.
   2. Окружности с прямой и отрезком.
4. Отсечение выпуклого многоугольника полуплоскостью.
   а. Простейший алгоритм нахождение областей Вороного (O(N³), каждая область за O(N²))
   
   1. Пересечение выпуклых многоугольников. (за O(N²) и за O(N))
5. Численные методы.
   1. Бинарный поиск
      1. Окружность наибольшего радиуса, свободная от точек (O(N²log 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 марта, воскресенье

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

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 марта, вторник

Лекция А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 марта, среда

Лекция АB. Грамматики

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

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

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

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

Лекция А. Подграф наибольшей плотности

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 марта, пятница

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

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

лекция B: "Потоки" (В.Гольдштейн)

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

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