Модуль 3

Раздел: Введение в олимпиадное программирование. (28 часов)

1. Введение.

Введение. Виды и типы олимпиад по спортивному программированию.

2. Языки программирования.

Обзор языков программирования семейства С++: Borland C++ 3.1, Microsoft Visual C++ 8.0, Java 2 SDK 1.5 . Обзор языков программирования семейства Pascal: Borland Pascal 7.0, Borland Delphi 7.0, Free Pascal 2.0 .

3. Типы данных. Работа с файлами.

Базовые типы данных: целые, вещественные, строки, массивы. Работа с файлами: чтение и вывод данных. Структура олимпиадной задачи. Классификация задач. Порядок сложности задач.

4. Базовые алгоритмы.

Алгоритмы сортировки массивов: пузырьком, выбором, быстрая сортировка, цифровая сортировка. Алгоритм двоичного поиска. Решение задач.

Раздел: Системы автоматического судейства. (20 часов)

5. Системы самотестирования

Принципы работы системы самотестирования. Системы: T-Run, Checker Федора Меньшикова, система от olympiads.ru

6. Acmp.ru

Знакомство с сайтом http://acmp.ru. Отправка задач в разделе «Архив задач». Участие в личных и командных олимпиадах.

7. Acm.timus.ru

Знакомство с Timus Online Judge - архивом задач с проверяющей системой. Рейтинговая система, статистика, форум. Система командных олимпиад.

8. Olympiads.ru

Олимпиадная информатика olimpiads.ru: структура сайта, система проведения internet-олимпиад.

9. Neerc.ifmo.ru

Раздел сайта для школьников: http://neerc.ifmo.ru/school : архив задач и результатов официальных олимпиад. Участие в личных и командных олимпиадах базового уровня.

Раздел: Структуры данных. (16 часов)

10. Элементарные структуры данных.

Стеки и очереди. Словари и множества. Бинарные деревья. Использование указателей для формирования структур.

11. C++ Standard Template Library.

Понятие шаблона в C++. Основные объекты: стек, очередь, словарь в STL. Использование функций STL для работы со структурами. Преимущества. Примеры.

12. Алгоритмы, использующие структуры.

Разбор алгоритмов решения задач «Карточная колода», «Покраска карты», «Скобки».

Раздел: Теория чисел. (20 часов)

13. Системы счисления.

Свойства систем счисления. Перевод числа из одной системы в другую.

14. Виды чисел и последовательностей.

Простые числа. Поиск простых чисел. Разложение числа на множители. Совершенные числа. Числа Фибоначчи.

15. Целочисленная арифметика.

Наибольший общий делитель и наименьшее общее кратное. Свойства НОД и НОК. Алгоритм Евклида.

16. Длинная арифметика.

Понятие длинной арифметики. Структуры для хранения длинных чисел. Арифметические операции с длинными числами: сложение, умножение, деление и извлечение корня.

Раздел: Комбинаторика. (16 часов)

17. Базовые методики счета.

Классификация комбинаторных задач. Перебор с помощью двоичных чисел. Перестановки. Обратная перестановка. Поиск циклов и порядка перестановки. Задача о счастливых билетах.

18. Биномиальные коэффициенты.

Факториал. A(k,n) и C(k,n). Биномиальные коэффициенты. Вычисление количества комбинаций с использованием сочетаний.

Задача «Великий комбинатор».

19. Рекурсия и перебор.

Прямая и косвенная рекурсия. Примеры. Рекурсивный перебор всех перестановок. Решение задач.

Раздел: Динамическое программирование. (12 часов)

20. Математическая индукция.

Принцип математической индукции. Понятие динамического программирования. Примеры.

21. Рекуррентные соотношения.

Понятие рекуррентного соотношения. Примеры.

22. Решение задач.

Решение задач: «Гвоздики», «Покраска забора», «Лесенка», «Скобочки».

Раздел: Графы. (16 часов)

23. Введение.

Введение: понятие графа, определения. Классификация графов.

24. Структуры данных для графов.

Матрица смежности и таблица ребер. Примеры.

25. Обход графа в ширину.

Волновой алгоритм. Пример поиска кратчайшего пути в лабиринте.

26. Обход графа в глубину.

Рекурсивная реализация обхода графа в глубину. Задача коммивояжера.

27. Алгоритмы с графами.

Алгоритмы Дейкстры и Флойда поиска наикратчайшего пути в графе. Алгоритм Форда-Беллмана релаксации вершин графа. Алгоритм Каскала и Примы построения остова графа.

Раздел: Геометрия. (16 часов)

28. Аналитическая геометрия.

Векторное и скалярное произведения и их свойства. Вычисление площади треугольника. Принадлежность точки треугольнику. Расстояние от точки до прямой.

29. Вычислительная геометрия.

Пересечение отрезков. Площадь многоугольника. Выпуклая оболочка. Теорема Пика.

30. Разбор геометрических задач.

Разбор задач: «Треугольные страны», «Целые точки» и «Дремучий лес».