Использование специализированных электронных образовательных ресурсов для подготовки школьников к олимпиадам по информатике

Полный текст

Проблема и цель. Одной из первостепенных задач современной школы является развитие олимпиадного движения, значение которого трудно переоценить. Прежде всего, это мощный механизм выявления талантливых учеников на всей территории нашей страны. В последние годы Всероссийское олимпиадное движение насчитывает более пяти миллионов участников [1-4]. Среди приоритетных направлений развития Всероссийского олимпиадного движения создание равных возможностей для школьников всех регионов Российской Федерации. Информатика - одна из самых молодых дисциплин, изучаемых в школе. Неудивительно, что сложность задач, предлагаемых участникам олимпиад по информатике, возрастает год от года. Достаточно заметить, что сегодня сложность задач на муниципальном этапе Всероссийской олимпиады по информатике соответствует заключительному этапу олимпиады 30-летней давности. А задачи современного заключительного этапа олимпиады раньше были по силам только студентам 2-3-х курсов специальности «Прикладная математика». Вместе со сложностью задач увеличились и требования к объему знаний и умений, которыми должны владеть участники олимпиады. К сожалению, эти знания выходят далеко за пределы школьной программы. В качестве примера можно привести курс «Алгоритмы и структуры данных», который обычно преподают в рамках программы высшей школы [5-9]. По установившейся на сегодняшний день практике, решение множества современных олимпиадных задач по информатике невозможно без усвоения базовых элементов данного курса. Курс включает как большинство классических алгоритмов решения задач (метод декомпозиции, перебор с возвратом, жадные алгоритмы, динамическое программирование, эвристики и т. д.), так и структуры данных (стек, очередь, дек, бинарная куча, дерево отрезков, дерево поиска и т. д.), применение которых позволяет эффективно решать олимпиадные задачи. Очевидно, что изучение некоторых элементов курса «Алгоритмы и структуры данных» необходимо начинать на уровне средней школы, с 7-х классов. Тогда к 9-11-м классам у учеников сформируется четкое понятие о структурах данных и алгоритмах работы с ними. Но знакомство с подобными динамическими структурами следует делать с учетом поправки на возраст учеников. Современное развитие электронных образовательных ресурсов, обладающих мультимедийными и интерактивными возможностями, позволяет организовать подачу учебного материала в доступной для учеников средней школы форме [10; 11]. Обычно знакомство со стеком, очередью и деком происходит либо в рамках углубленного изучения информатики в старших классах, либо уже в высшей школе, где требования к наглядности изучаемого материала являются не столь актуальными. На иллюстрациях в учебниках информатики стек и очередь обычно изображается в виде таблицы, в ячейки которой могут быть помещены числа. Пример такой иллюстрации представлен на рис. 1. Дисциплина стека: последним вошел - первым вышел [Last In, First Out] Дисциплина очереди: первым вошел - первым вышел [First In, First Out] Рис. 1. Изображение стека и очереди в классических учебниках для высшей школы Figure 1. An image of the stack and queue in classic high school textbooks Не вызывает сомнения, что для знакомства с динамическими структурами данных учеников 7-го класса требуются учебные материалы с большей степенью наглядности. В связи с этим при создании интерфейса электронного образовательного ресурса (ЭОР) «Стройплощадка» возникла идея использования в качестве модели стека, очереди и дека анимационного изображения конвейера, лента которого проходит через накопитель (буфер). Изображение конвейера представлено на рис. 2. В данном случае это модель дека. Определить это можно по количеству и направлению стрелок. Четыре стрелки символизируют возможность помещать груз в накопитель (и забирать из накопителя) как с левой, так и с правой части ленты конвейера. Рис. 2. Изображение конвейера, работающего в режиме дека Figure 2. Image of a conveyor operating in deque mode Конвейер, работающий в режиме стека, изображен на рис. 3. Две стрелки, расположенные в левой части накопителя, обозначают возможность помещать груз в накопитель (и забирать из накопителя) только с левой части ленты конвейера. Рис. 3. Изображение конвейера, работающего в режиме стека Figure 3. Image of a conveyor operating in stack mode Конвейер, работающий в режиме очереди, изображен на рис. 4. Две стрелки одного направления, расположенные в левой и правой частях накопителя, обозначают возможность помещать груз в накопитель только с левой части ленты конвейера, а забирать из накопителя только с правой части ленты. Рис. 4. Изображение конвейера, работающего в режиме очереди Figure 4. Image of a conveyor operating in queue mode Методология. В ходе исследования применялись как общенаучные методы (анализ, синтез, индукция, дедукция, аналогия, абстрагирование, конкретизация, системный анализ, формализация), так и эмпирические (наблюдение, сравнение). Результаты и обсуждение. ЭОР «Стройплощадка» представляет собой исполнитель, моделирующий работу по перемещению грузов на строительной площадке. Поэтому, кроме конвейера, имитирующего работу стека, очереди или дека, на стройплощадке присутствует исполнитель «кран», управление которым возможно осуществлять как в ручном (для лучшего понимания алгоритма решения задачи), так и в программном режиме. Задача обучающегося - написать программный код управления краном (и опосредованно конвейером), позволяющий переместить грузы из исходного в итоговое положение. Интерфейс ЭОР «Стройплощадка» изображен на рис. 5. Рис. 5. Внешний вид (интерфейс) ЭОР «Стройплощадка» Figure 5. Appearance (interface) of EER “Construction site” В условии задачи могут варьироваться количество и цвет грузов, количество складов на стройплощадке, между которыми перемещаются грузы, и режим работы конвейера (стек, очередь или дек). Допустимо каждый склад, расположенный на стройплощадке (их количество может достигать девяти), задавать в одном из трех режимов: - прием грузов; - выдача грузов; - прием и выдача грузов. Грузы дифференцируются по цвету (6 вариантов) и яркости (5 градаций). Такое разнообразие режимов работы позволяет разрабатывать большое количество задач различной сложности. Каждая задача имеет несколько тестов (входных данных). Задача считается выполненной лишь в случае, если программа, написанная обучающимся, правильно перемещает грузы во всех тестах. Для ЭОР «Стройплощадка» разработан комплект из 60 заданий, различающихся по сложности выполнения и типу динамической структуры (стек, очередь или дек), применяемой для решения поставленной задачи. Кроме того, учителя информатики, использующие ЭОР «Стройплощадка» для подготовки своих учеников к олимпиадам, могут сами создавать новые задачи, так как у задач достаточно простой формат. Интерфейс панели «Меню» представлен на рис. 6. Рис. 6. Внешний вид (интерфейс) панели «Меню» Figure 6. Appearance (interface) of the “Menu” panel В окнах «Дано» и «Получить» отображается исходное и итоговое (которое нужно получить) расположение грузов на стройплощадке. В изображенном примере требуется все грузы переместить на две позиции вправо, при этом расположение грузов должно остаться прежним. В верхней части панели расположены кнопки загрузки и сохранения программы, написанной учеником, а также кнопка загрузки задачи и выбора из выпадающего списка из прилагаемых к задаче тестов. Обычно к каждой задаче прилагается 3-4 теста с различными условиями. В зоне «Выполнение программы» отображаются элементы управления выполнением программы. Программа может выполняться либо в автоматическом режиме (АР), либо в ручном (РР). В ручном режиме управление подъемным краном осуществляется с помощью клавиш «вправо», «влево», «вверх», «вниз» и «пробел». В автоматическом режиме кран выполняет команды из программы, составленной учеником. Имеются четыре кнопки управления работой программы: «пуск», «стоп», «пауза», «шаг». Они позволяют запускать программу на исполнение, останавливать ее, а также отлаживать в пошаговом режиме. В правой части зоны расположен блок управления скоростью выполнения программы. В зоне «Программа» построчно записывается программа управления подъемным краном. В основу встроенного алгоритмического языка положена парадигма структурного программирования «сверху вниз». Этот подход был предложен еще в начале 70-х годов прошлого века и основывался на теореме о структурировании Бёма - Якопини, согласно которой любой алгоритм может быть преобразован в структурный вид. Согласно работе Э. Йодана [12], структурное программирование основано на использовании четырех алгоритмических конструкций, каждая из которых имеет один вход и один выход. Графическое изображение этих конструкций представлено на рис. 7. Изначально программа содержит в своем теле один единственный прямоугольник, который может быть превращен в любую из вышеприведенных конструкций. Таким образом, программа постепенно разрастается, сохраняя при этом структурную целостность. В результате в коде программы полностью отсутствуют операторы безусловного перехода (goto), а также значительно облегчается чтение текста программы, что позволяет минимизировать количество допущенных ошибок и упрощает процесс отладки. Рис. 7. Алгоритмические конструкции структурного программирования сверху вниз Figure 7. Algorithmic constructions of structured programming top-down В рамках реализации принципа «дружественного интерфейса» ввод команд и управляющих конструкций осуществляется не с клавиатуры, а выбором из списка. Отображение команд и управляющих конструкций осуществляется согласно принципу, реализованному в большинстве языков программирования: вложенный блок сдвигается вправо на одну позицию табуляции. Кроме того, применяется цветовая дифференциация команд и управляющих конструкций с целью облегчения визуального восприятия программы. В интерфейсе исключена возможность копирования, вставки и удаления крупных частей программы с целью выработать у учащихся стиль программирования в соответствии с парадигмой структурного программирования сверху вниз (рис. 8). Для выработки навыков алгоритмического мышления и умения писать эффективные программы в ЭОР «Стройплощадка» специально введено множество ограничений. Одно из них - невозможность копирования и удаления фрагментов программы. Это ограничение заставляет учеников более вдумчиво подходить к написанию программы, так как исправление кода сопряжено с серьезными временными затратами. Второе ограничение - наличие всего четырех переменных (называемых флагами), которые могут сохранять только числа от 0 до 9. В рамках этого ограничения ученики вынуждены очень экономно использовать данные переменные для организации, например, вложенных циклов. И, наконец, третье ограничение - усеченный набор команд и управляющих конструкций, с помощью которых формируется текст программы [13; 14]. Для построения программы используются три управляющих конструкции: - альтернатива (ЕСЛИ - ИНАЧЕ - КОНЕЦ ЕСЛИ); - цикл с предусловием (ПОКА - КОНЕЦ ПОКА); - цикл с постусловием (ЦИКЛ - КОНЕЦ ЕСЛИ). Для каждой из управляющих конструкций может быть использовано одно из условий, представленных на рис. 8. Кроме управляющих конструкций, для построения программы используются также команды (операторы). Список доступных команд представлен на рис. 9. Рис. 8. Форма добавления управляющей конструкции Figure 8. Form for adding a control structure Рис. 9. Форма добавления команды Figure 9. Form for adding a command В качестве примера можно рассмотреть задачу со стеком первого уровня сложности. Условие задачи и расположение грузов на стройплощадке показано на рис. 10. В данной задаче ученик должен написать программу, которая, управляя краном, переместит грузы из исходного положения (первый склад) в итоговое положение (второй склад), сохраняя взаимное расположение грузов без изменения. Для выполнения задачи ученик может (и должен) использовать стек. На рис. 11 представлен текст программы, решающей эту задачу. Постепенное возрастание сложности предлагаемых задач и расширение набора алгоритмических приемов, используемых при их решении, позволят школьникам легче справляться с решением олимпиадных задач по информатике, в которых требуется применять такие структуры данных, как стек, очередь или дек. Рис. 10. Условие задачи и внешний вид стройплощадки Figure 10. Condition of the task and the appearance of the construction site Рис. 11. Текст программы, перемещающей грузы с первого склада на второй с помощью стека Figure 11. The text of a program that moves goods from the first warehouse to the second using a stack Заключение. В результате эксплуатации ЭОР «Стройплощадка» выявлено положительное влияние на качество подготовки учащихся к олимпиадам по информатике различного уровня [15-17]. Доказано, что применение ЭОР способствует повышению мотивации изучения специализированных структур данных (стека, очереди и дека), используемых для решения олимпиадных задач по информатике. Ученики, познакомившиеся с использованием стека, очереди и дека в рамках данного ЭОР, более эффективно применяют полученные навыки при решении олимпиадных задач по информатике, в которых требуется использовать «обход в глубину», «обход в ширину», «обратную польскую бесскобочную запись» и подобные им алгоритмы.

Об авторах

Ольга Юрьевна Заславская

Московский городской педагогический университет

Email: zaslavskaya@mgpu.ru
ORCID iD: 0000-0002-6119-8271

доктор педагогических наук, профессор, департамент информатизации образования, Институт цифрового образования

Российская Федерация, 127521, Москва, ул. Шереметьевская, д. 29

Олег Дмитриевич Любутов

Школа № 1579

Автор, ответственный за переписку.
Email: lod375039@yandex.ru

учитель информатики

Российская Федерация, 115522, Москва, Пролетарский пр-кт, д. 7, корп. 3

Список литературы