УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Разработка логики визуализаторов алгоритмов на основе конечных автоматов

Статья в формате PDF

Аннотация

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

Это открывает возможность использования новой технологии при изучении дискретной математики и программирования [3].

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

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

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

Многолетний опыт построения и применения визуализаторов на кафедре Компьютерные технологии СПбГУ ИТМО показал, что они могут быть использованы как основной инструмент преподавания указанных выше курсов, в частности, при дистанционном обучении (http://ips.ifmo.ru).

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

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

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

Для описания логики работы визуализаторов выбраны автоматы Мура, в которых действия выполняются только в состояниях. Это позволяет отображать операции, выполняемые алгоритмом, наиболее естественным образом.

Литература

1. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. М.: Вильямс, 2000.
2. Кормен Т., Лейзерсон Ч., Ривес Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.
3. Казаков М.А., Столяр С.Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования //Тезисы докладов международной научно-методической конференции "Телематика-2000". СПб.: СПбГИТМО (ТУ), 2000.
4. Шалыто А.А., Туккель Н.И. Программирование с явным выделением состояний //Мир ПК. 2001. № 8, 9.