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



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / Разработка логики визуализаторов алгоритмов на основе конечных автоматов (версия для печати)


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



М.А. Казаков, Г.А. Корнеев, А.А. Шалыто

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

Аннотация

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

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

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

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

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

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

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

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

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

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

Литература

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



© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com