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

Курс рекомендован учащимся 9–10-х классов.

Занятия рассчитаны на 3 модуля (по 24 ак. часа)

В каждом модуле 12 занятий по 2 академических часа.

Занятия проводятся 1 раз в неделю по 2 ак. часа с сентября-октября по апрель-май в рабочие или выходные дни. Каждый слушатель обеспечен компьютером. Группы до 10 человек.

По окончании обучения выдается свидетельство 1С Центра сертифицированного обучения 1С.

Стоимость обучения: 1 модуль (24 ак.часа, 12 занятий по 2 ак.часа) – 5400 руб. При оплате обучения единовременно за 2 модуля скидка – 10%! Для слушателей 2-го и последующих модулей – скидка 10%!

Договор на оказание платных образовательных услуг: скачать в PDF

Реквизиты для оплаты обучения:  cкачать в PDF

На курсе:

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

Программа Модуля 1. 

Занятие №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)

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