Решение олимпиадных задач по программированию

Курс "Решение олимпиадных задач по программированию" направлен на подготовку детей и развитие навыков к решению олимпиадных задач по спортивному программированию, что позволит им успешно участвовать в олимпиадах и даст возможность профессионального развития в этой области. Образовательная программа ориентирована на использование сайта http://acmp.ru в процессе обучения. Основная аудитория - учащиеся 8-11 классов, имеющие базовую подготовку и владеющие одним из языков программирования.

Настоящее методическое пособие не предназначено для самостоятельного изучения предмета, его назначение - это опорный конспект обучающегося в системе очных 2-часовых занятий по 2 занятия в неделю в течении 2 лет. Книга служит методическим обеспечением олимпиадного курса наряду с одноименным названием в разделе "Курсы" сайта "Школа программиста", который содержит набор тематических заданий для практических занятий с возможностью автоматической проверки и контроля выполненных заданий педагогом.

Основное содержание курса - изучение алгоритмов, используемых при решении олимпиадных задач. В методическом пособии представлены как алгоритмические, так и программные решения большого количества задач данного сайта.

Содержание книги

Введение в олимпиадное программирование
    Пример олимпиадной задачи
    Реализация решения задачи «А+В»
Целочисленная арифметика
    Простые числа
    Числа Мерсенна
    Числа Ферма
    Совершенные числа
    НОК и НОД
    Числа Фибоначчи
    Алгоритмы с простыми числами
Алгоритмы сортировки
    Сортировка выбором (SelectSort)
    Сортировка пузырьком (BubbleSort)
    Сортировка в C++
    Сортировка структур в C++
    Сортировка подсчетом (CountSort)
    Пораздрядная сортировка (RadixSort)
    Быстрая сортировка (QuickSort)
    Сортировка слиянием (MergeSort)
Длинная арифметика
    Формы хранения длинных чисел
    Чтение, вывод  и сравнение
    Сложение, вычитание и умножение
    Деление длинного на короткое
    Реализация длинной арифметики на С++
Перестановки
    Понятие перестановки
    Перебор перестановок в C++
    Лексикографический перебор перестановок в Delphi 
    Next_Permutation в Delphi
    Алгоритмы перебора перестановок
Куча – структура данных
    Определение кучи
    Просеивание элемента (Heapify)
    Базовые операции при работе с кучей
    Пирамидальная сортировка (HeapSort)
    Задача «Коммерческий калькулятор»
STL – Standard Template Library
    STL и шаблоны в C++
    Пара (pair)
    Линейный массив (vector)
    Стек (stack)
    Очередь (queue)
    Дек (deque)
    Очередь с приоритетами (priority_queue)
    Строка (string)
    Множество (set)
    Ассоциативный массив (map)
    Алгоритмы (algorithm)
Динамическое программирование
    Факториал и числа Фибоначчи
    Задача «Пицца»
    Задача «Гвоздики»
    Задача «Зайчик»
    Задача «Компьютерная игра»
    Задача «Без двух нулей подряд»
    Задача «Максимальная подпоследовательность»
    Задача «Фермер»
    Задача «Игра-2»
    Задача «Сумма степеней двойки»
    Задача «Ход конем»
    Задача «Зоопарк»
    Задача «Игра в монеты»
    Задача «Шары и коробки»
    Задача «Китайские часы»
    Задача «Трипростые числа»
    Задача «Симпатичные узоры»
    Задача «Количество путей в лабиринте»
    Задача «Космический мусорщик»
    Задача «Объединение блоков»
    Задача «Лесенка»
    Задача «Раз-два, раз-два»
    Задача «Фотограф-зануда»
    Задача «Фермер-2»
    Задача «Счастливые билеты»
Комбинаторика
    Размещения
    Перестановки
    Сочетания
    Вычисление сочетаний
    Субфакториал
    Задача о разбиении числа
    Задача «Великий комбинатор»
    Задача «Волейбол»
Вычислительная геометрия
    Геометрические объекты
    Понятие вектора
    Скалярное и векторное произведение векторов
    Выражение псевдоскалярного произведения
    Полярная система координат
    Поворот точки на плоскости
    Уравнение прямой на плоскости
    Теорема Пика
    Длина объединения отрезков на прямой
    Проверка пересечения двух отрезков
    Пересечение окружности и прямой
    Пересечение двух окружностей
    Площадь многоугольника
    Принадлежность точки многоугольнику
    Методы Джарвиса и Грэхема построения выпуклой оболочки
Строки
    Определения
    Префикс-функция
    Z-функция
    Реализация построения префикс-функции и Z-функции
    Алгоритм Кнута-Морриса-Пратта
    Количество различных подстрок в строке
    Алгоритм Манакера
    Сжатие строки
Полиномиальный хеш
    Кольцо вычетов
    Полиномиальный хеш
    Сравнение строк с помощью хешей
    Подсчет различных строк
    Алгоритм Рабина-Карпа
    Вычисление Z-функции
    Поиск всех палиндромов в строке
    Лексикографически минимальный сдвиг
Структуры данных
    Базовые операции над массивом
    Sqrt-декомпозиция
    Дерево Фенвика
    Двумерное дерево Фенвика
    Sparse Table
    Дерево отрезков
Теория графов
    Понятие графа
    Определения и виды графов
    Способы представления графа
    Матрица весов
    Список дуг
    Описание Бержа
    Список смежности
    Реализация структур для графов в C++
    Поиск в глубину
    Реализация поиска в глубину
    Определение предка вершины в дереве
    Подсчет компонент связности
    Поиск цикла в графе
    Топологическая сортировка
    Задача «Производство деталей»
    Задача о шахматном коне
    Задача коммивояжера
    Поиск в ширину
    Задача «Lines – 2»
    Задача «Алхимия»
    Задача «Лабиринт»
    Алгоритм Флойда
    Алгоритм Форда-Беллмана
    Алгоритм Дейкстры
    Минимальный остов
    Свойства минимальных остовов
    Алгоритм Прима
    Алгоритм Крускала
    Система непересекающихся множеств
    Задача «Минимальный каркас»
    Эйлеров цикл и путь
    Алгоритмы поиска эйлерова цикла
    Задача «Ковбои»
    Задача «Домино»
    Сильная связность графа
    Поиск компонент сильной связности
    Поиск мостов
    Двудольный граф
    Проверка на двудольность и разбиение на доли
    Поиск максимального паросочетания
    Алгоритм Куна
    Задача о назначениях
    Венгерский алгоритм