Новые возможности задачника Programming Taskbook: обработка динамических структур и конструктор учебных заданий

Вид материала

Документы

Содержание 2. Общая характеристика программного комплекса Programming Taskbook 3. Обработка динамических структур данных 4. Конструктор учебных заданий

Подобный материал:

• Анализ, обработка и передача динамических изображений в моделях виртуальной реальности, 80.25kb.
• Методична програма „Конструктор занять" Воснову методичної програми „Конструктор занять",, 107.37kb.
• Информатизации структур государственной службы реферат, 60.69kb.
• Лекции по основам программирования на C/C++, 690.4kb.
• От локальных задач автоматизации к интегрированной асу комбината хлебопродуктов, 95.01kb.
• Разработка нелинейных динамических систем для формирования хаотических колебаний, 219.26kb.
• Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме, 891.19kb.
• «Дидактическое обеспечение десятибалльной системы оценки учебных достижений учащихся, 234.51kb.
• Нии заданий темы «Обработка информации» третьей части экзаменационной работы 25,7%, 132.84kb.
• План лекций параллели «С» лкш 2006, 20.22kb.

Новые возможности задачника Programming Taskbook: обработка динамических структур и конструктор учебных заданий

М. Э. Абрамян, доцент факультета математики, механики
и компьютерных наук Южного федерального университета,
mabr@math.sfedu.ru

В докладе обсуждаются принципы разработки электронных задачников по программированию и описываются новые возможности задачника Programming Taskbook, реализованные в 2008-2009 г.

1. Принципы разработки электронных задачников по программированию

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

Такая схема является достаточно эффективной для проверки текущего уровня подготовки учащегося, однако не слишком пригодна для использования в ходе собственно обучения программированию, поскольку никак не влияет на процесс разработки программы. При решении задачи учащийся по-прежнему остается «один на один» с компьютером, точнее, с используемой средой программирования. Автоматизируется лишь последний этап — тестирование созданной программы; при этом сам процесс тестирования является скрытым от учащегося, поскольку проводится на удаленном компьютере.

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

Принцип интеграции задачника и программной среды не означает, что для каждой среды надо разрабатывать свой вариант задачника. Используя современные средства программирования, можно создать универсальное «ядро» задачника и набор модулей-«посредников», с помощью которых это ядро будет интегрировано в различные программные среды, в том числе и ориентированные на разные языки программирования. В операционной системе Windows «ядро» задачника естественно реализовать в виде динамически подключаемой библиотеки (dll), поскольку средства подключения таких библиотек к программе предусмотрены в подавляющем большинстве программных сред, функционирующих под управлением Windows. Помимо процедур, управляющих работой задачника, «ядро» должно содержать достаточно обширный базовый набор заданий по различным разделам программирования. Весьма желательным представляется также возможность расширения задачника, то есть дополнения имеющегося базового набора новыми группами заданий. Новые группы можно оформлять в виде дополнительных динамических библиотек, автоматически подключаемых к ядру задачника при его инициализации.

^ 2. Общая характеристика программного комплекса Programming Taskbook

Перечисленные выше принципы организации электронного задачника были положены автором в основу разработанного им программного комплекса Programming Taskbook [1, 2].

Программный комплекс «Электронный задачник по программированию Programming Taskbook 4» зарегистрирован в Реестре программ для ЭВМ 28 апреля 2007 г. (свидетельство об официальной регистрации программы для ЭВМ № 2007611815). Имеется как русский, так и английский вариант задачника. Разработка английского варианта выполнена при финансовой поддержке Европейского консорциума инновационных университетов (ECIU) в рамках совместного русско-германского проекта «Supporting Assessment of Program Assignments».

В докладе [1], представленном на II конференции «Современные информационные технологии и ИТ-образование», уже описывались основные возможности задачника Programming Taskbook. В настоящем докладе рассматриваются новые возможности задачника, реализованные в его последних версиях.

Задачник Programming Taskbook может использоваться для следующих языков и программных сред:

• Pascal: Borland Delphi 3.0–7.0, Turbo Delphi 2006 for Win32, Free Pascal Lazarus 0.9, PascalABC.NET (система программирования PascalABC.NET разработана на факультете математики, механики и компьютерных наук ЮФУ под руководством доц. С. С. Михалковича; информация об этой системе приводится на ее сайте pascalabc.net);
  
• Visual Basic и Visual Basic .NET: Microsoft Visual Basic 5.0–6.0, Microsoft Visual Studio .NET 2003, 2005, 2008;
  
