Модуль 1.1. Изучение основ программирования Python 3.x на основе курса «Поколение Python: курс для начинающих» учащимися 7-9 классов Модуль 1.2 Подготовка к участию ВсОШ по информатике | | | |
1.1 Алгоритмы и их свойства | | Участие в ВсОШ | |
Понятие алгоритма | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Концепции и свойства алгоритмов | Участие в ВсОШ | |
Запись алгоритма на неформальном языке | Участие в ВсОШ | |
Структуры данных | | Участие в ВсОШ | |
Простые базовые структуры | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Множества | Участие в ВсОШ | |
Последовательности | Участие в ВсОШ | |
Списки | Участие в ВсОШ | |
Неориентированные графы | Участие в ВсОШ | |
Ориентированные графы | Участие в ВсОШ | |
Деревья | Участие в ВсОШ | |
Пирамида и дерево отрезков * | Участие в ВсОШ | |
Сбалансированные деревья * | Участие в ВсОШ | |
Хэш-таблицы и ассоциативные массивы * | Участие в ВсОШ | |
Бор * | Участие в ВсОШ | |
Основы анализа алгоритмов | | Участие в ВсОШ | |
Нотация О большое | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Стандартные классы сложности | Участие в ВсОШ | |
Асимптотический анализ поведения алгоритмов в среднем и крайних случаях | Участие в ВсОШ | |
Компромисс между временем и объемом памяти в алгоритмах * | Участие в ВсОШ | |
Использование рекуррентных отношений для анализа рекурсивных алгоритмов * | Участие в ВсОШ | |
NP-полнота * | Участие в ВсОШ | |
Алгоритмические стратегии | | Участие в ВсОШ | |
Алгоритмы полного перебора | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
"Жадные" алгоритмы | Участие в ВсОШ | |
Алгоритмы "разделяй и властвуй" * | Участие в ВсОШ | |
Перебор с возвратом * | Участие в ВсОШ | |
Эвристики * | Участие в ВсОШ | |
Рекурсия | | Участие в ВсОШ | |
Понятие рекурсии | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Рекурсивные математические функции | Участие в ВсОШ | |
Простые рекурсивные процедуры | Участие в ВсОШ | |
Реализация рекурсии | Участие в ВсОШ | |
Стратегия "разделяй и властвуй" * | Участие в ВсОШ | |
Рекурсивный перебор с возвратами * | Участие в ВсОШ | |
Фундаментальные вычислительные алгоритмы | | Участие в ВсОШ | |
Простые численные алгоритмы | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Классические комбинаторные алгоритмы | Участие в ВсОШ | |
Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы) | Участие в ВсОШ | |
Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего. | Участие в ВсОШ | |
Алгоритмы последовательного и бинарного поиска | Участие в ВсОШ | |
Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) | Участие в ВсОШ | |
Сортировка подсчетом за линейное время. | Участие в ВсОШ | |
Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием) * | Участие в ВсОШ | |
Цифровая сортировка * | Участие в ВсОШ | |
Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов * | Участие в ВсОШ | |
Арифметика многоразрядных целых чисел * | Участие в ВсОШ | |
Числовые алгоритмы | | Участие в ВсОШ | |
Разложение числа на простые множители | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Решето Эратосфена | Участие в ВсОШ | |
Алгоритм Евклида | Участие в ВсОШ | |
Расширенный алгоритм Евклида. Способы реализации алгоритма без деления * | Участие в ВсОШ | |
Решение линейных сравнений с помощью алгоритма Евклида * | Участие в ВсОШ | |
Эффективная реализация решета Эратосфена (O(n)) * | Участие в ВсОШ | |
Эффективная проверка числа на простоту * | Участие в ВсОШ | |
Быстрые алгоритмы разложения чисел на простые множители. Ро-эвристика * | Участие в ВсОШ | |
Алгоритмы на строках | | Участие в ВсОШ | |
Поиск подстроки в строке. Наивный метод | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Алгоритмы поиска подстроки в строке за O(N+M) * | Участие в ВсОШ | |
Периодические и циклические строки * | Участие в ВсОШ | |
Алгоритм поиска нескольких подстрок за линейное время * | Участие в ВсОШ | |
Алгоритмы на графах | | Участие в ВсОШ | |
Вычисление длин кратчайших путей в дереве | Дистанционный курс Информатикс (informatics.msk.ru) Практическая работа | Участие в ВсОШ | |
Обход графа в ширину и в глубину | Участие в ВсОШ | |
Способы реализации поиска в ширину (“наивный” и с очередью) | Участие в ВсОШ | |
Проверка графа на связность | Участие в ВсОШ | |
Алгоритмы поиска кратчайшего пути во взвешенных графах | Участие в ВсОШ | |
Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка * | Участие в ВсОШ | |
Циклы отрицательной длины – критерий наличия, поиск * | Участие в ВсОШ | |
Задача о синхронизации времени и задача о системе неравенств * | Участие в ВсОШ | |
Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) * | Участие в ВсОШ | |
Нахождение транзитивного замыкания графа * | Участие в ВсОШ | |
Алгоритмы нахождения взвешенных остовных деревьев* | Участие в ВсОШ | |
Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину * | Участие в ВсОШ | |
Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе * | Участие в ВсОШ | |
Поиск максимального потока в сети * | Участие в ВсОШ | |
Динамическое программирование | | Участие в ВсОШ | |
Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл. | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Задачи с монотонным направлением движения в таблице | Участие в ВсОШ | |
Задача о рюкзаке – решение методом динамического программирования | Участие в ВсОШ | |
Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) * | Участие в ВсОШ | |
Восстановление решения в задачах динамического программирования * | Участие в ВсОШ | |
Общая схема решения задач динамического программирования * | Участие в ВсОШ | |
Алгоритмы теории игр * | | Участие в ВсОШ | |
Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе * | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Оценка позиций. Альфа-бета отсечение * | Участие в ВсОШ | |
Геометрические алгоритмы | | Участие в ВсОШ | |
Алгоритмы определения совпадения точек, лучей, прямых и отрезков | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Представление точек, прямых и отрезков на плоскости | Участие в ВсОШ | |
Нахождение расстояний между объектами на плоскости * | Участие в ВсОШ | |
Алгоритмы определения пересечения отрезков на плоскости * | Участие в ВсОШ | |
Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) * | Участие в ВсОШ | |
Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) * | Участие в ВсОШ | |
Окружности на плоскости, пересечение их с другими геометрическими объектами * | Участие в ВсОШ | |
Эффективный алгоритм нахождения пары ближайших точек на плоскости * | Участие в ВсОШ | |
Основы программирования | | Участие в ВсОШ | |
Языки программирования | | Участие в ВсОШ | |
Классификация языков программирования | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Процедурные языки | Участие в ВсОШ | |
Основы синтаксиса и семантики языков высокого уровня | Участие в ВсОШ | |
Формальные методы описания синтаксиса: форма Бэкуса-Наура * | Участие в ВсОШ | |
Объектно-ориентированные языки * | Участие в ВсОШ | |
Основные конструкции программирования | | Участие в ВсОШ | |
Переменные, типы, выражения и присваивания | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Основы ввода/вывода | Участие в ВсОШ | |
Операторы проверки условия и цикла | Участие в ВсОШ | |
Функции и передача параметров | Участие в ВсОШ | |
Структурная декомпозиция * | Участие в ВсОШ | |
Переменные и типы данных | | Участие в ВсОШ | |
Концепция типа данных как множества значений и операций над ними | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Свойства объявлений (связывание, область видимости, блоки и время жизни) | Участие в ВсОШ | |
Обзор проверки типов | Участие в ВсОШ | |
Типы структур данных | | Участие в ВсОШ | |
Примитивные типы | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Массивы | Участие в ВсОШ | |
Записи | Участие в ВсОШ | |
Стратегии выбора подходящей структуры данных | Участие в ВсОШ | |
Представление данных в памяти * | Участие в ВсОШ | |
Статическое, автоматическое и динамическое выделение памяти * | Участие в ВсОШ | |
Указатели и ссылки * | Участие в ВсОШ | |
Связанные структуры * | Участие в ВсОШ | |
Методы реализации стеков, очередей и хэш-таблиц * | Участие в ВсОШ | |
Методы реализации графов и деревьев * | Участие в ВсОШ | |
Механизмы абстракции. | | Участие в ВсОШ | |
Процедуры, функции и итераторы как механизмы абстракции | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Механизмы параметризации (ссылки и значения) | Участие в ВсОШ | |
Модули в языках программирования | Участие в ВсОШ | |
Особенности программирования фундаментальных алгоритмов. | | Участие в ВсОШ | |
Стратегии решения задач | Дистанционный курс Https://informatics.msk.ru/ Практическая работа | Участие в ВсОШ | |
Роль алгоритмов в процессе решения задач | Участие в ВсОШ | |
Стратегии реализации алгоритмов | Участие в ВсОШ | |
Реализация рекурсии | Участие в ВсОШ | |
Стратегии отладки * | Участие в ВсОШ | |
Модуль 1.3 Подготовка к ОГЭ по информатике | | | |
Запись средствами ИКТ информации об объектах и процессах, создание и обработка информационных объектов | Лекция, практическая работа https://inf-oge.sdamgia.ru/test?theme=7 | | |
Проектирование и моделирование | Лекция, практическая работа https://inf-oge.sdamgia.ru/test?theme=25 | | |
Математические инструменты, электронные таблицы | Лекция, практическая работа https://inf-oge.sdamgia.ru/test?theme=17 | | |
Организация информационной среды, поиск информации» | Лекция, практическая работа https://inf-oge.sdamgia.ru/test?theme=27 | | |
Алгоритмизация и программирован» | Лекция, практическая работа https://kpolyakov.spb.ru/download/volgin152.pdf | | |