Методы визуализации при разработке виртуальной лаборатории по теории алгоритмов и структурам данных

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

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

Методы визуализации при разработке виртуальной лаборатории по теории алгоритмов и структурам данных

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

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

• •    анализ метрических характеристик алгоритма;

• •    оценка скорости роста алгоритма;

• •    имитационная реализация алгоритма;

• •    проверка правильности работы алгоритма.

Содержание виртуальной лаборатории соответствует программе курса «Теория алгоритмов и структуры данных» для указанных выше специальностей.

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

• 1.    Описание алгоритма – задается представление алгоритма в виде блок-схемы или с помощью псевдокода.

• 2.    Описание ввода – определяются режимы ввода данных (ручной или автоматический на основе случайной выборки.

• 3.    Описание вывода – определяются основной и детальный режимы. При основном режиме выводятся исходный и обработанный массивы данных, количество сравнений P. При детальном – исходный и промежуточные массивы данных после каждого цикла.

• 4.    Аппроксимационная оценка быстродействия методом наименьших квадратов:

• •    ввод : задается число M повторений алгоритма на случайных наборах исходных массивов возрастающей длины N1, N2,…;

• •    счет : задается функция интерполяции (например, квадратичная), определяется минимальная сумма квадратов отклонений для каждого массива - S_N1, S_{N2, …;}

• •    вывод : «быстродействие пропорционально N^α», график

• 5.    Программирование и проверка правильности алгоритма (программы) – многоэтапная оценка:

скорости, последовательность отклонений для каждого массива - S N1 , S N2 …, график отклонений.

• •    составление   программы ,   компиляция и вывод

результатов p1,p2,… и промежуточных массивов после каждого этапа (цикла) алгоритма на случайном наборе данных (числовой массив длины N);

• •    параллельный счет на том же наборе входных данных, результаты p 01 ,p 02 ,… и промежуточных массивов после каждого этапа;

• •    сравнение результатов p i и p 0i , получение оценки Q ni “netto”: при совпадении – 1 балл, иначе 0, Q n = Q n1 + Q n2 +….

• 6.    Оценка работы студента:

• •    Q b “brutto” = Q n * K;

• •    добавление оценки - ввод параметра «весовой коэффициент К»;

• •    получение оценки в журнал студента.

• 7.    Визуализация результатов при оценке правильности разработанного алгоритма.

Визуализация при разработке данной виртуальной лаборатории включает следующие возможности:

• •    визуализация ввода данных – студент видит набор

вводимых данных в удобной визуальной форме;

• •    визуализация работы алгоритма – основные этапы

работы алгоритма выводятся на экран в форме таблиц, графиков;

• •    визуализация результатов – итог исполнения алгоритма виден на экране, причем, студент имеет возможность сравнить исходные данные и конечный результат;

• •    оценка правильности алгоритма.

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

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

Заключение

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

Разрабатываемая на основе методов визуализации виртуальная лаборатория может быть использована в e-learning системе обучения. Соответствующее программное обеспечение разрабатывается на основе web-технологий и может быть использовано также в дистанционном образовании.