Полный текст статьи
Печать

Подготовку сборной команды школьников Республики Саха (Якутия) к участию в олимпиадах по информатике и программированию осуществляет кафедра информатики МАН РС(Я), в составе которой работают преподаватели Института математики и информатики (ИМИ) СВФУ. Система подготовки учащихся включает в себя учебно-тренировочные и практико-ориентированные сборы, кружок по программированию при ИМИ (руководитель Н.Н. Павлов, доцент кафедры информационных технологий, преподаватель информатики Республиканского лицея), спецкурс  по олимпиадной информатике. В республике проводятся муниципальный и региональный этапы Всероссийской олимпиады школьников по информатике, а также ставшие традиционными Республиканская командная олимпиада школьников по программированию, Международная олимпиада школьников «Туймаада» по информатике, Открытая лично-командная олимпиада по программированию в рамках научной конференции студентов, аспирантов и молодых ученых «Лаврентьевские чтения», Открытый командный чемпионат по программированию ИМИ СВФУ. В результате многолетней кропотливой работы учащиеся республики более 10 раз становились призерами заключительного этапа Всероссийской олимпиады школьников, трижды – чемпионами Международной олимпиады «Туймаада», 4 раза – призерами Международной Жаутыковской олимпиады по информатике. В командных соревнованиях по программированию также имеются достаточно высокие результаты – 13 раз становились призерами и победителями полуфинала Всероссийской командной олимпиады школьников по программированию (в том числе четырежды занимали абсолютное 1 место), 6 раз – призерами финала.  

В целях систематизации процесса подготовки учащихся к олимпиадам по информатике разрабатывается учебно-методическое обеспечение, включающее в себя три учебно-методических комплекса на основе уровневой дифференциации: базовый уровень, 1 и 2 ступени. Каждая из этих комплексов  рассчитана на 48 часов  подготовки. Отбор содержания программ осуществлялся на основе структуры содержания олимпиад по информатике [1], соотнесение тем по уровням – на основе опыта работы со школьниками и анализа результатов олимпиад, проводимых в республике, за последние годы.   

Программа подготовки базового уровня предназначена для школьников, делающих первые шаги в олимпиадном программировании, и знакомит учащихся с основами комбинаторики, представлением чисел в различных системах счисления, структурами данных «массив» и «строка», организацией полного перебора вариантов и идеей динамического программирования. Освоив данную программу, учащиеся должны овладеть следующими базовыми алгоритмами:

  • Вычисление n!
  • Перевод из одной системы счисления в другую 
  • Стандартные алгоритмы обработки массивов (суммирование элементов,  нахождение минимального (максимального) элемента и его местоположения, удаление (вставка) элемента)
  • Формирование новой строки из частей исходной, поиск подстроки в строке (наивный метод и алгоритмы поиска за O(n+m)), выделение слов из текста
  • Линейный и двоичный поиск
  • Квадратичные алгоритмы сортировки (метод «пузырька», метод выбора минимального (максимального) элемента, метод включения).

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

Предполагается, что перечисленными навыками учащиеся, имеющие интерес к программированию и мотивированные к участию в олимпиадах по информатике, должны овладеть еще в школе. Но как показывает практика, не во всех школах и не все учителя хотят и могут научить ребенка этому. В нашей республике вот уже больше 10 лет проводятся Заочная олимпиада учителей информатики по программированию и Республиканская командная олимпиада учителей по программированию. Их итоги показывают, что в личных соревнованиях из года в год участвует максимум 17 учителей со всей республики, и мастерство лидеров растет [2]. В то же время, большинство учителей не принимают участия, поскольку не могут составить конкуренцию группе лидеров или просто не хотят. Поэтому целью разработки рассматриваемого УМК является оказание неопытным учителям методической помощи в начальной организации школьного кружка олимпиадной информатики, а также повышение уровня их профессиональной компетенции. 

Следующий уровень – программа «Ступень 1» учебно-тренировочных сборов резервного состава сборной РС(Я) – предназначена для школьников 7-9 классов, уже показавших свои способности, в частности, прошедших на региональный этап Всероссийской олимпиады школьников по информатике. Здесь учащиеся знакомятся со способами представления многоразрядных чисел, основами аналитической геометрии, понятием рекурсии, улучшенными алгоритмами поиска и сортировки, методом динамического программирования. Практическая часть включает в себя реализацию алгоритмов сложения, вычитания и умножения многоразрядных чисел, двоичного поиска и «быстрой» сортировки, решение задач целочисленной арифметики, геометрических задач на взаимное расположение и вычисление площадей различных фигур, классических задач на использование рекурсивных алгоритмов и метода динамического программирования.

