автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Автоматизация построения визуализаторов алгоритмов дискретной математики на основе автоматного подхода

На правах рукописи

Корнеев Георгий Александрович

Автоматизация построения визуапизаторов алгоритмов дискретной математики на основе автоматного подхода

Специальность 05.13.12 — Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2006

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

Научный руководитель

доктор технических наук, профессор

Шалыто Анатолий Абрамович

Официальные оппоненты

доктор физико-математических наук, профессор

Романовский Иосиф Владимирович

доктор технических наук, профессор

Тропченко Александр Ювенальевич

Ведущая организация

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

Защита диссертации состоится 24 октября 2006 года в 15 часов 50 минут на заседании диссертационного совета Д 212.227.05 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан 22 сентября 2006 г.

Ученый секретарь совета Д 212.227.05, .

кандидат технических наук, доцент

Поляков Владимир Иванович

Общая характеристика работы

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

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

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

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

Многолетний опыт построения и применения визуализаторов на кафедре «Компьютерные технологии» СПбГУ ИТМО показал, что они могут быть использованы как основной инструмент преподавания алгоритмов дискретной математики.

Написание визуализатора «с нуля» является трудоемкой задачей. Для ее решения используются системы визуализации, предоставляющие как средства создания визуализаторов, так и поддержку времени выполнения.

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

Несмотря на то, что визуализаторы разрабатываются с 80-х годов XX века, можно утверждать, что к настоящему времени основные достижения в проектировании визуализаторов относятся к сфере их применения в учебном процессе, а успехи в сфере технологии создания визуализаторов практически отсутствуют. В частности, отсутствует метод, позволяющий по алгоритму формально и единообразно создавать логику работы визуализатора.

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

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

Основные задачи диссертационной работы состоят в следующем.

1. Развитие методов преобразования императивных программ в автоматные.

2. Разработка языка описания визуализаторов алгоритмов дискретной математики.

3. Разработка технологии построения визуализаторов алгоритмов.

4. Внедрение результатов работы в практику программирования визуализаторов и учебный процесс в СПбГУ ИТМО.

Научная новизна, В работе получены следующие научные результаты, которые выносятся на защиту.

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

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

3. Разработан язык описания визуализаторов алгоритмов дискретной математики.

4. На основе предложенных методов преобразования программ к автоматному виду разработана технология, автоматизирующая построение визуализаторов рассматриваемого класса.

Методы исследования. В работе использованы методы теории автоматов, теории графов, теории алгоритмов, теории компиляторов и языков программирования.

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

Практическое значение работы состоит в том, что все полученные результаты могут быть использованы и в настоящее время уже используются на практике в учебном процессе в СПбГУ ИТМО и других учебных учреждений.

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

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

Реализация результатов работы. Результаты, полученные в диссертации, используются на практике следующим образом: I. В учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО при

чтении лекций по курсу «Дискретная математика» и выполнении курсовых работ по

этому курсу. .

, 2. В учебном процессе в Лицее «Физико-техническая школа» (Санкт-Петербург).

.3. В учебном процессе в Специализированном учебно-научном центре МГУ (Москва).

Научно-исследовательские работы. Результаты диссертации были получены в ходе выполнения научно-исследовательских работ по гранту конкурса персональных грантов для студентов и аспирантов вузов и академических институтов Санкт-Петербурга; по теме «Разработка технологии программного обеспечения систем управления на основе автоматного подхода», выполняемой по заказу Министерства образования РФ в 2001-2006 гг.; по теме «Разработка технологии автоматного программирования», выполненной по гранту РФФИ № 02-07-90114 в 2002-2003 гг.; по теме «Разработка технологии объектно-ориентированного программирования с явным выделением состояний»» выполняемой по гранту РФФИ № 05-07-90011; по государственному контракту «Технология автоматного программирования: применение и инструментальные средства», выполняемому в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002 - 2006 годы».

Апробация результатов работы. Основные положения диссертационной работы докладывались на Второй Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ, 2005 г.); II и III конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2005, 2006 гг.); Политехническом симпозиуме «Молодые ученые — промышленности Северо-Западного региона» (Санкт-Петербургский государственный политехнический университет, 2005 г.); Software Engineering Conference in Russia — SECR-2005 (Москва, 2005 г.); научно-методических конференциях «Телематика-2001», «Телематика-2003» (Санкт-Петербург); XXXV научной и учебно-методической конференция СПбГУ ИТМО «Достижения ученых, аспирантов и студентов СПбГУ ИТМО в науке и образовании» (Санкт-Петербург, 2006 г.); на семинаре «Автоматное программирование» в рамках международной конференции «International Computer Science Symposium in Russia CSR 2006» (Санкт-Петербург, 2006 г.).

Публикации. По теме диссертации опубликовало 11 печатных работ, в том числе в Научно-техническом вестнике СПбГУ ИТМО (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»); сборниках трудов конференций «Методы и средства обработки информации», «Телематика», «Межвузовская конференция молодых учёных», Политехнического симпозиума «Молодые ученые — промышленности Северо-Западного региона»; журналах «Телекоммуникации и информатизация образования», «Компьютерные инструменты в образовании».

Структура диссертации. Диссертация изложена на 181 странице и состоит из списка терминов, введения, шести глав, заключения и двух приложений (на 11 страницах). Список литературы содержит 103 наименования. Работа иллюстрирована 50 рисунками и содержит 12 таблиц.

Содержание работы

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

Первая глава содержит описание текущего состояния в области создания и применения визуализаторов и систем визуализации. В частности, рассмотрено применение визуализаторов в учебном процессе и предъявляемые к ним требования.

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

На основе анализа литературы и многолетнего опьгга применения визуализаторов на кафедре «Компьютерных технологий» в СПбГУ ИТМО выделены основные варианты применения визуализаторов алгоритмов в учебном процессе.

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

1. Интерактивность — учащиеся должны иметь возможность задавать наборы входных данных и рассматривать работу алгоритма на них.

2. Двунаправленность — при работе с визуализатором должна быть возможность совершать шаги алгоритма как вперед, так и назад.

