Олимпиадная подготовка и проведение олимпиад. Подготовка школьников к участию в олимпиадах по информатике. Подготовка и проведение олимпиад по информатике
 Скачать 0.93 Mb.
|
|
Подготовка школьников к участию в олимпиадах по информатике. Подготовка и проведение олимпиад по информатике. Сухов В.Б., к.ф.-м.н., член жюри регионального этапа, член региональной п.м.к., председатель жюри краснодарского муниципального этапа, председатель краснодарской муниципальной п.м.к. Всероссийской олимпиады школьников по информатике тренер краснодарских краевых и городских сборов, руководитель Краснодарской школы программирования Всероссийская олимпиада школьников по информатике Этап 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://крашколап.рф |