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

Актуальность проблемы. В настоящее время приборы и устройства становятся все сложнее. Для автоматизации их проектирования требуется знание алгоритмов на графах [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−90 114 в.

2002;2003 гг.- по теме «Разработка технологии объектно-ориентированного программирования с явным выделением состояний», выполняемой по гранту РФФИ № 05−07−90 011- по государственному контракту «Технология автоматного программирования: применение и инструментальные средства», выполняемому в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 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.

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