3. Автоматический режим работы — визуализаторы должны предоставлять возможность работы без вмешательства пользователя. .

4. История — визуализатор должен обеспечивать возможность пошагового возврата назад, вплоть до начального состояния,

5. Отображение хода выполнения алгоритма ——: визуализатор должен иметь возможность отображать не только изменения в данных, но и другие действия, например, сравнения при сортировке.

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

7. Простота использования — интерфейс визуализатора должен быть интуитивно понятен.

8. Свободный доступ — у учащихся должна быть возможность доступа к визуализаторам не только в аудиториях.

9. Платформ онезависимость — визуализатор должен работать на распространенных аппаратных конфигурациях и операционных системах.

10. Автономность — при работе визуализатор не должен требовать подключения )с вычислительным сетям.

Системы ¡визуализации должны позволять строить визуализаторы, удовлетворяющие ,указанным требованиям. Кроме того, к системам визуализации предъявляются дополнительные требования.

П. Удобство создания визуализаторов — простота использования системы визуализации при разработке визуализаторов.

12. Скорость разработки визуализаторов — возможность разработки визуализаторов на основе уже существующих компонент.

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

• «+» — свойство выполняется;

• «-» — свойство не выполняется;

• «±» — свойство выполняется частично.

Таблица 1. Сравнительные характеристики визуализаторов алгоритмов сортировок

Визуализаторы 1 2 3 4 5 6 7 8 9 10

Brown University — + ± + ± dt — — — —

SUNYBrockport — ± + ± — + — + + +

Princeton University ± — + — — — ± + + +

Hope College — — + — + — + + + +

Jeiiot + — — — + — + + ± +

СПбГУ ИТМО (Казаков MA.) — - + — — + + + + +

Также проанализированы девять систем визуализации алгоритмов (таблица 2).

Таблица 2. Сравнительные характеристики систем визуализации

Система визуализации 1 2 3 4 5 6 7 8 9 10

Animal — + ± ± + + + + +

JAWAA — ± — ± ± + + + — —

BALSA — + ± + ± ± _ — — _

Tango — + + +

XTango — + + — — — _ — — +

Jeiiot + — _ — + — + + — —

Polka + — — ± ± + — + +

Leonardo + + + + +

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

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

Диаграмма вариантов использования визуализатора, построенная в результате анализа материала, изложенного в первой главе, приведена на рис.

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

• логика визуализатора, обеспечивающая возможность трассировки алгоритма;

• модель данных, хранящая вычислительное состояние алгоритма;

• визуальное представление — часть визуализатора, определяющая, что и как будет отображаться пользователю в интересных состояниях;

• набор комментариев, определяющий какие комментарии будут отображаться пользователю в каждом интересном состоянии;

• элементы управления, позволяющие пользователю управлять визуализатором;

• интерфейс визуализатора, определяющий каким образом части визуализатора отображаются на экране;

• проектная документация, описывающая разработанный визуализатор.

Модель

Задание входных

I

рСно&памю дни

-

Логик* ■мэуалмэтое*

Перймимение по алгоритму

П

Получение состояния «лгоритма

Э1ММН1Ы

I

е

Н«бор комимпрма

Управление аиаумммгтором

I

1—|—1 Ви:

I—) пред

Вкаумаыю*

Прсяетявгмииа

Комментарий к

сосгоипнию ^влгор™«___

I

Иэобршмнне состоянии апкфитма

Имгерфейс •мушноатор«

I

I дааумвиццт

Интерфейс пользой*«!*

I

Руководство пользователя

Попьхнотел»

Рис. 2. Диаграмма компонентов основных частей виэуализатора

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

• метод автоматизации построения модели данных по программе;

• метод построения программ, обеспечивающий трассировку исходной программы в прямом и обратном направлениях;

• язык описания визуализаторов.

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

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

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

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

Построение модели данных по программе можно разбить на два этапа:

1. Создание модели данных по программе.

2. Модификация программы к виду, использующему модель данных.

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

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

X. Выражение (expression).

2. Составной оператор ({ ... }).

3. Укороченный оператор ветвления (if-then).

4. Полный оператор ветвления (if-then-else).

5. Цикл с предусловием (while).

6. Оператор вызова процедуры.

7. Цикл с постусловием (do).

8. Цикл со счетчиком (for).

9. Оператор продолжения цикла (continue).

10. Оператор выхода из цикла (break),

11. Оператор возврата из процедуры (return).

12. Оператор выбора (switch).1

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

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

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

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

Построение автомата по процедуре будем выполнять постепенно — от листьев дерева к корню. Для такого построения требуется ввести новые термины.

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

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

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

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

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

Для обеспечения обратимого исполнения будем строить пары автоматов, состоящие из прямого и обратного автоматов. Прямой автомат будет обеспечивать трассировку программы в прямом направлении, а обратный автомат — трассировку в обратном направлении.

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

образом, пара автоматов может быть рассмотрена как один автомат с двумя функциями переходов.

На основе пар автоматов разрабатываются методы построения систем конечных автоматов, обеспечивающих обратимое исполнение. Предлагаемые методы обобщены в таблице 3.

Таблица 3. Варианты построения прямого и обратного автоматов

Особенности обращения Непосредственное обращение Косвенное обращение

Оператор присваивания Ветвления и циклы Последовательности операторов

1 2 3 4 5

Формализм неформальный формальный формальный формальный

Тип автоматов Мура Мура смешанный Мура

Стек не требуется один не требуется

Модификация прямого автомата не требуется требуется

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

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

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

а б

Рис. 3. Фрагменты прямого (а) и обратного (б) автоматов, вызывающие автомат А

Предложенные методы проиллюстрированы на программе, осуществляющей поиск максимума в массиве натуральных чисел: int шах »0;

for (int i » О; i < a.length; i++) { if (max < a[il) max = a[i] ;

}

Пара автоматов, построенная при использовании методов, соответствующих столбцам 3 и 4 таблицы 3, приведена на рис. 4.

Г 0. Начально* состоят« J

i

f 1, Им*циална&4>1й

. ©m*x« 0 %

i

r 2. Нвчело цикла «с

J

tru«

atecfcputWabe)

