Файл: Подготовка школьников к участию в олимпиадах по информатике. Подготовка и проведение олимпиад по информатике.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 14
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Подготовка школьников к участию в олимпиадах по информатике.
Подготовка и проведение олимпиад по информатике.
Сухов В.Б., к.ф.-м.н., член жюри регионального этапа, член региональной п.м.к.,
председатель жюри краснодарского муниципального этапа,
председатель краснодарской муниципальной п.м.к.
Всероссийской олимпиады школьников по информатике тренер краснодарских краевых и городских сборов,
руководитель Краснодарской школы программирования
Всероссийская олимпиада школьников по информатике
Этап
5 – 6 класс
7 – 8 класс
9 – 11 класс
Школьный
+
+
+
Муниципальный
-
+
+
Региональный
-
-
+
Заключительный
-
-
+
Кол-во участников заключительного этапа
Регион
2014
2015
2016
2017
2018
В год в
средн.
На
1 млн.
1
Москва
62 67 65 68 72 66,8
5,40
2
Санкт-Петербург
28 35 41 34 24 32,4
6,13
3
Республика Татарстан
7 15 16 21 20 15,8 4,07 4
Челябинская область
6 13 15 22 11 13,4 3,83 5
Московская область
10 9
9 11 13 10,4 1,40 6
Удмуртская Республика
10 6
6 10 7
7,8 5,14 7
Свердловская область
8 7
5 4
12 7,2 1,66 8
Ставропольский край
8 9
8 5
2 6,4 2,28 9
Самарская область
5 8
4 7
8 6,4 1,99 10
Пермский край
5 5
5 8
5 5,6 2,13 18
Республика Адыгея
2 5
3 3
1 2,8
6,18
…
…
…
…
…
…
…
…
45-55
Краснодарский край
2 0
1 0
0 0,6 0,11
Целевой показатель для
Краснодарского края
Показатель
Значение
Целевое кол-во
участников по
показателю для
Краснодарского края
Среднее кол-во участников на 1 млн. жителей по стране
1,7 9
Медиана среднегодового кол-ва уч. на 1 млн. жителей по Top-10 регионам
3 17
Минимум среднегодового кол-ва уч. на 1 млн. жителей по
Top-10 регионам
1,4 8
Путь олимпиадника
Этап
Хороший
Отличный Выдающийся
Участие в международной Олимпиаде
-
-
10 – 11 кл.
Кандидат в сборную страны
-
-
9 – 10 кл.
Победитель заключительного этапа ВОШ
-
11 кл.
8 – 9 кл.
Призёр заключительного этапа ВОШ
11 кл.
9 – 10 кл.
7 – 8 кл.
Участник заключительного этапа ВОШ
9 – 10 кл.
8 – 9 кл.
6 – 7 кл.
Победитель регионального этапа ВОШ
8 – 9 кл.
7 – 8 кл.
5 – 6 кл.
Начало участия в олимпиадах
7 – 8 кл.
6 – 7 кл.
-
Начало серьёзной подготовки
6 – 7 кл.
5 – 6 кл.
-
Вовлечение
5 – 6 кл.
3 – 5 кл.
-
Вузовские олимпиады
Олимпиада
Вуз
Уровень
ИОИП
ИТМО
1
Открытая олимпиада по программированию
МГУ, МФТИ
1
Московская олимпиада школьников
ВШЭ, МГУ
1
Ломоносов
МГУ
1
Информационные технологии
ИТМО
1
Олимпиада университета Иннополис
Иннополис
1
Высшая проба
ВШЭ
2
Технокубок
МФТИ, МГТУ
2
Олимпиада СПбГУ
СПбГУ
2
Когнитивные технологии
МИСиС, МФТИ
2
ВКОШП
ИТМО
-
Льготы
• Диплом заключительного этапа ВОШ –
поступление на любой профильный факультет страны
• Диплом вузовской олимпиады из утверждённого перечня – приём без экзаменов либо 100 баллов по ЕГЭ на усмотрение вуза
• Участие во ВКОШП – проход на заключительный этап ИОИП
Летние школы
Летняя компьютерная школа
Летняя школа университета Иннополис
Летние сборы юниоров
Вовлечение: Работа с 3 – 5 классами
Code.org
Работа с 3 – 5 классами
Scratch
Работа с 3 – 5 классами
Scratch
Работа со средней и старшей возрастной группой – ключевые моменты
• Автоматизированная проверка решений
• Контроль качества кода
• Оценки сложности алгоритмов, потребления ресурсов и вопросы оптимизации
• Два направления работы:
– Теория и базовые задачи
– Олимпиадные задачи
• Математическая подготовка
Перечень тем – базовый уровень
1.
Формулы и неравенства
2.
Деление и остатки
3.
Работа с массивами:
– Поиски экстремумов
– Слияния
– Исключение элементов
– Моделирование целочисленных множеств
– Сортировка подсчётом
4.
Теоретико-числовые алгоритмы
– Проверка на простоту
– Сумма собственных делителей
– Факторизация
– Представление в системах счисления
– Решето Эратосфена
– Алгоритм Евклида
5.
Формула включения- исключения
6.
Языковые вопросы
–
Типы данных, диапазон значений
–
Процедуры и функции, передача параметров
–
Статическое и динамическое выделение памяти, указатели, двумерные динамические массивы
–
Файловый ввод-вывод
–
Работа со строками, ASCII-таблица, конвертация строка – число, посимвольный анализ строки
–
Рекурсия
Перечень тем – средний уровень
7.
Сортировка и её применения
– Алгоритмы сортировки
– Сканирующая прямая
– Метод «двух указателей»
8.
Бинарный поиск
– В массиве, верхняя и нижняя границы
– По ответу
9.
Порождение комбинаций
–
Размещения с повторениями
–
Перестановки
10. Перебор
–
По числовым параметрам
–
По комбинаторным объектам
11. Графы
–
Способы задания
–
Обход в глубину
–
Обход в ширину
–
Компоненты связности
–
Сильная связность
–
Поиск цикла
–
Проверка на двудольность
–
Эйлеров путь
–
Мосты и точки сочленения
–
Конденсация
12. Динамическое программирование
–
Один и два параметра
–
Индуктивные расширения
Перечень тем – средний уровень
13. Игры и стратегии
14. Структуры данных и их применения
–
Стек, очередь, дек
–
Проход со стеком
–
Экстремум по окну
–
Список, корневая декомпозиция
15. Конечные автоматы
16. Вычислительная геометрия
–
Векторные вычисления
–
Приближенные вычисления
17. Численные методы
–
Деление отрезка пополам
–
Тернарный поиск экстремума
Перечень тем – высокий уровень
18. Структуры данных:
–
Куча
–
Дерево отрезков
–
Система непересекающихся множеств
–
Бор
–
Сбалансированные деревья
–
Хеш-таблицы
19. Кратчайшие пути
–
Алгоритм Дейкстры
–
Алгоритм Форда-Беллмана
–
Алгоритм Флойда
20. Выпуклая оболочка
21. Невыпуклые многоугогольники
22. Алгоритмы на строках:
–
Суффиксный бор
–
Z-функция
–
Алгоритм Ахо-Корасик
23. 2-SAT алгоритм
24. …
Языковые аспекты
Язык
Преимущества
Недостатки
С
•
Простые и лаконичные языковые конструкции
• Строгая типизация
• Абсолютно прозрачная работа с оперативной памятью
• Компилируется в нативный код
• Прародитель многих синтаксических и стилистических конструкций, принятых во многих современных языках
• Востребованный в индустрии язык
• Отсутствует стандартная реализация многих популярных высокоуровневых алгоритмов и структур данных
С++
• Все преимущества C
• Имеется богатая стандартная библиотека STL
• Крайне высокая востребованность в индустрии
Отсутствуют
Языковые аспекты
Язык
Преимущества
Недостатки
Pascal
• Строгая типизация
• Компилируется в нативный код
• Для начинающих простая организация ввода-вывода
• Менее прозрачная работа с оперативной памятью
• Отсутствие развитой стандартной библиотеки
• Устаревший синтаксис
• Крайне низкая востребованность в индустрии
Python
• Лаконичные языковые конструкции
• Богатые встроенные структуры данных и простые конструкции работы с ними
• Встроенная длинная арифметика
• Крайне высокая востребованность в индустрии
• Для начинающих непростая организация ввода
• Отсутствие строгой типизации
• Крайне непрозрачная работа с памятью
• Выполняется интерпретатором, скорость работы алгоритмов очень низкая
Языковые аспекты
Язык
Преимущества
Недостатки
Java
• Очень богатая стандартная библиотека
• Стандартная библиотека включает реализацию длинной арифметики
• Строгая типизация
• Очень стройная, строгая, и понятная и не перегруженная реализация ООП
• Крайне высокая востребованность в индустрии
• Для начинающих непростая организация ввода
• Непрозрачная работа с памятью
• Более медленной по сравнению с нативным кодом выполнение программы виртуальной машиной
Элементы STL C++
Алгоритм или структура данных
Реализация
Сортировка sort
Динамически расширяющийся массив vector
Бинарный поиск binary_search
Нижняя и верхняя границы lower_bound, upper_bound
Стек stack
Очередь queue
Дек deque
Список list
Множества на сбалансированных деревьях set, multiset, map, multimap
Множества на хеш-таблицах unordered_set, unordered_multiset, unordered_map, unordered_multimap
Перестановки next_permutation
Математика - темы
1.
Делимость и остатки.
Арифметика остатков.
2.
Теория чисел
–
Алгоритм Евклида
–
Системы счисления
–
Малая теорема Ферма
3.
Комбинаторика
–
Количество подмножеств
–
Размещение с повторениями
–
Перестановки
–
Число сочетаний
4.
Игры и стратегии
–
Выигрышные позиции
–
Инварианты и полуинварианты
5.
Графы
–
Теорема Эйлера
–
Эйлеров путь
–
Двудольность
6.
Векторная и вычислительная геометрия
Психологические аспекты подготовки
• Результат = способности × труд
• Труд = усилия × время
• Усилия пропорциональны интересу
• Интерес = первичный интерес + мотивация
• Первичный интерес сегодня вынужден конкурировать с большим количеством соблазнов, в младших классах слаб
• Мотивация – индуцированный интерес
Мотивация
• Младшие классы:
– Влияние родителей
– Повышение самооценки
• Средние классы:
– Стремление побеждать
– Желание заниматься перспективным делом
• Старшие классы:
– Поступление в вуз
– Профессиональная ориентация
Воспитательные аспекты подготовки
При правильном подходе развиваются:
• Серьёзное отношение к делу
• Самостоятельность
• Культура общения
• Уважительное отношение к сверстникам и учителям
• Адекватная самооценка
Роль родителей
• Организация рабочего времени ребёнка
• Психологическая поддержка – интерес к занятиям и результатам
• Финансовое обеспечение
• Результат = труд ученика × поддержку родителей × труд учителей
Школьная олимпиада для
5-6 классов
Автоматизированное тестирование обеспечивает объективность проверки
Подготовка и организация олимпиад
– технические аспекты: задачи.
• Подготовка задач в специализированном инструменте – Polygon
• Использование testlib.h
• Чекер – свой или стандартный
• Валидаторы, постпроцессинг
• Автоматическая генерация тестов
• Тщательная проработка тестовых случаев
• Неполные решения
Подготовка и организация олимпиад
– технические аспекты: контесты.
• Тип соревнования:
– acm
– ioi (в т.ч. scoring)
• Основные настройки:
– Показ вердикта тестирования
– Видимость монитора
– Заморозка монитора
– Проверка при не пройденных тестах из условия
– Выбор оцениваемой посылки
– Вердикт AC (Accepted)
Подготовка и организация олимпиад
– методические аспекты: задачи
• Олимпиадный характер задач
• Соответствие принятым олимпиадным темам
• Качество формулировки
– Строгость
– Лаконичность и ясность
– Художественность
– Необходимость построения модели участником
– Грамотность
• Следование стандартам оформления задач
• Наличие уровней сложности (подзадач)
• Полнота тестов
Подготовка и организация олимпиад
– методические аспекты: комплект
• Хорошее ранжирование участников
• Комплект должен позволять участникам различного уровня подготовки проявить себя
• Темы задач не должны пересекаться
Интернет-ресурсы
• informatics.mccme.ru
• acmp.ru
• neerc.ifmo.ru/school
• contest.yandex.ru
• codeforces.com
• polygon.codeforces.com
• infolymp.ru
• olimpiada.ru
• rsr-olymp.ru
Литература
• Шень А., Программирование: Теоремы и задачи.
• Кирюхин В.М., Информатика: всероссийские олимпиады. Выпуск 1.
• Кормен Т. Х. и др., Алгоритмы. Построение и анализ.
• Бабенко М.А., Левин М.В., Введение в теорию алгоритмов и структур данных.
• Керниган Б., Ритчи Д., Язык программирования C.
• Страуструп Б., Язык программирования C++.
Сухов Владимир Борисович
+7-928-239-06-01
V_Sukhov@mail.ru
Краснодарская школа программирования http://крашколап.рф