Курс «Олимпиадное программирование на Java»

Класс: 8-11

Наставник: Игорь Баранов

Предметные области: Информатика, Математика

Период обучения: 2 года

Курс ориентирован на учащихся 8 – 11 классов с уклоном на информатику и математику. Курс посвящен знакомству с языком программирования Java, изучению базовых алгоритмов для решения тех или иных задач. Навыки, приобретенные на курсе, помогут при поступлении на технические специальности.

Темы

1 год обучения

  1. Встроенные типы данных, операции над ними:
    1. Примитивные типы данных и операции;
    2. Выражения;
    3. Операторы;
    4. Решение задач на логику.
  2. Работа с массивами:
    1. Теоретическая информация по работе с одномерными и многомерными массивами;
    2. Решение задач на работу с массивами.
  3. Сортировки, базовые алгоритмы НОД и НОК
  4. Работа со строками:
    1. Описание строк;
    2. Работа со встроенными методами класса String;
    3. Решение задач со строками.
  5. Объектно-ориентированное программирование в Java:
    1. Описание классов и объектов;
    2. Наследование;
    3. Описание функций и процедур;
    4. Рекурсия.
  6. Основы комбинаторики:
    1. Формулы перестановок, размещений и сочетаний без повторения;
    2. Формулы перестановок, размещений и сочетаний c повторениями;
    3. Решение задач с использованием комбинаторных формул.
  7. Основы динамического программирования:
    1. Описание алгоритмов решения задач при помощи динамического программирования;
    2. Решение типовых задач на динамическое программирование.

* Решение задач ЕГЭ и ОГЭ.

 

2 год обучения

  1. Минимальный остов: алгоритм Прима, Крускала;
    1. Решение задач.
  2. Алгоритмы на строках:
    1. Префикс-функция, алгоритм Кнута-Морриса-Пратта;
    2. Z- функция;
    3. Алгоритмы хэширования;
    4. Суффиксный автомат, нахождение всех подпалиндромов;
    5. Алгоритм Ахо-Корасика;
    6. Суффиксное дерево, Алгоритм Укконена, алгоритм Вейнера.
    7. Решение задач.
  3. Работа со структурами данных:
    1. Sqrt-декомпозиция;
    2. Стеки, очереди;
    3. Дерево фенвика;
    4. Система непересекающихся множеств;
    5. Дерево отрезков;
    6. Решение задач.
  4. Алгоритмы на последовательностях:
    1. Задача RMQ и модификации;
    2. Решение задач.
  5. Алгоритмы на графах:
    1. Поиск кратчайшего пути: алгоритм Дейкстры, алгоритм Форда-Беллмана;
    2. Поиск в глубину, ширину;

Результат обучения

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