/ Э. фил \

/- 4. Уело«** -\

\

G

Начальное состояние

)

I ®ГТИ1 < Öal®I|

f V Инициализация ^

г6. Обновление максимуме^

H»g*-f>utft<@™t) t em«»®»[2Ч j

bu*

, Bleck. push(true)

г 5. Условие (окончание) ^

atack.popQ V__/

r 7. Начало цикла >

■ stack.popO

T -atedtpopQ

С

■ @9.>*пэт

б Конечно« состояние

D

f 7. ИнффнАнт

Ч ftftdcpuahf®) 1 J

У Um*

true

CE

Конечное оостоянив

3

r 4', Условие 1

t

(6\ Обновление максимума ^

ч @ma* ■ stock pop()

1 ttack.popQ

( В', /споена (окончание) ^

\

t

r 7\ Инфвмвнт 1

V ei * etecKpopQ

stack, puGft(1ru*)

POPO

а б

Рис. 4. Прямой (а) и обратный (6) автоматы для процедуры поиска максимума

Для предложенных методов при помощи структурной индукции доказываются следующие основные свойства:

1. Адекватность — система автоматов выполняет те же действия, что и исходная программа.

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

3. Непротиворечивость — условия на переходах из одного состояния не могут быть истинными одновременно (все попарные конъюнкции условий на переходах должны быть невыполнимы).

4. Отсутствие недостижгшых состояний — любое состояние может быть достигнуто по переходам из начального состояния.

5. Обратимость — при выполнении действий обратного автомата будут восстановлены исходные значения всех переменных, при условии, что в точке входа они были такими же, как в точке выхода при прямом проходе.

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

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

В пятой главе предлагается язык описания визуализаторов, основанный на XML. При этом отдельно рассматриваются структуры описаний визуализируемого алгоритма и конфигурации визуализатора.

Описание визуализатора алгоритма можно разбить на две основные части:

1. Описание визуализируемого алгоритма, позволяющее автоматизировать реализацию: модели данных, логики визуализатора, набора комментариев, связи с визуальным представлением.

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

Первая часть описания создается один раз в процессе разработки визуализатора и после этого не изменяется. Вторая — позволяет настраивать визуализатор под конкретное окружение, например, языковое.

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

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

Для оператора может быть указан его уровень, шаблон комментария и связь с визуальным представлением. Шаблон комментария''определяет вид и ' параметры комментария, отображаемого на данном шаге. Связь с визуальным представлением позволяет обновлять визуальное представление при отображении шага.

Корневым элементом конфигурации является элемент configuration. Конфигурация может содержать следующие элементы:

• Описания групп (элемент group), СВОЙСТВ (property) И сообщений (message).

• Описания таблиц стилей (style и style-set), шрифтов (font), цветов (color).

• Описание элементов управления: панелей (panel), кнопок (button), панелей выбора (adjustablePanel).

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

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

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

Система визуализации Vizi состоит из двух основных частей: динамической, функционирующей во время исполнения визуализатора, и статической, работающей на этапе создания визуализатора.

Динамическая часть состоит из библиотеки времени исполнения и кода, сгенерированного по описанию визуализатора. При этом динамическая часть фиксирует структуру визуализатора.

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

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

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

При этом считается, что время, затраченное на построение программы, примерно пропорционально размеру ее кода.

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

Отметим сходства и различия Vizi и BaseApplet, влияющие на сравнение:

1. При построении визуализаторов используется единый язык и стиль программирования.

2. Визуализаторы выполнялись людьми примерно одинаковой квалификации.

3. К проектам визуализаторов предъявлялись схожие требования.

4. Vizi содержит средства автоматизации построения визуализаторов, разработанные на основе предложенных методов.

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

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

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

Список визуализаторов, построенных на основе системы визуализации Vizi в 2003-2004 учебном году, представлен в таблице 5. Здесь в столбце «А» обозначено количество пар автоматов, а в столбце «С» — суммарное количество состояний в них. В общей сложности с 2003 по 2006 год на основе системы Vizi было построено более 80 визуализаторов алгоритмов.

Таблица 4. Сравнение размеров исходного кода визуализаторов

Алгоритм BaseApplet Vizi Уменьшение размера

Автор Общий размер (КБ) Автор Общий размер (КБ)

Алгоритм Бойера-Мура Пак С. 18.69 Наумов Р. 12.06 35.5%

Поиск двусвязных компонент графа Кузнецов А. 26.54 Коломейцева О. 22.87 13.8%

Обход графа в ширину и глубину Прощенко Ю. 32.34 Гунич И. 25.20 22.1%

Алгоритм Форда-Фалкерсона Штучкин А. 45.80 Кулев В. 26.57 42.0%

Алгоритм Форда-Беллмана Гаврил ов М. 51.39 Кулагин Д. 26.08 493%

Дерево отрезков Дронь В. 61.01 Лагунов И. 27.63 54.7%

2-3 деревья Суясов Д. 82.28 Постников Д. 33.20 59.6%

Красно-черные деревья Краюхин Д. 95.20 Акишев И. 62.50 34.4%

Таблица 5. Визуализаторы, выполненные на основе Vtzi

Алгоритм Автор А С

Построение кратчайшего дерева в ориентированном графе Пименов С. 2 26

Битоническяй алгоритм для задачи коммивояжера Красильников Н. 2 25

2-3 Деревья Красильников Н. 14 195

Циклы и разрезы в графах Ахметов И. 16 97

Алгоритм Укконена Ахметов И. 2 56

Алгоритм Прима Ярцев Б. 2 21

Генерация всех простых строк и построение цикла де Брюина Лоторейчик В. 2 21

Работа со стеком Поликарпова Н. 14 54

Венгерский алгоритм Кудинов М. S 46

Нахождение максимального потока в сети методом Малхотры-Кумара-Махешвари Бедный Ю. 18 89

Нахождение максимального потока в сети методом Диница Бедный Ю. 8 68

Алгоритм Штрассена Котов А. 2 16

Алгоритм Флойда Колыхматов И. 2 47

Сортировка слиянием Парашенко Д. 6 31

Быстрая сортировка Кочелаев Д. 4 40

Дерево отрезков Вокин А. 2 15

Сортировка кучей Пименов И. 8 38

Алгоритм Краскала Данилов В. 6 32

Система визуализации Vizi (как и ее предшественник BaseApplet) была использована

в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО, лицее «Физико-техническая школа» (Санкт-Петербург), специализированном учебно-научном центре МГУ (Москва).

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

Заключение В диссертации получены следующие результаты:

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

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

3. Разработан язык описания визуализаторов алгоритмов дискретной математики.

А. На основе предложенных методов преобразования программ к автоматному

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

5. Результаты работы были внедрены в учебном процессе различных учебных заведений.

Список публикаций

1. Корнеев Г.А., Шалыто A.A. Преобразование программ в систему взаимодействующих конечных автоматов / Труды Второй Всероссийской Научной конференции «Методы и средства обработки информации». М.: МГУ. 2005, с. 385-387.

2. Корнеев Г. А. Метод преобразования программ в систему взаимодействующих автоматов / Труды II межвузовской конференции молодых учёных. СПб.: СПбГУ ИТМО. 2005, с. 65-72.

3. Корнеев Г. А. Технология разработки визу ализато ров алгоритмов /Труды I! межвузовской конференции молодых учёных. СПб.: СПбГУ ИТМО, 2005, с. 18-23.

4. Казаков М.А., Корнеев Г.А., Шалыто A.A. Разработка логики визуализаторов алгоритмов на основе конечных автоматов // Телекоммуникации и информатизация образования. 2003. № 6, с. 27-58.

5. Корнеев Г.А., Васильев В.Н., Парфенов В.Г., Столяр С.К Визуализаторы алгоритмов как основной инструмент технологии преподавания дискретной математики и программирования / Труда международной научно-методической конференции «Телематика-2001». СПб.: СПбГИТМО (ТУ). 2001, с. 119,120.

6. Корнеев Г.А., Шалыто A.A. Реализация конечных автоматов с использованием объектно-ориентированного программирования / Труды X международной научно-методической конференции «Телематика-2003». СПб.: СПбГИТМО (ТУ). 2003, с. 377, 378.

7. Корнеев Г.А., Казаков М.А., Шалыто A.A. Построение логики работы визуализаторов алгоритмов на основе автоматного подхода /Труды X международной научно-методической конференции «Телематика-2003». СПб.: СПбГИТМО (ТУ). 2003, с. 378, 379.

8. Корнеев Г.А., Шамгунов H.H., Шалыто A.A. Обход деревьев на основе автоматного подхода // Компьютерные инструменты в образовании. 2004. № 3, с. 33-37.

9. Корнеев Г.А. Преобразование программы в систему взаимодействующих автоматов, допускающих двустороннюю трассировку / Материалы политехнического симпозиума 2005 «Молодые ученые — промышленности Северо-Западного региона». СПб.: Политехнический университет. 2005, с. 33,34.

10. Корнеев Г.А., Шалыто A.A. Построение визуализаторов алгоритмов дискретной математики //Научно-технический вестник СПбГУ ИТМО. Выпуск 23. Высокие технологии в оптических и информационных системах. СПб.: СПбГУ ИТМО. 2005, с.118-129.

11. Корнеев Г.А., Шалыто A.A. VIZI — язык описания логики визуализаторов алгоритмов //Научно-технический вестник СПбГУ ИТМО. Выпуск 23. Высокие технологии в оптических и информационных системах. СПб.: СПбГУ ИТМО. 2005, с. 130-138.

Тиражирование и брошюровка выполнены в центре «Университетские телекоммуникации» Санкт-Петербург, Саблинская ул. 14; тел: (812)233-46-69 Тираж 100 экз.

ОГЛАВЛЕНИЕ.

СПИСОК ТЕРМИНОВ.

ВВЕДЕНИЕ.

ГЛАВА 1. СИСТЕМЫ ВИЗУАЛИЗАЦИИ АЛГОРИТМОВ ДИСКРЕТНОЙ

МАТЕМАТИКИ.

1.1. Применение визуализаторов в учебном процессе.

1.1.1. Варианты применения визуализаторов.

1.1.2. Требования к визуализаторам алгоритмов.

1.2. Обзор визуализаторов на примере алгоритмов сортировок.

1.2.1. Подходы к визуализации алгоритмов сортировки.

1.2.2. Обзор визуализаторов алгоритмов сортировок.

1.2.3. Анализ визуализаторов алгоритмов сортировок.

1.3. Обзор систем визуализации.

1.3.1. Развитие систем визуализации.

1.3.2. Классификация систем визуализации.

1.3.3. Обзор общих систем визуализации.

1.3.4. Обзор систем визуализации алгоритмов.

1.3.5. Анализ систем визуализации.

Выводы по главе 1.

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

2.1. Структура визуализатора.

2.1.1. Варианты использования визуализатора.

2.1.2. Выделение основных частей визуализатора.

2.2. Разработка визуализаторов.

2.2.1. «Ручная» разработки визуализаторов.

2.2.2. Автоматизация разработки визуализаторов.

2.3. Модель данных визуализатора.

2.3.1. Требования к модели данных.

2.3.2. Подходы к построению модели данных.

2.4. Логика визуализатора.

2.4.1. Требования к логике визуализатора.

2.4.2. Подходы к реализации обратимого исполнения.

2.4.3. Автоматный подход к построению логики визуализаторов.

2.5. Язык описания визуализаторов.

2.6. Задачи, решаемые в диссертационной работе.

Выводы по главе 2.

ГЛАВА 3. ПОСТРОЕНИЕ МОДЕЛИ ДАННЫХ И ПРЕОБРАЗОВАНИЕ

ПРОГРАММЫ К ПРИВЕДЕННОЙ ФОРМЕ.

3.1. Построение модели данных.

3.1.1. Этапы построения модели данных.

3.1.2. Требования к исходной программе.

3.2. Построение модели данных по итеративной программе.

3.2.1. Создание модели данных.:.

3.2.2. Модификация программы.

3.2.3. Упрощенная запись (@-нотация).

3.2.4. Пример построения модели данных.

3.3. Построение модели данных по рекурсивной программе.

3.3.1. Построение модели данных.

3.3.2. Модификация программы.

3.3.3. Пример выделения модели и модификации программы.

3.3.4. Обращение правил именования.

3.4. Преобразование программы к приведенной форме.

3.4.1. Типы операторов.

3.4.2. Оператор цикла с постусловием.

I 3.4.3. Оператор цикла со счетчиком.!.

3.4.4. Оператор продолжения цикла.

3.4.5. Оператор выхода из цикла.

3.4.6. Оператор возврата из процедуры.

3.4.7. Оператор выбора.

3.4.8. Порядок преобразования операторов.

Выводы по главе 3.

ГЛАВА 4. ПРЕОБРАЗОВАНИЕ ПРОГРАММЫ В СИСТЕМУ

ВЗАИМОДЕЙСТВУЮЩИХ КОНЕЧНЫХ АВТОМАТОВ.

4.1. Основные понятия.

4.1.1. Исходная программа.

4.1.2. Фрагменты автоматов.

4.2. Преобразование процедуры в автомат.

4.2.1. Оператор присваивания.

4.2.2. Последовательность операторов.

4.2.3. Оператор вызова процедуры.

4.2.4. Оператор ветвления.

4.2.5. Цикл с предусловием.

4.2.6. Завершение построения автомата.

4.2.7. Пример преобразования процедуры в автомат.

4.3. Построение обратного автомата.

4.3.1. Обратные автоматы.

4.3.2. Обращение операторов.

4.3.3. Обращение оператора присваивания.

4.3.4. Обращение последовательности операторов.

4.3.5. Обращение оператора вызова.

4.3.6. Обращения операторов ветвления.

4.3.7. Обращение оператора цикла с предусловием.

4.3.8. Варианты построения обратного автомата.

4.3.9. Пример построения обратного автомата.

4.4. Процедуры и вызовы автоматов.

4.4.1. Итеративные программы.

4.4.2. Рекурсивные программы.

4.5. Формализация преобразования программы.

4.5.1. Свойства автоматов.

4.5.2. Текстовая нотация.

4.5.3. Преобразование оператора присваивания.

4.5.4. Преобразование оператора ветвления.

4.5.5. Преобразование оператора цикла.

4.5.6. Преобразование оператора вызова процедуры.

4.5.7. Преобразование последовательностей операторов.

4.5.8. Преобразование процедуры.

4.5.9. Завершение доказательства.

Выводы по главе 4.

ГЛАВА 5. ЯЗЫК ОПИСАНИЯ ВИЗУАЛИЗАТОРОВ.

5.1. Структура языка.

5.2. Описание визуализируемого алгоритма.

5.2.1. Описание алгоритма.

5.2.2. Описание процедур.

5.2.3. Описание операторов.

5.2.4. Переменные.

5.2.5. Пример описания визуализируемого алгоритма.

5.3. Описание конфигурации визуализатора.

5.3.1. Группы, свойства и сообщения.

5.3.2. Таблицы стилей.

5.3.3. Элементы управления.

Выводы по главе 5.

ГЛАВА 6. ВНЕДРЕНИЕ ПРЕДЛОЖЕННЫХ МЕТОДОВ.

6.1. Система визуализации Vizi. t 6.1.1. Структура визуализатора.

6.1.2. Статическая часть.

6.1.3. Отладка описания визуализатора.

6.1.4. Процесс построения визуализатора.

6.2. Пример построения визуализатора.

6.2.1. Постановка задачи и анализ литературы.

6.2.2. Создание визуализируемой программы.

6.2.3. Проектирование визуализатора.

6.2.4. Построение описания визуализируемой программы.

6.2.5. Реализация визуального представления.

6.2.6. Реализация элементов управления.

6.2.7. Интеграция и отладка визуализатора.

6.2.8. Выводы.

6.3. Сравнение с существующими подходами.

6.3.1. Сравнение проектов визуализаторов.

6.3.2. Визуализаторы, построенные на основе Vizi.

6.3.3. Выполнение требований к визуализаторам.

6.4. Практическое использование результатов работы.

Выводы по главе 6.

Актуальность проблемы. В настоящее время приборы и устройства становятся все сложнее. Для автоматизации их проектирования требуется знание алгоритмов на графах [17,22], операций над матрицами [20], вычислительной геометрии [27], линейного и динамического программирования [5,18] и т.д. Часто эти алгоритмы являются весьма сложными и, поэтому, трудны для изучения. Это требует новых подходов к разработке научных основ обучения автоматизированному проектированию, и, в частности, обучению указанным алгоритмам [11, 97]. Таким новым подходом является применение визуализаторов алгоритмов [34]. Так как указанные алгоритмы часто сложны, то создание их визуализаторов требует разработки методов построения визуализаторов с целью формализации процесса их проектирования и реализации.

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

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

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

Многолетний опыт построения и применения визуализаторов на кафедре «Компьютерные технологии» СПбГУ ИТМО [97] показал, что они могут быть использованы как основной инструмент преподавания указанных выше курсов, и, в частности, при дистанционном обучении [10].

Написание визуализатора «с нуля» является трудоемкой задачей. Для ее решения используются системы визуализации, предоставляющие как средства создания визуализаторов, так и поддержку времени выполнения.

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

Несмотря на то, что визуализаторы разрабатываются с 80-х годов XX века, можно утверждать, что к настоящему времени основные достижения в проектировании визуализаторов относятся к сфере применения их в учебном процессе [11], а успехи в сфере технологии создания визуализаторов практически отсутствуют. В частности, отсутствует метод, позволяющий по алгоритму формально и единообразно создавать логику работы визуализатора.

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

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

Основные задачи диссертационной работы состоят в следующем.

1. Развитие методов преобразования императивных программ в автоматные.

2. Разработка языка описания визуализаторов алгоритмов дискретной математики.

3. Разработка технологии построения визуализаторов алгоритмов.

4. Внедрение результатов работы в практику программирования визуализаторов и учебный процесс в СПбГУ ИТМО.

Научная новизна. В работе получены следующие научные результаты, которые выносятся на защиту.

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

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

3. Разработан язык описания визуализаторов алгоритмов дискретной математики.

4. На основе предложенных методов преобразования программ к автоматному виду разработана технология, автоматизирующая построение визуализаторов рассматриваемого класса.

Методы исследования. В работе использованы методы теории автоматов, теории графов, теории алгоритмов, теории компиляторов и языков программирования.

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

Практическое значение работы состоит в том, что все полученные результаты могут быть использованы и в настоящее время уже используются на практике в учебном процессе в СПбГУ ИТМО и других учебных учреждений.

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

Эти методы реализованы в системе визуализации Vizi, существенно упрощающей и ускоряющей процесс создания визуализаторов алгоритмов за счет автоматизации некоторых операций.

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

Реализация результатов работы. Результаты, полученные в диссертации, используются на практике следующим образом:

1. В учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО при чтении лекций по курсу «Дискретная математика» и выполнении курсовых работ по этому курсу.

2. В учебном процессе в Лицее «Физико-техническая школа» (Санкт-Петербург).

3. В учебном процессе в Специализированном учебно-научном центре МГУ (Москва).

Научно-исследовательские работы. Результаты диссертации были получены в ходе выполнения научно-исследовательских работ по гранту конкурса персональных грантов для студентов и аспирантов вузов и академических институтов Санкт-Петербурга; по теме «Разработка технологии программного обеспечения систем управления на основе автоматного подхода», выполняемой по заказу Министерства образования РФ в 2001-2006 гг.; по теме «Разработка технологии автоматного программирования», выполненной по гранту РФФИ №02-07-90114 в

2002-2003 гг.; по теме «Разработка технологии объектно-ориентированного программирования с явным выделением состояний», выполняемой по гранту РФФИ №05-07-90011; по государственному контракту «Технология автоматного программирования: применение и инструментальные средства», выполняемому в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002 - 2006 годы».

Апробация результатов работы. Основные положения диссертационной работы докладывались на Второй Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ, 2005 г.); II и III конференции молодых ученых СПбГУ ИТМО (Санкт-Петербург, 2005, 2006 гг.); Политехническом симпозиуме «Молодые ученые — промышленности Северо-Западного региона» (Санкт-Петербургский государственный политехнический университет, 2005 г.); Software Engineering Conference in Russia — SECR-2005 (Москва, 2005 г.); научно-методических конференциях «Телематика-2001», «Телематика-2003» (Санкт-Петербург); XXXV научной и учебно-методической конференция СПбГУ ИТМО «Достижения ученых, аспирантов и студентов СПбГУИТМО в науке и образовании» (Санкт-Петербург, 2006 г.); на семинаре «Автоматное программирование» в рамках международной конференции «International Computer Science Symposium in Russia CSR 2006» (Санкт-Петербург, 2006 г.).

Публикации. По теме диссертации опубликовано 11 печатных работ, в том числе в Научно-техническом вестнике СПбГУ ИТМО (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»); сборниках трудов конференций «Методы и средства обработки информации», «Телематика», «Межвузовская конференция молодых учёных», Политехнического симпозиума «Молодые ученые — промышленности Северо-Западного региона»; журналах «Телекоммуникации и информатизация образования», «Компьютерные инструменты в образовании».

Структура диссертации. Диссертация изложена на 181 странице и состоит из списка терминов, введения, шести глав, заключения и двух приложений (на 11 страницах). Список литературы содержит 103 наименования. Работа иллюстрирована 50 рисунками и содержит 12 таблиц.

Выводы по главе 6

1. Разработана система визуализации Vizi.

2. Выполнено сравнение с предшествующей системой построения визуализаторов, которое показало, что система визуализации Vizi позволяет сократить объем кода визуализатора.

3. Показано, что система визуализации Vizi позволяет выполнить все требования к визуализаторам, сформулированные в главе 1.

4. Система визуализации Vizi успешно внедрена в учебный процесс.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Система визуализации Vizi была внедрена на кафедре «Компьютерные технологии» СПбГУ ИТМО (2003-2006 гг.). Визуализаторы, созданные на ее основе внедрены в учебном процессе в Лицее «Физико-техническая школа» (Санкт-Петербург) и специализированном учебно-научном центре МГУ (Москва).

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

Таким образом, результаты, достигнутые в данной работе, существенно изменяют процесс построения визуализаторов. Формализация процесса построения визуализаторов позволяет использовать менее квалифицированные кадры, в частности, студентов, что полезно при изучении сложных алгоритмов, применяемых в САПР приборов и устройств.

1. Автоматы / Ред. Шеннона К.Э., МакКарти Дж. М.: Изд-во иностр. лит., 1956.

2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии иинструменты. М.: Вильяме. 2001.

3. Буч Г., Якобсон А., Рамбо Дж. UML. 2-е издание. СПб.: Питер, 2006, 736 с.

4. Баранов С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Д.: Энергия, 1979.

5. Батищев Д. И., Львович Я. Е., Фролов В. Н. Оптимизация в САПР. Воронеж: Воронежский государственный университет, 1997.

6. Гаврилов М. А. Теория релейно-контактных схем. М.: Изд-во АН СССР, 1 1950.

7. Глушков В. М. Синтез цифровых автоматов. М.: Изд-во физ.-мат. лит., 1962.

8. ГрисД Наука программирования. М.: Мир, 1984.

9. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975.

10. Казаков М. А., Мельничук О. П., Парфенов В. Г. Интернет-школапрограммирования в СПбГИТМО. Реализация и внедрение / Труды международной научно-методическая конференции «Телематика-2002». СПб.: СПбГИТМО (ТУ), 2002.

11. Казаков М. А., Столяр С. Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования i / Труды международной научно-методическая конференции «Телематика2000». СПб.: 2000.

12. Казаков М. А., ШалытоА.А. Использование автоматного программирования для реализации визуализаторов // Компьютерные инструменты в образовании. 2004. № 2.

13. КазаковМ. А., ШалытоА.А. Реализация анимации при построении визуализаторов алгоритмов на основе автоматного подхода // Информационно-управляющие системы. 2005. № 4.

14. КазаковМ. А., ШалытоА. А. Автоматный подход к реализации анимации в визуализаторах алгоритмов // Компьютерные инструменты в образовании. 2005. № 3.

15. Казаков М. А., ШалытоА.А., ТуккельН.И. Использование автоматного подхода для реализации вычислительных алгоритмов / Труды международной научно-методической конференции «Телематика-2001». СПб.: СПбГИТМО (ТУ), 2001.

16. Клини С. Представление событий в нервных сетях и конечных автоматах /В1.

17. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. М.: Вильяме, 2000.

18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.

19. КорнеевГА., ШалытоА.А., ШамгуновН.Н. Паттерн State Machine для объектно-ориентированного проектирования автоматов // Информационно-управляющие системы. 2004. № 5.

20. Ли К. Основы САПР (CAD/CAM/CAE). СПб.: Питер, 2004.21 .ЛингерР., МиллсХ., УиттБ. Теория и практика структурного программирования. М.: Мир, 1982.

21. Мелихов А. Н., Бернштейн Л. С., КурейчикВ. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

22. Мур Э. Умозрительные эксперименты с последовательными машинами /В 1.

23. Рабин М.О., Скотт Д. Конечные автоматы и задачи их разрешения // Кибернетический сборник. Вып. 4. М.: Изд-во иностр. лит., 1962.

24. Столяр С. Е., Остова Т. Г., Крылов И. П., Столяр С. С. Об инструментальных средствах для курса информатики / II Всероссийская конференция «Компьютеры в образовании». СПб, 1994.

25. Туккель Н. И., Шалыто А. А., Шамгунов Н. Я. Реализация рекурсивных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2002. № 5.

26. ФоксА., ПраттМ. Вычислительная геометрия: применение в проектировании и на производстве. М.: Мир, 1982.

27. ХопкрофтД., МотваниР., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильяме, 2001.

28. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

29. Шалыто А.А., Туккель Н. И. Преобразование итеративных алгоритмов автоматные //Программирование. 2002. № 5.

30. Шалыто А.А. Туккель Н.И. От тьюрингова программирования к автоматному // Мир ПК. 2002. № 2.

31. Печатные издания на английском языке

32. BaeckerR. Sorting out Sorting / SIGGRAPH 1981, Dallas, Texas.

33. Baker J.E., Cruz I. F., Liotta G., Tamassia R. The Mocha Algorithm Animation System /Proceedings of International Workshop on Advanced Visual Interfaces. 1996.

34. Brown M. Algorithm Animation. MIT Press, Cambridge, MA, 1988.

35. Brown M. Zeus: a System for Algorithm Animation / Proceedings of 1991 IEEE Workshop on Visual Languages. 1991.

36. BrownM., SedgewickR. A system for Algorithm Animation /Computer Graphics, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, July 1984.

37. Crescenzi P., Demetrescu C., Finocchi /., Petreschi R. Reversible execution and visualization of programs with Leonardo // Journal of Visual Languages and Computing (JVLC). Volume 11. Issue 2, Academic Press, April 2000.

38. Demetrescu C., Finocchi I. A technique for generating graphical abstractions of program data structures / Proceedings of the 3rd International Conference on Visual Information Systems. Amsterdam, 1999.

39. Dijkstra E.W. Go To Statement Considered Harmful // Communications of the ACM. Volume 11. No. 3, March 1968.

40. Huffman D.A. The Synthesis of Sequential Switching Circuits // J. Franclin Inst. 1954. V.257, № 3,4.

41. Italiano G., Cattaneo G., Ferraro U., Scarano V. CATAI: Concurrent Algorithms and Data Types Animation over the Internet / Proceedings of 15th IFIP World Computer Congress. Vienna, August September 1998.

42. Joy В., Steele G., Gosling J., Bracha G. Java Language Specification (Second Edition). Addison-Wesley. 2000.

43. Kane G. MIPS RISC architecture. Prentice-Hall, N.J., 1988.

44. Knowlton K. L6: Bell Telephone Laboratories Low-Level Linked List Language / 16-minute black-and-white film. Murray Hill, N.J., 1966.

45. Knowlton K. L6: Part II. An Example of L6 Programming / 30-minute black-and-white film, Murray Hill, N.J., 1966.

46. Lahtinen S., Sutinen E., Tarhio J. Automated Animation of Algorithms with Eliot // Journal of Visual Languages and Computing. 9 (3). 1998.

47. Lawrence A., BadreA., StasskoJ. Empirically evaluating the use of animations to teach algorithms / Technical report. Graphics Visualization and Usability Center, Georgia Institute of Technology. 1993.

48. McCulloch W., Pitts W. A Logical Calculus of Ideas Immanent in Nervous Activity// Bull. Math. Biophysics. 1943,5.51 .Mealy G. A Method for Synthesizing Sequential Circuits //Bell System Technical Journal. 1955. V.34. № 5.

49. Moreno A., MyllerN. Producing an Educationally Effective and Usable Tool for Learning, The Case of the Jeliot Family // Proceedings of International Conference on Networked e-learning for European Universities.

50. Moreno A., MyllerN., Sutinen E., Ben-AriM. Visualizing Programs with Jeliot 3 / Proceedings of the International Working Conference on Advanced Visual Interfaces AVI 2004, Gallipoli (Lecce), Italy, 25-28 May, 2004.

51. PiersonW., Rodger S.H. Web-based Animation of Data Structures Using JAWAA / Twenty-ninth SIGCSE Technical Symposium on Computer Science Education. 1998.

52. Programming Language FORTRAN. American National Standards Institute (ANSI). 1978.

53. Programming Langauges — C. ISO/IEC 9899:1999.1999.

54. Rodger S. H. Using Hands-on Visualizations to Teach Computer Science from Beginning Courses to Advanced Courses / Second Program Visualization Workshop, Hornstrup Centert, Denmark, June 2002.

55. Rodger S. H. Introducing Computer Science Through Animation and Virtual Worlds / Thirty-third SIGCSE Technical Symposium on Computer Science Education. 2002.

56. Rdfiling G., Freisleben B. ANIMAL: A System for Supporting Multiple Roles in Algorithm Animation //Journal of Visual Languages and Computing, Volume 13 issue 3. Elsevier, Amsterdam, Netherlands, 2002.

57. RuknetC. The Design of the Processor Architecture Capable of forward and Reverse Execution / Proceedings of IEEE SoutheastCon 91. V.2,1991.

58. Stasko J. Tango: A Framework and System for Algorithm Animation // IEEE Computer. 23,1990.

59. Stasko J. Animating Algorithms with XTANGO // SIGACT News, volume 23, issue 2, Spring 1992.

60. Stasko J. Tango: A Framework and System for Algorithm Animation // IEEE Computer, September 1990.

61. Stasko J. A methodology for building Application-Specific Visualizations of Parallel Programs //Journal of Parallel and Distributed Computing. 1993, № 18.

62. Thompson K. Regular expression Search Algorithm //Communications of the ACM. 1966. V.ll. № 6.

63. Wilson J., Aiken R. KatzL Review of animation systems for algorithm understanding /SIGCSE'96, Proceedings of the 1st conference on integrating technology into computer science education, Volume 28 Issue SI.

64. Zelkowitz M. V. Reversible Execution // Communication of the ACM. 1973. V. 16, №9.1. Ресурсы сети Internet

65. Визуализатор пирамидальной сортировки / http://is.ifmo.ru/works/heapsort/

66. Кафедра «Технологии программирования» СПбГУ ИТМО / http://is.ifmo.ru.

67. Agat: Another Graphical Animation Tool / http://www-sop.inria.fr/cafe/Olivier.Arsac/agat/agat.html.

68. Animal Home Page / http://www.animal.ahrgr.de.

69. Apache Ant Home Page / http://ant.apache.org/.

70. Arsac 0., Lavirotte S. The Agat Manual / http://www-sop.inria.fr/cafe/01ivier. Arsac/agat/Doc/refman.ps.gz.

71. Code conventions for Java programming language. /http://Java.sun.com/docs/codeconv/.

72. Дискретная математика: алгоритмы / http://rain.ifmo.ru/cat.

73. Extensible Markup Language (XML) Version 1.0 (Second Edition) / http://www.w3.org/TR/2000/REC-xml-200Q 1006/.

74. Font class description (Java 2 Platform SE 1.4.2) /http://Java.sun.com/i2se/api/Java/awt/Font.html.

75. Hope College animator page /http://www.cs.hope.edu/~alganim/animator/Animator.html.

76. Jeliot Home Page / http://cs.ioensuu.fi/ieliot/.

77. Leonardo home page / http://www.dis.uniromal .it/~demetres/Leonardo/Leonardo.html.

78. MessageFormat class description (Java 2 Platform SE 1.4.2) /http://Java.sun.com/i2se/api/Java/text/MessageFormat.html.

79. Polka Animation System /http://www.cc.gatech.edu/gvu/softviz/parviz/polka.html.

80. Princeton University animators collection / http.7/www.cs.princeton.edu/~ah/alg anim/versionl/Animator.html.

81. Properties class description (Java 2 Platform SE 1.4.2) /http://Java.sun.com/i2se/api/Java/util/Properties.html.

82. Samba algorithm animation system /http://www.cc.gatech.edu/gvu/softviz/algoanim/samba.html.

83. State University of New York College at Brockport sorting animators collection / http://www.cs.brockport.edu/cs/Javasort.html.

84. Vizi home page / http://ctddev.ifmo.ru/vizi

85. XML Schema Part 0: Primer /http://www.w3.org/TR/2001/REC-xmlschema-0-200105Q2/.

86. XML Schema Part 1: Structures / http://www.w3 .org/TR/2001/REC-xml schema-1 -20010502/.

87. XML Schema Part 2: Data Types / http://www.w3.org/TR/2001/REC-xml schema-2-20010502/.

88. XSL Transformations (XSLT) Version 1.0 /http://www.w3.org/TR/1999/REC-xslt-199911161. Публикации

89. Корнеев Г.А., Шалыто A.A. Преобразование программ в систему взаимодействующих конечных автоматов / Труды Второй Всероссийской Научной конференции «Методы и средства обработки информации». М.: МГУ. 2005, с. 385-387.

90. Корнеев Г. А. Метод преобразования программ в систему взаимодействующих автоматов /Труды II межвузовской конференции молодых учёных. СПб.: СПбГУ ИТМО. 2005, с. 65-72.

91. КорнеевГ.А., ШалытоА.А. Реализация конечных автоматов с использованием объектно-ориентированного программирования /Труды X международной научно-методической конференции «Телематика-2003». СПб.: СПбГИТМО (ТУ). 2003, с. 377,378.

92. Корнеев Г.А., Казаков М.А., Шалыто А.А. Построение логики работы визуализаторов алгоритмов на основе автоматного подхода /Труды X международной научно-методической конференции «Телематика-2003». СПб.: СПбГИТМО (ТУ). 2003, с. 378,379.

93. КорнеевГ.А., ШамгуновН.Н., ШалытоА.А. Обход деревьев на основе автоматного подхода // Компьютерные инструменты в образовании. 2004. № 3, с. 32-37.

94. КорнеевГ.А., ШалытоА.А. Построение визуализаторов алгоритмов дискретной математики //Научно-технический вестник СПбГУ ИТМО. Выпуск 23. Высокие технологии в оптических и информационных системах. СПб.: СПбГУ ИТМО. 2005, с. 118-129.

95. Корнеев Г.А., Шалыто А.А. VIZI — язык описания логики визуализаторов алгоритмов //Научно-технический вестник СПбГУ ИТМО. Выпуск 23. Высокие технологии в оптических и информационных системах. СПб.: СПбГУ ИТМО. 2005, с. 130-138.