• C++: Borland C++Builder 4.0–5.0, Microsoft Visual C++ 6.0, Microsoft Visual Studio .NET 2003, 2005, 2008;
  
• C#: Microsoft Visual Studio .NET 2003, 2005, 2008.
  

Версия 4.8 задачника (последняя на момент подготовки доклада) содержит 1100 учебных заданий, охватывающих все разделы базового курса программирования: «Ввод и вывод данных, оператор присваивания» (40 заданий), «Целые числа» (30), «Логические выражения» (40), «Условный оператор» (30), «Оператор выбора» (20), «Цикл с параметром» (40), «Цикл с условием» (30), «Процедуры и функции» (60), «Последовательности» (40), «Минимумы и максимумы» (30), «Одномерные массивы» (140), «Двумерные массивы (матрицы)» (100), «Символы и строки» (70), «Двоичные файлы» (90), «Текстовые файлы» (60), «Составные типы данных в процедурах и функциях» (70), «Рекурсия» (30), «Динамические структуры данных» (80), «Бинарные деревья» (100).

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

^ 3. Обработка динамических структур данных

Тема «Динамические структуры данных» изучается в завершающем разделе базового курса программирования; в ней обычно рассматриваются односвязные линейные структуры (стек, очередь), двусвязные списки и бинарные деревья. В языках Pascal и C++, традиционно используемых при начальном обучении программированию, для хранения и обработки динамических структур применяются цепочки записей, размещенные в динамической памяти, и связанные с ними указатели. Выполняя практические задания на обработку динамических структур, учащиеся сталкиваются с дополнительными трудностями при формировании исходных данных и выводе результатов. Действительно, для того чтобы обработать динамическую структуру, необходимо прежде всего сформировать ее в памяти, а эта задача является достаточно сложной. Не менее сложно также обеспечить визуализацию динамической структуры с целью проверки ее правильности. Автоматизация этих этапов выполнения заданий позволила бы учащимся сосредоточить усилия на разработке алгоритма решения задачи и ускорила бы тестирование разработанного алгоритма. В версии 4.8 задачника Programming Taskbook реализована подобная автоматизация для всех перечисленных выше динамических структур.

Задачник содержит две группы заданий, связанных с динамическими структурами. Первая группа (Dynamic) посвящена линейным структурам и содержит 80 заданий. Задания разбиты на подгруппы, в каждой из которых рассматривается конкретная динамическая структура: стек, очередь, двусвязный список. Задания в подгруппах располагаются по возрастанию уровня сложности: от простейших, связанных с просмотром структуры и добавлением или удалением ее элементов, до достаточно трудных (на перегруппировку элементов, объединение или разбиение структур).

Вторая группа (Tree) посвящена бинарным деревьям и содержит 100 заданий. Каждая из ее подгрупп освещает какой-либо аспект обработки деревьев: анализ содержимого дерева, формирование дерева с заданной структурой, преобразование имеющегося дерева, особенности работы с деревьями с обратной связью, деревьями поиска, деревьями разбора выражений и деревьями с произвольным ветвлением (типа «left child – right sibling»).

В качестве примера приведем программу, решающую на языке Pascal одно из простейших заданий на обработку бинарных деревьев (в задании требуется найти количество вершин данного бинарного дерева):


program Tree2;

uses PT4;


function NodeCount(P: PNode): Integer;

begin

if P = nil then

NodeCount := 0

else

NodeCount := 1 + NodeCount(P^.Left) +

NodeCount(P^.Right);

end;


var

Root: PNode;

begin

Task('Tree2');

GetP(Root);

PutN(NodeCount(Root));

end.


Алгоритм решения, подобно большинству алгоритмов обработки деревьев, оформлен в виде рекурсивной функции. Исходное дерево формируется самим задачником, который передает программе указатель на его корень (программа считывает этот указатель с помощью процедуры GetP). Найденный результат (целое число) программа передает для проверки задачнику, используя процедуру PutN. Раздел операторов начинается вызовом процедуры Task, которая инициализирует задание с указанным именем. Все перечисленные процедуры, а также вспомогательный тип PNode (указатель на запись типа TNode с полями Data, Left и Right), определены в модуле PT4, который должен подключаться к любой программе, использующей задачник Programming Taskbook.




Рис. 1. Окно задачника Programming Taskbook


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

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