Республика Саха (Якутия) – самый крупный регион Российской Федерации, особенностью которого является большая удаленность населенных пунктов от столицы республики и непростая ситуация с транспортными сообщениями. В основном используется автомобильный транспорт, а поскольку в республике еще и очень много рек и озер, включая главную водную артерию – реку Лену, то по два месяца весной и осенью добраться до г. Якутска весьма проблематично. Вместе с тем, во многих улусах республики работают высококвалифицированные учителя информатики (В.Н. Элякова, П.П. Захаров, Д.Д. Прокопьев, Г.Е. Герасимова, С.М. Фролова и другие), которым вполне по силам заниматься со школьниками по данной программе. Поэтому в последнее время Малой академией наук РС(Я) практикуется проведение учебно-тренировочных сборов в нескольких группах улусов, и цель УМК 1-ой ступени – дать учителям ориентир и дидактические материалы по обеспечению УТС.  

И, наконец, программа «Ступень 2» учебно-тренировочных сборов предназначена для более опытных старших школьников – учащихся 10-11 классов, а также для одаренных учащихся 7-9 классов, победителей и призеров регионального этапа Всероссийской олимпиады школьников по информатике. Она предполагает знакомство с алгоритмами вычислительной геометрии, основными алгоритмами на графах, алгоритмическими стратегиями, комбинаторными алгоритмами, динамическими структурами данных. Тематика задач практических занятий – задачи на нахождение расстояний между объектами на плоскости, пересечение различных геометрических фигур, поиск в графе, подсчет числа компонент связности и порождение каркасов графа, вычисление длин кратчайших путей в дереве, сокращение полного перебора вариантов решений, генерацию комбинаторных объектов и т.п.

Понятно, что работать по данной программе могут только те учителя, которые постоянно тренируются, сами активно и успешно участвуют в олимпиадах по программированию, преподаватели ИМИ СВФУ – члены региональной методической комиссии, а также студенты и выпускники IT-направлений подготовки, имеющие богатый и ценный опыт участия в олимпиадах по программированию, но, возможно, не имеющие опыта преподавания. Поэтому цель разработки УМК 2-ой ступени – обеспечить преподавателей и учителей дидактическими материалами и оказать методическую помощь молодежи.  

Большинство практических занятий рекомендуется проводить с использованием системы автоматизированной проверки программ, в режиме онлайн соревнования. Однако при решении задач по некоторым темам, в частности, на рекурсию, преподавателю нужно проверять именно тексты программ, ставя искусственный запрет учащимся на использование циклов, и добиваясь, тем самым,  осознанного использования учащимися такого приема, как рекурсия. При решении задач на «длинную» арифметику, в свою очередь, ставится запрет на использование возможностей современных высокоуровневых языков программирования – для того, чтобы учащиеся лучше понимали, как компьютер работает с многоразрядными числами, и, тем самым, повышали свою математическую культуру.

Обучение по программе каждого уровня заканчивается 4-х часовой онлайн олимпиадой: подобраны задачи соответствующего уровня сложности и тематики. А обучение на ступенях 1 и 2 начинается со входной олимпиады, позволяющей подкорректировать программу обучения, подбор задач в зависимости от ее результатов.

Таким образом, структурную схему учебно-методического обеспечения можно представить следующим образом (см. рисунок): 

Конечно, создаваемая система сама по себе не гарантирует успешности выступлений учащихся на олимпиадах по информатике. После обучения по программам учебно-тренировочных сборов, учащиеся должны оттачивать мастерство и углублять свои знания решением и разбором большого количества задач, предлагавшихся на различных олимпиадах, самостоятельно или под руководством школьного учителя информатики, или же на подготовительных практико-ориентированных сборах.  Здесь на помощь могут прийти различные веб-ресурсы, посвященные олимпиадам по программированию. Начинающим можно порекомендовать, например, сайт проекта «Школа программиста» Красноярского краевого Дворца пионеров и школьников (acmp.ru), более опытным – сайт «Олимпиады по информатике. Санкт-Петербург, Россия» (neerc.ifmo.ru/school/io/), сайт «Соревнования по программированию» Михаила Мирзаянова (codeforces.ru), Timus Online Judge – архив задач с проверяющей системой Уральского федерального университета (acm.timus.ru).