Телематика'2004

XI Всероссийская
научно-методическая
конференция


 

 

РЕАЛИЗАЦИЯ ВИЗУАЛИЗАТОРОВ НА ОСНОВЕ АВТОМАТНОГО ПРОГРАММИРОВАНИЯ

М.А.Казаков, А.А.Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики, Санкт-Петербург

Тел.: (812) 247-95-45, e-mail: shalyto@mail.ifmo.ru

Одним из методических приемов [1- 4] при обучении программированию и дискретной математике является разработка визуализаторов классических вычислительных алгоритмов [5, 6].
Визуализатор – это программа, иллюстрирующая выполнение алгоритма при определенных входных данных. Примерами визуализаторов могут служить, например, программа, занимающаяся построением графика функции, либо программа, визуально моделирующая какой-либо физический процесс. Применительно к дискретной математике и программированию, визуализаторы обычно моделируют некоторые алгоритмы, давая возможность обучающемуся при помощи интуитивно понятного интерфейса проходить алгоритм шаг за шагом от начала до конца, а при необходимости, и обратно.
Визуализаторы в рассматриваемой области решают следующие задачи, возникающие в процессе обучения.
1. Графическое и словесное разъяснение действий алгоритма на конкретных наборах входных данных. При этом понимание алгоритма не обязательно, поскольку именно визуализатор должен объяснить действие алгоритма.
2. Предоставление пользователю инструмента, реализующего данный алгоритм. При этом учащийся освобождается от необходимости выполнять шаги алгоритма, так как их автоматически выполняет визуализатор.
Визуализатор выполняет обычно следующие функции:
– пошаговое выполнение алгоритма;
– возможность просмотра действия алгоритма при разных наборах входных данных, в том числе и введенных пользователем;
– возможность просмотра действия алгоритма в динамике;
– возможность перезапуска алгоритма на текущем наборе входных данных.
Динамическая визуализация наглядно демонстрирует такую характеристику алгоритма, как трудоемкость (особенно при пошаговой демонстрации). Для некоторых алгоритмов (например, машины Тьюринга) динамический вариант демонстрации вообще представляется более естественным, чем любой набор статических иллюстраций.
До недавнего времени технология разработки визуализаторов сводилась к эвристике. При этом каждый алгоритм требовал нового подхода и осмысления реализации визуализатора. Другими словами, технология разработки визуализаторов отсутствовала, и основные успехи в этой области были педагогическими [3, 4, 7].
Основным недостатком при построении визуализаторов является то, что обычно используются только такие понятия, как «входные и выходные переменные», а понятие «состояние» в явном виде не используется. Однако, по мнению авторов, совершенно естественным кажется, что каждый шаг визуализации необходимо проводить в соответствующем состоянии или на переходе. Поэтому при построении программ визуализации целесообразно использовать технологию автоматного программирования, базирующуюся на конечных автоматах [8].
В настоящей работе показано, что применение программирования с явным выделением состояний превращает процесс разработки логики визуализаторов в технологию.
Основным требованием к визуализатору является возможность пошаговой реализации алгоритма. Поэтому предлагаемая технология должна преобразовать исходный алгоритм в набор шагов для отображения на экране.
Визуализатор «по-крупному» предлагается строить следующим образом:
– по программе строится автомат логики визуализатора (контроллер – controller);
– выбираются визуализируемые переменные (модель – model);
– проектируется формирователь изображений и комментариев, который преобразует номер состояния и соответствующие значения визуализируемых переменных в «картинку» и поясняющий текст (представление – view).
Такая конструкция визуализатора соответствует одному из основных паттернов проектирования объектно-ориентированных программ, который обозначается аббревиатурой MVC (Model-View-Controller) [9].
Предлагаемая технология основана на методе построения конечного автомата по тексту программы [10]. При этом по указанному тексту строится схема алгоритма, которая на основе соответствующего кодирования преобразуется в граф перехода конечного автомата.
Исходя из изложенного, сформулируем основные этапы технологии построения визуализаторов:
– 1. Постановка задачи.
– 2. Решение задачи (в словесно-математической форме).
– 3. Выбор визуализируемых переменных.
– 4. Анализ алгоритма для визуализации. Анализируется решение с целью определения того, что и как отображать на экране.
– 5. Алгоритм решения задачи.
– 6. Реализация алгоритма на выбранном языке программирования. На этом шаге производится реализация алгоритма, его отладка и проверка работоспособности.
– 7. Построение схемы алгоритма по программе.
– 8. Преобразование схемы алгоритма в граф переходов автомата Мили.
– 9. Формирование набора невизуализируемых переходов.
– 10. Выбор интерфейса визуализатора.
– 11. Сопоставление иллюстраций и комментариев с состояниями автомата.
– 12. Архитектура программы визуализатора.
– 13. Программная реализация визуализатора.
Известно, что обычно создание программы разбивается на пять стадий: разработка требований, анализ, проектирование, реализация и тестирование. В данном случае к разработке требований относятся первые три пункта технологии. Анализ – пункты четыре и пять технологии. К проектированию относятся пункты с шестого по одиннадцатый. В отличие от традиционного для объектно-ориентированного программирования подхода, выбор архитектуры программы относится не к стадии проектирования, а к реализации, так как все предыдущие пункты технологии не зависят от реализации. Естественно, что к стадии реализации относится и последний пункт технологии.
При использовании предлагаемой технологии тестирование резко упрощается, а время написания визуализатора сокращается.
Анализ Интернет-ресурсов в области построения визуализаторов [11-16], а также опыт их разработки и приема у студентов в рамках учебного процесса в 1999/2000 гг. на кафедре «Компьютерные технологии» СПбГУ ИТМО, позволяет утверждать, что предложенный подход является «прорывом» в области построения визуализаторов.