Для того чтобы задание было зачтено как выполненное, необходимо, чтобы программа была успешно испытана на нескольких тестах, проведенных подряд. Число тестов зависит от сложности задания и находится в диапазоне от 3 до 9. Исходные динамические структуры, как и данные других типов, генерируются задачником с применением датчика случайных чисел, что обеспечивает разнообразие исходных данных при тестировании разработанной программы.

Поскольку версия 4.8 задачника Programming Taskbook позволяет использовать языки платформы .NET (Visual Basic .NET и C#), в которых вместо указателей применяются ссылки на объекты, потребовалось соответствующим образом изменить формулировки заданий групп Dynamic и Tree для этих языков. При выполнении заданий данных групп на одном из языков платформы .NET необходимо пользоваться объектами специального класса Node, определенного в задачнике и пред­назначенного для хранения информации об элементах динамической структуры.

^ 4. Конструктор учебных заданий

Конструктор учебных заданий является новой возможностью задачника Programming Taskbook, появившейся в версии 4.8. Новые группы заданий можно создавать в средах Borland Delphi или Free Pascal Lazarus, оформляя их в виде динамических библиотек (dll-файлов). Задания, разработанные с применением конструктора, будут доступны для выполнения на языках Pascal, C++, Visual Basic, Visual Basic .NET и C# в любой среде, в которую интегрирован задачник, если сам разработчик заданий не ограничит их применение рамками какого-либо отдельного языка или набора языков (например, языков, поддерживающих работу с указателями, или языков платформы .NET).

Конструктор заданий реализован в виде модуля PT4TaskMaker языка Pascal и содержит подпрограммы, обеспечивающие программную реализацию учебных заданий и объединение их в группу. Эти подпрограммы можно разбить на следующие категории:

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

Возможны ситуации, когда преподавателю может понадобиться выполнить перекомпоновку имеющихся заданий, объединив требуемые задания в новую группу. Например, это представляется оправданным при подготовке групп заданий, включаемых в варианты индивидуальных заданий или варианты контрольных работ. Для создания подобных «сводных» групп заданий не требуется разрабатывать новую динамическую библиотеку; достаточно подготовить текстовый файл, указав в нем необходимые сведения о создаваемой сводной группе (в том числе имена включаемых в нее заданий), и обработать этот файл специальной программой, которая сгенерирует на его основе динамическую библиотеку.

Для подключения созданной группы заданий к задачнику достаточно разместить dll-файл с ее реализацией в подкаталоге Lib системного каталога задачника или в рабочем каталоге учащегося. После этого все задания новой группы станут доступными для выполнения, а информация об этой группе будет включена в программные модули задачника PT4Demo и PT4Load, обеспечивающие соответственно просмотр заданий в демонстрационном режиме и создание программ-заготовок для выполнения заданий в различных программных средах.

В версии 4.8 задачника Programming Taskbook появилась возможность автоматической генерации html-страниц с описанием любой группы заданий (как входящей в базовый набор, так и созданной с помощью конструктора). Помимо текста формулировок всех заданий и заголовка группы страница может содержать заголовки подгрупп в пределах данной группы, а также комментарии ко всей группе заданий и ее подгруппам. Для генерации html-страницы и ее немедленного отображения в стандартном веб-браузере можно использовать программный модуль PT4Demo; кроме того, сгенерировать требуемую страницу можно и непосредственно из программы, выполняющей учебное задание, вызвав соответствующую процедуру. Эта новая возможность задачника делает его «самодокументируемым» и упрощает ознакомление с имеющимися группами заданий.

Подробная информация о задачнике Programming Taskbook содержится на его веб-сайте ptaskbook.com.


Литература

1. Абрамян М. Э. Электронный задачник Programming Taskbook: опыт разработки и применения / II Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, 18–21 декабря 2006 г. Сборник докладов научно-практической конференции. — М.: МАКС пресс, 2006. — С. 194–199.

2. Абрамян М. Э. Реализация универсального электронного задачника по программированию // Информатика и образование, 2009, № 6. — С. 118–120.

3. Абрамян М. Э. Бинарные деревья: задачи, решения, указания. — Банк компьютерных изданий ЮФУ, 2009. — 71 с. (open-edu.sfedu.ru/files/abramyan-bintrees.zip)

4. Абрамян М. Э. Конструктор учебных заданий для электронного задачника Programming Taskbook. Методическая разработка для преподавателей программирования. — Банк компьютерных изданий ЮФУ, 2009. — 76 с. (open-edu.sfedu.ru/files/abramyan_taskmaker.pdf)