Олимпиадное программирование.

Алгоритмы – это “соль” программирования: задачи сортировки,поиска, обхода “дерева”, “рюкзак”, “коммивояжер” и т.п. Курс рассчитан на 2-х летний курс обучения.Каждый модуль курса рассчитан на полугодие,12 занятий по 2 урока в неделю(1.5 астрономических часа).

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

Поэтому было принято решение дополнить курс Стартовым модулем, занятия по которому можно проводить с детьми 7-8 класса, не имеющими предварительной подготовки. Модуль написан с расчетом именно на средний школьный возраст, олимпиадное программирование представляется в нем занимательным занятием, несмотря на обычное отсутствие наглядности в алгоритмическом программировании. При желании, можно начать обучение на курсе и со стартового модуля, предварительной подготовки по нему не требуется.

На курсе:

  • Сможете на лету решать основные задачи из области арифметики: разложение числа на цифры, на простые множители, делимость, арифметика остатков.
  • Освоите классические алгоритмы и хитрые трюки для решения задач на обработку последовательностей.
  • Узнаете, как легко решать задачи обработки матриц: линейный поиск, переворот, максимумы и минимумы.
  • Изучите различные методы сортировки, в том числе использующие тонкие оптимизации.
  • Приступите к основам высшего пилотажа в программировании – алгоритмам обработки графов, стеков и очередей.
  • Вы узнаете, что такое олимпиадное программирование,и в чем заключаются особенности автоматической проверки алгоритмов.
  • Познакомитесь с тестирующей системой Ejudge, в которой проходят  все крупнейшие соревнования по спортивному программированию.
  • Полученных знаний и навыков хватит, чтобы начать выступать на олимпиадах по программированию.

Продолжительность обучения:
4 модуля (2 года)

Программа курса “Алгоритмы. Олимпиадное программирование”.

Занятия рассчитаны на 4 модуля (4 семестра, 2 года)

Приведена программа только первого модуля.

Каждое занятие состоит из небольшой лекции (примерно 30 минут) с разбором простой задачи. В оставшееся время дети самостоятельно решают задачи и проверяют решение, используя систему автоматической проверки программ ejudge, которая применяется на всех олимпиадах по программированию. Преподаватель будет помогать детям и отвечать на их вопросы индивидуально. Ребенок по желанию (его лично и родителей) может продолжать решение дома и проверять решение задач онлайн в системе ejudge, соревнуясь с другими учениками своего клуба и других1С:Клубов программистов. Всего на каждое занятие будет предложено примерно по 10 задач – от простейших до сложных. Сложная задача будет соответствовать олимпиадному уровню (Муниципальные олимпиады, Всероссийская олимпиада). Ребенок не обязательно должен решать все задачи модуля на занятии или дома. Уровень и полноту решения задач определяет сам ребенок и его родители. Если ребенок свободно решает задачи десятого олимпиадного уровня, он может претендовать на хорошие баллы в олимпиаде. Для детей, изъявивших желание участия в олимпиадах, могут быть проведены отдельные занятия (сборы).

 

Модуль 1.

Занятие №1. Знакомство

  • Алгоритмы
  • Тестирующая система

Занятие №2. Типы данных и отладка

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

Занятие №3. Решение задач из области арифметики

  • Проверка на четность
  • Немного теории
  • Цифры числа
  • Получение цифр числа
  • Проверка на простоту
  • Сумма делителей
  • Количество делителей
  • Разложение на простые множители

Занятие №4. НОД(GCD) и НОК(LCM)

  • Немного теории
  • Немного о задачах

Занятие №5. Однопроходные алгоритмы

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

Занятие №6. Массивы

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

Занятие №7. Сортировка массива

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

Занятие №8. Символы и строки в Java

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

Алгоритмы. Олимпиадное программирование. Модуль 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)

  • Устройство
  • Реализация
  • Пирамидальная сортировка
  • Очередь с приоритетами

Обратный звонок по Олимпиадное программирование.

5 + 14 =