Литература
1. Интернет-школа программирования. http://ips.ifmo.ru/.
2. Казаков М.А., Мельничук О.П., Парфенов В.Г. Интернет-школа программирования в СПбГИТМО (ТУ). Реализация и внедрение // Всероссийская научно-методическая конференция «Телематика'2002». СПб.: 2002. – С.308-309. (http://tm.ifmo.ru/tm2002/db/doc/get_thes.php?id=170).
3. Столяр С.Е., Осипова Т.Г., Крылов И.П., Столяр С.С. Об инструментальных средствах для курса информатики // II Всероссийская конференция «Компьютеры в образовании». СПб.: 1994.
4. Казаков М.А., Столяр С.Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования // Международная научно-методическая конференция «Телематика'2000» . СПб.: 2000. – С.189-191.
5. Кормен Т., Лайзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦМНО, 2000. – 960 с.
6. Кнут Д. Искусство программирования. Т. 1: Основные алгоритмы. М.: Вильямс, 2001. – 712 с.
7. A Testbed for Pedagogical Requirements in Algorithm Visualizations.
8. Шалыто А.А. Технология автоматного программирования // Мир ПК. 2003. №10. С.74-78. http://is.ifmo.ru, раздел «Статьи».
9. Гамма Э., Хэлм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001. – 325 с.
10. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные // Программирование. 2002. № 5. – С.12-26. http://is.ifmo.ru, раздел «Статьи».
11. Gitta D. Tutorial on Visualization. http://www.siggraph.org/education/materials/HyperVis/domik/folien.html.
12. Owen G. S. Visualization Concepts: Overview. http://www.siggraph.org/education/materials/HyperVis/concepts/overview.htm.
13. Complete Collection of Algorithm Animations. http://www.cs.hope.edu/~alganim/ccaa/.
14. Interactive Data Structure Visualizations. http://www.student.seas.gwu.edu/~idsv/idsv.html.
15. Jawaa examples. http://www.cs.duke.edu/csed/jawaa2/examples.html.
16. Sorting Algorithms. http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html.


 



Санкт-Петербург, 7-10 июня 2004 г.
XI Всероссийская научно-методическая конференция "Телематика'2004"