Алгоритмы. Олимпиадное программирование для школьников

Полное расписание курса

Продолжительность: 2 года, 1 раз в неделю (сентябрь-май)

По сути, это "соль" программирования, задачи сортировки, поиска, обхода "дерева", "рюкзак", "коммивояжер" и т.п.

Курс рассчитан на 2-х летний цикл обучения.

Каждый модуль курса рассчитан на полугодие, 12 занятий по два урока в неделю (1,5 астрономических часа).

Курс рекомендован учащимся 9–10-х классов, которые обладают базовыми знаниями по программированию в объеме любого из курсов: "Основы программирования на Java" или "Основы программирования в 1С:Предприятие 8" 

На курсе:

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

- Познакомитесь с тестирующей системой Ejudge, в которой проходят  все крупнейшие соревнования по спортивному программированию.

- Сможете на лету решать основные задачи из области арифметики: разложение числа на цифры, на простые множители, делимость, арифметика остатков.

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

- Узнаете, как легко решать задачи обработки матриц: линейный поиск, переворот, максимумы и минимумы.

- Изучите различные методы сортировки, в том числе использующие тонкие оптимизации.

- Приступите к основам высшего пилотажа в программировании – алгоритмам обработки графов, стеков и очередей.

- Полученных знаний и навыков хватит, чтобы начать выступать на олимпиадах по программированию.

Занятие №1. Знакомство
Алгоритмы
Тестирующая система

Занятие №2. Типы данных и отладка
Типы данных в Java
Примитивные типы
Объекты
Классы-обертки
BigInteger и BigDecimal
Отладка

Занятие №3. Решение задач из области арифметики
Проверка на четность
Немного теории
Цифры числа
Получение цифр числа
Проверка на простоту
Сумма делителей
Количество делителей
Разложение на простые множители

Занятие №4. НОД(GCD) и НОК(LCM)
Немного теории
Немного о задачах

Занятие №5. Однопроходные алгоритмы
Чтение
Сумма элементов
Максимум из всех
Максимум из четных
Второй максимум
Немного о задачах
Чтение больших объемов данных
Пример использования класса StreamTokenizer для быстрого чтения
последовательности чисел

Занятие №6. Массивы
Создание массива
Ввод (считывание) массива из N элементов
Вывод всех элементов массива
Поиск максимума
Поиск индекса максимального
Поиск индекса заданного числа в массиве
Вывод массива в обратном порядке
Косвенная адресация

Занятие №7. Сортировка массива
Сортировка выбором (метод минимума)
Немного теории
Метод сортировки обменами (метод пузырька)

Занятие №8. Символы и строки в Java
Символы
Класс String
Создание строки
Чтение строки
Длина строки
Сравнение строк
Добавление к строке
Преобразование различных типов в строку и обратно
Извлечение символа и подстроки
Поиск в строке
Функции замены
Разворот строки

Занятие №9. Двумерные массивы
Создание и «стандартное» чтение
Вывод массива в виде таблицы
Cумма всех элементов
Сумма элементов главной диагонали
Неровные массивы

Занятие №10. Графы I. Определения, хранение
Немного теории
Основные понятия
Деревья
Способы хранения графов
Способ №0. Иногда граф можно вообще не хранить специальным образом
Способ №1. Матрица смежности
Способ №2. Список ребер
Способ №3. Списки смежности

Занятие №11. Стек и очередь
Стек (Stack)
Очередь (Queue)

Занятие №12. Графы II. Поиск в ширину
BFS (Breadth-first search)
BFS в графе, заданном матрицей смежности G
Применения алгоритма поиска в ширину
Поиск кратчайших путей из данной
Немного теории
Поиск компонент связности

Алгоритмы. Олимпиадное программирование. Модуль 2

Занятие 1. Вспомнить всё!

Занятие 2. Рекурсия I

Занятие 3. Рекурсия II

Занятие 4. Алгоритм поиска в глубину (DFS – Depth First Search)

Занятие 5. Применения поиска в глубину

Занятие 6. Сортировка слиянием

Занятие 7. Быстрая сортировка

Занятие 8. Командная олимпиада

Занятие 9. Динамическое программирование I.

Занятие 10. Динамическое программирование II

Занятие 11. Системы счисления

Занятие 12. Дорешивание

Алгоритмы. Олимпиадное программирование. Модуль 3.

Занятие 1. Вспомнить всё - 2!

Занятие 2. Основные понятия и формулы комбинаторики Правила суммы и произведения Формулы основных комбинаторных чисел Теоретические задачи

Занятие 3. Генерация комбинаторных объектов Универсальный алгоритм генерации всех заданных объектов Генерация следующей перестановки в лексикографическом порядке Генерация перестановки по номеру Генерация номера размещения по объекту

Занятие 4. Задачи динамического программирования I (НВП) Наибольшая возрастающая подпоследовательность Код на Java Вывод самой НВП Сложность алгоритма поиска и вывода НВП

Занятие 5. Динамическое программирование II (НОП)

Занятие 6. Задачи динамического программирования III (расстояние Левенштейна) Определение и применения Редакционное предписание

Занятие 7. Алгоритм Флойда-Уоршалла Взвешенные графы Описание алгоритма Рекуррентное соотношение Код алгоритма Восстановление ответа Циклы отрицательного веса

Занятие 8. Алгоритм Дейкстры Описание алгоритма Пример работы Код алгоритма Сложность алгоритма Вывод ответа

Занятие 9. Олимпиада Состав команды Подготовка к соревнованиям Стратегия и тактика поведения во время тура Рекомендации по процессу практического программирования олимпиадной задачи Как бороться со штрафным временем Как потратить последние 15 минут тура Как вести себя после тура

Занятие 10. Бинарный поиск Сложность метода Метод дихотомии Бинарный поиск по ответу

Занятие 11. Игры I. Ним Ограничения Выигрышные и проигрышные позиции Игра "Ним"

Занятие 12. Игры II. Сумма игр Постановка задачи Сведение любой игры к Ниму Функция Шпрага-Гранди для одной игры Функция Шпрага-Гранди для суммы игр Суммы игр "на практике" Реализация

Занятие 13. Геометрия. Основы Действительные числа Основные объекты Линейное взаиморасположение объектов Углы GeomVis

Занятие 14. Геометрия. Окружности и многоугольники Окружность Многоугольник Выпуклость многоугольника Площадь многоугольника GeomVis

Занятие 15. Выпуклая оболочка Наивный алгоритм Алгоритм Джарвиса Алгоритм Грэхэма

Занятие 16. Куча (HEAP) Устройство Реализация Пирамидальная сортировка Очередь с приоритетами