«Методы построения визуализаторов алгоритмов дискретной математики на основе автоматного подхода ...»

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

технологий, механики и оптики

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

Казаков Матвей Алексеевич

Методы построения

визуализаторов алгоритмов дискретной математики

на основе автоматного подхода

Специальность 05.13.06 – «Автоматизация и управление технологическими

процессами и производствами (образование) »

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель – доктор технических наук, профессор В.Г. Парфенов Санкт-Петербург

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

МАТЕМАТИКИ

1.1. ВИЗУАЛИЗАТОРЫ АЛГОРИТМОВ

1.2. ВИЗУАЛИЗАТОРЫ В ДИСТАНЦИОННОМ ОБУЧЕНИИ

1.3. ПОДХОДЫ К ПОСТРОЕНИЮ ВИЗУАЛИЗАТОРОВ

1.4. ТРАДИЦИОННЫЙ ЭВРИСТИЧЕСКИЙ ПОДХОД

1.5. ВЫБОР ТЕХНОЛОГИИ ДЛЯ ПОСТРОЕНИЯ ВИЗУАЛИЗАТОРА

1.6. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ

1.7. ЗАДАЧИ, РЕШАЕМЫЕ В ДИССЕРТАЦИОННОЙ РАБОТЕ

ВЫВОДЫ ПО ГЛАВЕ 1

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

ДИСКРЕТНОЙ МАТЕМАТИКИ

2.1. АВТОМАТНЫЙ ЭВРИСТИЧЕСКИЙ ПОДХОД

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

ПОДХОДА

2.2.1. Общая часть метода построения визуализаторов на основе автоматов Мили и Мура

2.2.2. Построение визуализаторов на основе автоматов Мили............ 2.2.3. Построение визуализаторов на основе автоматов Мура............. 2.2.4. Особенности разновидностей построения визуализаторов........

2.3. СРАВНЕНИЕ ТРАДИЦИОННОГО И АВТОМАТНЫХ (ЭВРИСТИЧЕСКОГО И

ФОРМАЛИЗОВАННОГО) МЕТОДОВ РАЗРАБОТКИ ВИЗУАЛИЗАТОРОВ АЛГОРИТМОВ

2.3.1. Алгоритм «пузырьковая сортировка»

2.3.2. Интерфейс визуализатора

2.3.3. Эвристический подход

2.3.4. Автоматный подход

2.3.5. Формализованное построение автомата по схеме алгоритма.... 2.3.6. Сравнение методов

ВЫВОДЫ ПО ГЛАВЕ 2

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

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

3.1. МЕТОД ПОСТРОЕНИЯ ВИЗУАЛИЗАТОРА

3.1.1. Изменения метода для обеспечения системы взаимодействующих автоматов

3.1.2. Формализация взаимодействия автоматов

3.1.3. Введение уровней визуализации

3.1.4. Внесение изменений в формирователь иллюстраций................. 3.1.5. Введение новых этапов в базовый метод

3.2. ПОСТРОЕНИЕ ВИЗУАЛИЗАТОРА АЛГОРИТМА «ЗАДАЧА О РЮКЗАКЕ» С

ИСПОЛЬЗОВАНИЕМ ВЗАИМОДЕЙСТВУЮЩИХ АВТОМАТОВ

3.3. СРАВНЕНИЕ С БАЗОВЫМ МЕТОДОМ

ВЫВОДЫ ПО ГЛАВЕ 3

ГЛАВА 4. АВТОМАТНЫЙ ПОДХОД К ОБЕСПЕЧЕНИЮ ПРОСТОЙ

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

МАТЕМАТИКИ

4.1. МЕТОД ОБЕСПЕЧЕНИЯ ПРОСТОЙ АНИМАЦИИ

4.1.1. Дополнительные этапы метода для обеспечения анимации..... 4.1.2. Формализация построения автомата визуализации.................. 4.1.3. Введение анимационных состояний в автомат визуализации.. 4.1.4. Построение автомата анимации

4.1.5. Обеспечение отображения анимации

4.1.6. Введение новых этапов в метод

4.2. ПОСТРОЕНИЕ ВИЗУАЛИЗАТОРА НА ПРИМЕРЕ АЛГОРИТМА ПИРАМИДАЛЬНОЙ

СОРТИРОВКИ

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

ДВОИЧНОГО ДЕРЕВА

ВЫВОДЫ ПО ГЛАВЕ 4

ГЛАВА 5. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ В УЧЕБНЫЙ ПРОЦЕСС

5.1. ПРИМЕНЕНИЕ ЭВРИСТИЧЕСКОГО АВТОМАТНОГО ПОДХОДА

5.2. ПРИМЕНЕНИЕ АВТОМАТНОГО ПОДХОДА

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

5.3. ИСПОЛЬЗОВАНИЕ В ИНТЕРНЕТ-ШКОЛЕ ПРОГРАММИРОВАНИЯ

5.4. ДАЛЬНЕЙШЕЕ РАЗВИТИЕ ПРЕДЛАГАЕМОГО ПОДХОДА

5.5. СРАВНЕНИЕ ТРУДОЗАТРАТ НА СОЗДАНИЕ ВИЗУАЛИЗАТОРОВ РАЗЛИЧНЫМИ

МЕТОДАМИ

ВЫВОДЫ ПО ГЛАВЕ 5

ЗАКЛЮЧЕНИЕ

СПИСОК ИСТОЧНИКОВ

ПУБЛИКАЦИИ АВТОРА

Статьи в журналахиз перечня ВАК

Другие статьи

Материалы конференций

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

ПРИЛОЖЕНИЕ. КУРСОВАЯ РАБОТА СТУДЕНТОВ 3 КУРСА КАФЕДРЫ

«КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИ» СПБГУ ИТМО А.В. СТЕПУКА,

В.А. ДОБРОВОЛЬСКОГО НА ТЕМУ «СОРТИРОВКА ПОДСЧЕТОМ» (2004)

ВВЕДЕНИЕ

Актуальность проблемы. С вводом Федеральных государственных образовательных стандартов (ФГОС) [1] усиливается роль самостоятельной работы студентов (СРС) [1], что требует разработки новых образовательных технологий для ее поддержки. Кроме того ФГОС содержат требование к обеспечению не менее 10–20% аудиторных занятий студентов в интерактивной форме. Это обстоятельство ставит новые задачи по разработке интерактивных средств обучения, призванных индивидуализировать образовательный процесс массовой подготовки выпускников вузов. При уровневой подготовке выпускников вузов информационной направленности важное место занимают методы и алгоритмы дискретной математики, изучение которых создает базис (базовые знания, умения и навыки) для формирования различных универсальных (общекультурных) и профессиональных навыков выпускников.

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

Многие годы эти алгоритмы изучались по книгам, в которых практически невозможно было отразить динамику [2 – 6]. В восьмидесятых годах двадцатого века в нескольких американских университетах [7], а в конце девяностых годов также и в Санкт-Петербургском государственном университете информационных технологий, механики и оптики (СПбГУ ИТМО) [8, 9, 78, 80] и Санкт-Петербургском государственном университете (СПбГУ) [10, 11] пришли к выводу, что алгоритмы следует изучать не только в статике в виде диаграмм, но и в динамике (в процессе работы). Для этого необходимо строить специальные программы, которые должны представлять алгоритмы в удобной для обучающихся форме: наряду с текстовыми комментариями должны отображаться динамические иллюстрации. Программы для реализации динамических иллюстраций, были названы визуализаторами. В течение последних 10 лет проблемами построения визуализаторов занимались многие специалисты в СПбГУ ИТМО, [12] и СПбГУ [10, 11, 13], в том числе автор настоящей диссертации [76, 78]. Однако все эти работы обладали существенным недостатком: визуализаторы для каждого алгоритма индивидуально и отсутствовали какие-либо методы их формализованной реализации.

С начала девяностых годов в России (в частности, в СПбГУ ИТМО) разрабатывался метод автоматного программирования (программирование с явным выделением состояний [44]), суть которого состоит в применении конечных автоматов в программировании. В 2001 г. автором настоящей работы было высказано предположение, что формализованные методы построения визуализаторов могут базироваться на автоматном подходе. Это предположение оказалось верным, что и будет показано в настоящей диссертации.

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

СПбГУ ИТМО. На основе этого подхода были созданы десятки визуализаторов автоматизированы, что потребовало разработки дополнительных технологий, которые учитывают особенности процесса автоматизации реализации визуализаторов. Эта работа выполнялась совместно с Г.А. Корнеевым [74], который свою диссертационную работу посвятил особенностям автоматизации построения визуализаторов. Настоящая работа описывает методы, которые, вопервых, весьма эффективны при их использовании вручную, а во-вторых, легли в основу автоматизации построения визуализаторов, описанной в диссертации Г.А. Корнеева. Опыт преподавания в Интернет-школе программирования, а также студентам первых и вторых курсов СПбГУ ИТМО показывает, что для хорошего понимания алгоритмов дискретной математики необходимо как ручное, так и автоматизированное построение визуализаторов. Ручное построение позволяет глубже как понять природу самих алгоритмов, так и природу процессов визуализации алгоритмов.

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

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

Конечные автоматы известны с пятидесятых годов прошлого века. Они в основном применялись для компиляторов и протоколов. Наиболее близкой к теме диссертации является применение автоматов для реализации пользовательского интерфейса. В 2007 г. ведущий сотрудник компании IBM Э. Принг предложил использовать автоматы для реализации виджетов [15 – 17], в частности, для реализации всплывающих окон. Однако в силу того, что методы формализованного перехода в его работах отсутствовали, были допущены ошибки при построении конечных программ, что отмечено в работе [18]. В этой же работе было отмечено, что методы, описываемые в настоящей диссертации, были ранее рассмотрены автором диссертации в работе [69].

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

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

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

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

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

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

1. Подход к реализации визуализаторов алгоритмов дискретной математики на основе конечных автоматов.

2. Метод построения визуализаторов на основе конечных автоматов.

взаимодействующих автоматов.

4. Метод для обеспечения простой анимации визуализаторов на основе автоматного подхода.

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

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

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

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

2. В учебном процессе на кафедре «Компьютерные технологии»

СПбГУ ИТМО при чтении лекций по курсу «Теория автоматов в программировании».

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

диссертационной работы докладывались на научно-методических конференциях: «Телематика-1999» (СПб.), «Дистанционное обучение.

Проблемы и перспективы взаимодействия вузов Санкт-Петербурга с регионами России» (СПб., 1999), «Телематика-2000», «Телематика-2001», «ТелематикаТелематика-2003» (СПб.), «Конференция молодых ученых СПбГУ ИТМО» (СПб., 2004), «Телематика-2004» (СПб.), «Телематика-2005» (СПб.), «Профессиональное образование, наука, инновации в XXI веке» (СПб., 2007), «Научное программное обеспечение в образовании и научных исследованиях»

(СПб., 2008).

Внедрение результатов работы. Результаты диссертации использованы при выполнении следующих научно-исследовательских работ: «Разработка технологии программного обеспечения систем управления на основе автоматного подхода» – гос. контракт № 10038 по заказу Министерства образования РФ в 2001 – 2005 гг. (http://is.ifmo.ru/science/1/), и «Разработка технологии автоматного программирования», выполненной по гранту Российского фонда фундаментальных исследований № 02-07-90114 в 2002 – 2003 гг. (http://is.ifmo.ru/science/2/).

Публикации. По теме диссертации опубликовано 28 научных работ, из них 21 печатная работа, в том числе 11 статей, из которых пять статей опубликованы в журналах из перечня ВАК, 7 отчетов по научноисследовательской работе.

Награды. В 2008 году автор стал лауреатом премии Правительства Российской Федерации в области образования в составе авторского коллектива научно-практической разработки «Инновационная система поиска и подготовки высококвалифицированных специалистов в области производства программного обеспечения на основе проектного и соревновательного подходов». В рамках этого проекта автор работал над разработкой методов построения визуализаторов и созданием Интернет-школы программирования. В 2008 году эта разработка стала лауреатом премии Правительства Российской Федерации в области образования (http://www.rg.ru/2009/01/16/premiiobrazovanie-dok.html).

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

Работа иллюстрирована 96 рисунками и 7 таблицами.

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

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

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

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

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

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

МАТЕМАТИКИ

образовательный инструмент, как визуализаторы алгоритмов [9].

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

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

В разд. 1.1 приведен общий обзор визуализаторов алгоритмов, описаны общие свойства визуализаторов. При этом в разд. 1.2 описывается роль визуализаторов в образовательном процессе и, в частности, в дистанционном обучении. В разд. 1.3 проводится обзор существующих систем визуализации и подходов к построению визуализаторов. Разд. 1.4 акцентирует внимание на предварительных исследованиях автора в области традиционного эвристического построения визуализаторов. Разд. 1.5 посвящен разъяснению технологической составляющей построения визуализаторов. В разд. 1. приведен обзор автоматного программирования и указаны достоинства автоматного программирования при построении визуализаторов. Разд. 1. завершает первую главу формулировкой задач решаемых в рамках данной диссертационной работы.

Дискретная математика – наука, изучающая область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. [19]. Одним из ключевых разделов дискретной математики является теория алгоритмов. Эта теория рассматривает общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления [20].

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

Автор настоящей диссертации занимается проблемами обучения дискретной математике с 1997 г. [75 – 78].

Проблема обучения алгоритмам дискретной математики существует с начала их использования в вычислительной технике. Сначала алгоритмы изображались в текстовом виде, потом – в виде схем алгоритма (блок-схем), а затем в виде псевдокода. Современные книги описывают алгоритмы в виде набора примеров входных и выходных данных, а также исходного кода алгоритма, реализованного на одном из императивных языков программирования, таких как C/С++, Pascal или Java [21]. Императивным программированием называется такое программирование, в котором программа состоит из набора инструкций, выполняемых в определенной последовательности [22].

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

1. Статическое восприятие текста с динамической прокруткой в голове.

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

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

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

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

Дальнейшие исследования в области преподавания дискретной математики привели к возникновению в середине восьмидесятых годов [7, 25] нового подхода к преподаванию – появились визуализаторы алгоритмов дискретной математики.

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

Перечислим отличительные характеристики визуализаторов.

1. Простота использования, определяемая понятностью интерфейса.

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

2. Четкость и простота представления визуализируемого процесса.

3. Компактность визуализаторов. Это при необходимости упрощает передачу визуализаторов в сети Интернет, что особенно важно при дистанционном обучении.

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

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

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

1. Пошаговое выполнение алгоритма.

2. Просмотр действия алгоритма при разных наборах входных данных, в том числе и введенных пользователем.

3. Просмотр действия алгоритма в динамике.

4. Перезапуск алгоритма на текущем наборе входных данных.

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

В задачи визуализатора алгоритма входит:

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

2. Отображение внутренних служебных переменных.

3. Отображение процесса воздействия алгоритма на входные данные и внутренние переменные:

b. Копирование и перемещение данных.

4. Комментарии к каждому действию алгоритма.

5. Отображение работы алгоритма по шагам.

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

1.2. Визуализаторы в дистанционном обучении Одной из важных предпосылок к началу работы над методами создания визуализаторов является опыт работы над проектом дистанционного обучения [23, 24] «Интернет-школа программирования» [26, 76, 77]. Этот проект разрабатывался совместно с сотрудниками и преподавателями кафедры «Компьютерные технологии» СПбГУ ИТМО.

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

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

Систематический подход преподавателя к собственно процессу ведения занятий определяют несколько факторов:

нематематической специализации, студенты-математики;

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

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

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

Приведем простой контрпример: лекция по дифференциальному исчислению, которая транслируется из радиостудии.

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

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

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

3. Технология «книга с картинками». Используются компьютер и демонстрационный экран; заранее подготовлен набор файловиллюстраций, например, в JPG- или GIF-формате; те же изображения могут быть встроены в HTML-файлы.

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

воспроизводимости лекции; для слушателей – доступность лекционных материалов не только во время занятия.

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

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

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

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

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

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

включает статический текст, два–три визуализатора, поясняющих рассматриваемые в уроке алгоритмы, а также набор задач, в том числе, предлагаемых для дистанционного тестирования [75, 76].

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

1.3. Подходы к построению визуализаторов Как отмечено выше, одним из методических приемов [8, 26, 78, 80] при обучении программированию и дискретной математике является разработка визуализаторов алгоритмов [2, 3].

Анализ литературы [27, 28], а также реализации визуализаторов [29 – 32] показал, что технологии разработки визуализаторов рассматриваемого класса обычно являются эвристическими.

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

Другими словами, формализованный метод разработки визуализаторов рассматриваемого типа отсутствовал, и основные успехи в этой области были педагогическими [8, 33, 78].

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

Первый зафиксированный визуализатор, демонстрирующий работу связанных списков, появился в далеком 1966 г. в Bell Telephone Laboratories [34, 35]. Лишь в конце восьмидесятых — начале девяностых были созданы первые системы визуализации: BALSA (Brown ALgorithm Simulator and Animator) [25] и TANGO (Transition-based Animation GeneratiOn) [36]. В настоящее время существует большое число систем визуализации (например, Animal [37], Leonardo [38], Zeus [39], CATAI [40], Mocha [41]). Однако, поскольку системы визуализации по своей сути реализуют пользовательский интерфейс и различные визуальные эффекты, но не предоставляют автоматического или формализованного построения визуализаторов алгоритмов, то их использование не дает преимуществ по сравнению с эвристическим подходом. Следует отметить, что в настоящее время существует одна система визуализации, реализующая возможность формализованного построения визуализаторов по алгоритмам, разработанная Г.А. Корнеевым на кафедре «Компьютерные технологии» СПбГУ ИТМО [42, 43]. Данная система разрабатывалась Г.А. Корнеевым на основе идей автора изложенных в настоящей диссертации, а также совместной работы над разработкой методов формализованного перевода алгоритмов в визуализаторы [74]. Как уже отмечалось выше, работа Г.А. Корнеева была продолжена в области автоматизации. В то время как автор настоящей работы работал в области ручного построения визуализаторов, что является хоть и более трудоемким занятием, но гораздо более эффективным для обучения теории алгоритмов.

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

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

• Автоматный эвристический. Автоматный подход основан на описании поведения визуализатора алгоритма на основе автоматов.

• Автоматный формализованный. Визуализатор с использованием автоматов строится на основе алгоритма формализовано.

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

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

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

1. Формулировка алгоритма в словесно-математической форме.

2. Принятие решения о визуализируемых элементах и процессе отображения визуализации.

3. Построение программы, реализующей визуализатор.

Данным способом строились визуализаторы с 1997 по 2001 гг. При этом в 1999 – 2001 гг. автором данной работы были организованы курсовые работы по построению визуализаторов для студентов первого курса. Опыт проведения этих работ показал, что из-за отсутствия метода разработки визуализаторов алгоритмов, создание каждого визуализатора требовало достаточно большого времени от преподавателя – от одного до двух рабочих дней (8 – 16 часов).

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

Как следует из приведенных данных, эвристические подходы построения визуализаторов делятся условно на следующие классы.

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

Таблица 1. Курсовые работы, выполненные под руководством автора 2. Добровольский В. Перебор перестановок Java, эвристика 4. Михалев Е. Генератор перестановок Java, от предыдущей 5. Прокушкин И. Алгоритм Кнута-Морриса- Java, стек состояний 11. Бородин Т. Алгоритм Кнута-Морриса- Delphi, стек состояний 12. Наумов Л. Алгоритмы поиска подстрок Delphi, стек состояний • «От предыдущей точки визуализации к следующей». При таком подходе визуализатор разбивается на точки визуализации, которые отображаются при шагах алгоритма. При этом явно выделен метод перехода из предыдущей точки к следующей. Такой способ работает только в повторяющихся итеративных алгоритмах, где каждый шаг повторяет предыдущий – логика алгоритма не зависит от текущего • Стек состояний. Этот способ является самым технологичным из эвристических, поскольку является универсальным. Суть способа состоит в том, что перед началом визуализации алгоритм запускается на входных данных и по ходу выполнения алгоритма в памяти запоминаются контрольные точки алгоритма. Эти точки содержат значения всех переменных, над которыми алгоритм производит повторяться на любом алгоритме.

Анализ всех перечисленных выше эвристических методов построения визуализаторов выявляет следующие недостатки.

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

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

1.5. Выбор технологии для построения визуализатора Визуализатор алгоритма – это программа (приложение), написанная в рамках определенной технологии. Как отмечалось выше, при использовании визуализаторов на лекциях, а также при заочном обучении возможно использование любых языков программирования и, соответственно, технологий. Обсуждение достоинств и недостатков различных подходов к построению приложений выходят за рамки данной работы. Отметим лишь, что в аудиторное преподавание позволяет писать на любом языке. При построении приложений, пригодных для использования в дистанционном обучении в Интернет-школе программирования требуется использование интернеториентированных технологий и языков.

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

1. Наличие готовых библиотек по построению пользовательского 2. Возможность встраивать приложения в Web-страницы.

3. Кросс-платформенность.

4. Возможность работы без использования браузера.

5. Широкое распространение и поддержка.

Существуют различные технологии для реализации приложений в Интернет. Примерами могут служить Adobe Flash [45], Microsoft Silverlight [46], JavaScript [47]. Несомненными достоинствами этих технологий является их широкое распространение и упрощенное написание Интернет-приложений. Их недостатком является их узкая область применения – они работают только в рамках браузеров. Несмотря на недавний выход в свет технологии Adobe AIR [48], позволяющей запускать Flash-приложения без браузеров, сама технология существенно уступает по гибкости и распространенности технологии Java [21]. Технология Java Applets [49], являющаяся частью технологической платформы Java, предоставляет максимальные преимущества по сравнению с другими языками и технологиями.

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

Таблица 2. Результаты сравнения платформ для разработки визуализаторов Из результатов сравнения следует, что только платформа Java совместно преимущества. Опишем эти преимущества более подробно.

• Интернет-ориентрированная технология – позволяет встраивать приложения в Web-сайты;

• Java Applets – это часть технологии Java. Это позволяет писать универсальные приложения для Web и одновременно создавать • Java является одной из самых распространенных технологий, поэтому использование этой технологии учащимися дает опыт использования профессиональных средств разработки, которые рассматриваемым в данной работе, целесообразно использовать процедурный язык. Первые визуализаторы писались с применением пакета Delphi, основанного на языке Object Pascal, который, однако, использовался лишь для пользовательского интерфейса (VCL). При этом вся логика требовала лишь процедурного подхода.

Автоматический подход к построению визуализаторов, изложенный в диссертации Г.А. Корнеева [43], требует использования объектноориентированного программирования. Необходимость этого обусловлена методом реализации рекурсивных алгоритмов на основе автоматного программирования [50]. Суть метода заключается в формировании стека автоматов, реализующих рекурсивные функции.

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

В 1991 г. в России появилось автоматное программирование [44]. До появления автоматного программирования автоматы использовались в программировании, начиная с шестидесятых годов от случая к случаю. Только при построении компиляторов и протоколов они применялись систематически [51]. Автоматное программирование предлагает использовать автоматы гораздо шире: парадигма автоматного программирования предполагает использование автоматов для моделирования и реализации произвольной логики поведения сложных программ.

Автоматное программирование (называемое также программированием с явным выделением состояний) позволяет решать класс задач, связанный с системами управления со сложным поведением. Особенностью автоматов целесообразно использовать в задачах управления, в особенности технологическими процессами, например, в образовании. В частности, использование автоматного программирования удобно применять совместно с паттерном Модель – Вид – Контроллер [52, 53] при реализации контроллера.

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

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

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

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

2. Методы должны быть универсальными и обеспечивать возможность требованиям к визуализаторам.

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

1. Отображение входных и выходных данных в наглядной форме.

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

3. Отображение процесса воздействия алгоритма на данные.

4. Комментарии к визуализируемому действию алгоритма.

5. Отображение работы алгоритма по шагам.

6. Отображение работы алгоритма на различных уровнях.

7. Отображение простой анимации (плавных динамически-меняющихся Для построения указанных выше методов построения визуализаторов алгоритмов требуется решить следующие задачи:

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

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

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

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

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

Исследования автора в этой области приведены в статье [74].

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

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

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

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

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

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

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

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

АЛГОРИТМОВ ДИСКРЕТНОЙ МАТЕМАТИКИ

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

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

Ниже приводится основная идея, положенная в основу настоящей диссертации.

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

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

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

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

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

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

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

Визуализатор «по-крупному» предлагается строить следующим образом:

• по алгоритму строится автомат логики визуализатора (Контроллер – • выбираются визуализируемые переменные (Модель – Model);

• проектируется формирователь иллюстраций и комментариев, который преобразует номер состояния и соответствующие значения визуализируемых переменных в «картинку» и поясняющий текст (Представление – View).

Такая конструкция визуализатора соответствует одному из основных паттернов проектирования объектно-ориентированных программ, нацеленных на взаимодействие с пользователем персонального компьютера, который Особенностью этой технологии является четкое разделение логики поведения программы от ее визуального представления. В применении к визуализаторам алгоритмов использование паттерна MVC позволяет создавать вариации визуализаторов с единой логикой поведения, но различными технологиями реализации пользовательского интерфейса. Так, например, в одном случае интерфейс можно сделать с использованием технологии Swing [54] (именно этот способ рассматривается как основной в настоящей работе), в другом случае – Java Applets [49], а в третьем – с использованием технологии AJAX [55]. Наличие единой модели и логики в этом случае будут гарантировать единообразие в поведении визуализатора в разных пользовательских окружениях.

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

В разд. 2.2 рассматриваются две модификации базового метода построения визуализаторов на основе автоматов Мили и автоматов Мура, происходит сравнение модификаций.

В разд. 2.3 приводится сравнение эвристического, автоматного эвристического подходов с формализованным методом построения визуализаторов алгоритмов.

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

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

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

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

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

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

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

1. Постановка и решение задачи в словесной форме.

2. Автоматная реализация алгоритма решения задачи.

3. Реализация построителя иллюстраций.

4. Реализация визуализатора.

Рассмотрим применение этого подхода к простой задаче из теории алгоритмов – «Решето Эратосфена» [56]. Этот классический алгоритм, хоть и не является широко распространенным в силу своей малой эффективности, но является достаточно полезным при изучении дискретной математики.

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа который приписывают древнегреческому математику Эратосфену [57].

Приведем словесное описание усовершенствованного алгоритма решения этой задачи.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, необходимо выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n.

2. Пусть переменная p изначально равна двум — первому простому 3. Вычеркнуть из списка все числа от p2 до n, делящиеся на p.

4. Найти первое, не вычеркнутое число, большее, чем p, и присвоить значению переменной p это число.

5. Повторять шаги 3 и 4 до тех пор, пока p2 не станет больше, чем n.

6. Все не вычеркнутые числа в списке — простые числа.

Приведенный алгоритм можно реализовать при помощи автомата, приведенного на рис. 1. При этом предполагается, что a[i] – булево значение, обозначающее, что данное число является простым.

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

Рис. 1. Смешанный автомат алгоритма «Решето Эратосфена»

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

1. Начальное состояние – отображается в состоянии 1.

2. Поиск уже известных чисел (шаг 2 и 4 словесного алгоритма) – отображается в состоянии 2.

3. Вычеркивание непростых чисел – в состоянии 3.

4. Отображение финального результата – в состоянии 4.

несостоятельность эвристического подхода. Отметим недостатки графа переходов, представленного на рис. 1.

1. Поскольку приоритет переходов в состоянии 2 расположен в соответствии с формулировкой задачи, то визуализатор будет проходить по лишним числам. Например, в случае, если n = 50, то последнее рассмотренное число должно быть 8, в то время как визуализатор покажет 11 (первое простое число большее n ). При формализованном методе построения визуализатора, рассмотренном ниже, этот недостаток устраняется путем отладки императивного алгоритма, написанного на языке программирования. Безусловно, отладку можно производить и на автоматах, но эта задача требует более высокого уровня подготовки обучающихся.

2. В состоянии 3, как можно отметить, значение служебной переменной j изменяется сразу же после изменения флага a[j]. Таким образом, при отображении иллюстраций требуется вводить специальную логику для анализа ситуации в состоянии 3.

С учетом указанных недостатков, автомат (рис. 1) предлагается трансформировать в другой автомат. Этот автомат не является эквивалентным в силу того, что он проходит меньший интервал значений i, но является более правильным и простым с точки зрения визуализации, поскольку устраняет указанные недостатки (рис. 2).

Рис. 2. Усовершенствованный автомат алгоритма «Решето Эратосфена»

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

Состояние 1 показывает исходный массив чисел (рис. 3).

В состоянии 2 осуществляется поиск следующего простого числа (рис. 4).

Рис. 4. Состояние 2 – поиск следующего простого числа В состоянии 3 осуществляется вычеркивание непростых чисел (рис. 5).

Рис. 5. Состояние 3 – вычеркивание непростых чисел Состояние 4 является конечным и отображает все не вычеркнутые числа как простые (рис. 6).

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

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

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

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

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

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

Существует две модификации метода разработки визуализаторов алгоритмов ручным способом. Оба метода основаны на использовании программирования с явным выделением состояний и применении SWITCHтехнологии [59].

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

Вторая модификация метода основана на реализации поведения визуализатора с помощью автомата Мура. При использовании этой модификации действия совершаются в управляющих состояниях.

Приведем этапы метода формализованного построения визуализаторов алгоритмов, который назовем базовым:

1. Постановка задачи.

2. Решение задачи (в словесно-математической форме).

3. Выбор визуализируемых переменных.

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

5. Реализация алгоритма решения задачи.

6. Реализация алгоритма на выбранном языке программирования.

На этом шаге производится реализация алгоритма, его отладка и проверка работоспособности.

7. Построение схемы алгоритма по программе.

8. Преобразование схемы алгоритма в граф переходов автомата 10. Выбор интерфейса визуализатора.

11. Сопоставление иллюстраций и комментариев с состояниями 12. Выбор архитектуры программы визуализатора.

13. Программная реализация визуализатора.

Известно, что обычно создание программы разбивается на пять стадий:

разработка требований, анализ, проектирование, реализация и тестирование. В данном случае к разработке требований относятся первые три пункта технологии. Анализ – пункты 4 и 5. К проектированию относятся пункты с 6-го по 11-й. В отличие от процедурного подхода для объектноориентированного подхода, выбор архитектуры программы относится не к стадии проектирования, а к стадии реализации, так как все предыдущие пункты метода не зависят от реализации. Естественно, что к стадии реализации относится и последний пункт метода.

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

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

Ниже приведены два варианта реализации «дискретной целочисленной задачи о рюкзаке» – на основе автоматов Мили и автоматов Мура.

2.2.1. Общая часть метода построения визуализаторов на основе Отметим, что этапы метода с 1-го по 7-ой не зависят от выбора разновидности метода, в то время как этапы с 8-го по 13-й зависят от того, какие используются автоматы – автоматы Мили или Мура. Поэтому первые семь этапов сделаем общими для двух модификаций.

Рассмотрим словесную постановку задачи, которая в литературе носит название «дискретная целочисленная задача о рюкзаке» [1, 4]. Приведем одну из формулировок этой задачи.

Имеется набор из K неделимых предметов, для каждого из которых известна масса Mi (в кг), являющаяся натуральным числом. Задача состоит в том, чтобы определить, существует ли хотя бы один набор предметов, размещаемый в рюкзаке, суммарная масса которых равна N. Если такой набор существует, то требуется определить его состав.

Приведем словесную формулировку решения этой задачи.

1. Построение функции, представляющей оптимальное решение.

Построим вектор M (1..K), каждый элемент Mi которого соответствует массе i-го предмета.

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

значения для подзадач.

Определим начальные значения функции T:

• T (0, j) = 0 при j 1 {без предметов нельзя набрать массу j 1};

• T (i, 0) = 1 при i 0 {всегда можно набрать нулевую массу}.

Определим возможные значения функции T при других значениях аргументов.

Существуют две возможности при выборе предметов: включать предмет с номером i в набор или не включать. Это в математической форме может быть записано следующим образом:

• если предмет с номером i не включается в набор, то решение задачи с i предметами сводится к решению подзадачи с (i – 1)-им предметом.

• если предмет с номером i включается в набор, то это уменьшает суммарную массу для i – 1 первых предметов на величину Mi. При этом T (i, j) = T (i – 1, j – Mi). Эта ситуация возможна только тогда, Для получения решения необходимо выбрать большее из значений рассматриваемой функции. Поэтому рекуррентные соотношения при i 1 и j 1 имеют вид:

После построения таблицы T проверяется элемент T(K, N). Если этот элемент равен единице, то искомый набор может быть получен.

• Эти предметы имеют следующие массы: M1 = 4; M2 = 5; M3 = 3;

• Суммарная масса предметов, которые должны быть размещены в 4. Вычисление значений функции T (i, j) (прямой ход алгоритма).

Используя приведенные выше рекуррентные соотношения, построим таблицу значений рассматриваемой функции (табл. 3).

Т (i, j) Из таблицы следует, что Т (5, 16) = 1, и поэтому существует хотя бы один набор предметов, удовлетворяющий постановке задачи.

5. Определение набора предметов (обратный ход алгоритма).

Во время обратного хода алгоритма происходит поиск искомого набора, начиная с ячейки T (K, N). При этом переход с ячейки T (i, j) в следующую ячейку происходит следующим образом:

• Если значение T (i – 1, j) равно нулю, то не существует набора среди элементов с первого по i – 1-й, суммарный вес которых равен j.

Поэтому предмет с номером i входит в искомый набор, а следующей рассматриваемой ячейкой становится T (i – 1, j).

• В случае, когда значение T (i – 1, j) равно 1, то следующей рассматриваемой ячейкой становится T (i – 1, j).

• Обратный ход алгоритма происходит до тех пор, пока значение i не рассматриваемом примере. Рассмотрим элементы Т (5, 16) и Т (4, 16) таблицы.

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

Теперь рассмотрим элементы Т (4, 16) и Т (3, 16). Их значения не равны, и поэтому набор из трех предметов не обеспечивает решение задачи.

Следовательно, четвертый предмет должен быть включен в набор. Поэтому «остаток» массы, размещаемой в рюкзаке, который должен быть набран из оставшихся предметов, равен: 16 – М4 = 16 – 7 = 9.

Для элементов Т(3, 9) и Т(2, 9) значения равны – третий предмет в набор не включается.

Для элементов Т(2, 9) и Т(1, 9) значения не равны – второй предмет должен быть включен в набор. При этом остаток равен: 9 – М2 = 9 – 5 = 4.

И, наконец, рассмотрим элементы Т(1, 4) и Т(0, 4). Их значения не равны – первый предмет должен быть включен в набор, а «остаток» массы для других предметов равен нулю.

Таким образом, одно из решений задачи найдено – в набор включены первый, второй и четвертый предметы.

Перечислим переменные, которые содержат значения, необходимые для визуализации:

• i – номер предмета;

• j – сумма весов предметов;

• T[][] – значения функции T;

• positions – номера искомых предметов.

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

• показать таблицу, заполненную начальными значениями;

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

Приведем алгоритм решения задачи на псевдокоде [2]:

Перепишем программу c псевдокода на язык Java (листинг 1).

Текст программы, реализующей решение «задачи о рюкзаке»

Листинг 1.

2 * @param N суммарный вес предметов в рюкзаке 3 * @param M массив весов предметов 4 * @return список номеров предметов, сумма весов которых 5 * равна N, либо null, если это невозможно 7 private static Integer[] solve(int N, int[] M) { 8 // Переменные циклов 10 // Число предметов 11 int K = M.length;

12 // Массив T 13 int[][] T = new int[K + 1][N + 1];

14 // Результирующие номера 15 Collection positions = new ArrayList();

16 // Результат работы true, если суммарный вес можно получить 17 boolean result = false;

19 // Определение начальных значений функции T При этом наличие кнопок пропуска деталей определенного уровня и их число не является строгим и зависит от конкретного визуализатора. Так в примере, рассматриваемом далее в этой главе, визуализатор имеет три уровня детализации, в то время как другие визуализаторы могут иметь другое число уровней.

3.1.4. Внесение изменений в формирователь иллюстраций В терминах приведенных выше обозначений формирователь иллюстраций должен реализовывать функцию FS(S) = FS(s1, s2, …,sN). В базовом методе, приведенном в главе 2, формирователь иллюстраций является частным случаем формирователя, используемого в рассматриваемом методе. В то время как в методе, изложенном в главе 2, формирователь иллюстраций реализовывается посредством единственного оператора switch, в настоящем методе реализация формирования статических иллюстраций достигается посредством системы вложенных операторов switch.

статическую иллюстрацию для каждого состояния системы автоматов. Однако, поскольку до построения формирователя иллюстраций строится список интересных состояний {Vj}j=1={{v1,v2,…,vN}j}j=1, то при формировании операторов switch необходимо построить иллюстрации лишь для интересных состояний. Таким образом, формирователь иллюстраций реализуется следующим образом (листинг 5).

Формирование иллюстраций в системе взаимодействующих автоматов Листинг 5.

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

3.1.5. Введение новых этапов в базовый метод После приведенных изменений этапы базового метода преобразуются следующим образом:

1. Постановка задачи.

2. Решение задачи (в словесно-математической форме).

3. Выбор визуализируемых переменных.

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

5. Реализация алгоритма решения задачи.

6. Реализация алгоритма на выбранном языке программирования.

На этом шаге производится реализация алгоритма, его отладка и проверка работоспособности.

7. Преобразование программы с целью выделения крупных шагов 8. Построение схем алгоритма по программе: одна схема для главного алгоритма и по одной схеме для каждой вложенной 9. Преобразование схем алгоритма в графы переходов системы 10. Формирование набора невизуализируемых состояний для 11. Назначение уровня детализации каждому из автоматов.

12. Выбор интерфейса визуализатора.

13. Сопоставление иллюстраций и комментариев с состояниями 14. Выбор архитектуры программы визуализатора.

15. Программная реализация визуализатора.

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

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

7. Преобразование программы с целью выделения крупных шагов в Как отмечено выше, шаги с первого по шестой не изменяются, поэтому начнем с программы, реализующей алгоритм (листинг 1). После выделения основных этапов алгоритма в процедуры получаем следующий код на языке Java (листинг 6).

Преобразованная программа с выделенными процедурами Листинг 6.

1 /** 2 * @param N суммарный вес предметов в рюкзаке 3 * @param M массив весов предметов 4 * @return список номеров предметов, сумма весов которых равна N, 5 * либо null, если это невозможно.

7 private static Integer[] solve(int N, int[] M) { 8 // Число предметов 9 int K = M.length;

10 // Массив T 11 int[][] T = new int[K + 1][N + 1];

12 // Результирующие номера 13 Collection positions = new ArrayList();

14 // Результат работы true, если суммарный вес можно получить 15 boolean result;

17 // Определение начальных значений функции T 18 firstRow(T);

19 firstColumn(T);

21 // Построение таблицы значений функции T 22 fillTable(M, T);

24 // Определение набора предметов 25 if (T[K][N] == 1) { 26 // Решение существует 27 searchResult(N, M, T, positions);

28 // Решение найдено 29 result = true;

30 } else { 31 result = false;

34 // Если решение найдено, то оно возвращается, иначе возвращается null 35 return (Integer[])(result ? positions.toArray(new Integer[0]) : null);

38 private static void firstRow(int[][] T) { 39 for (int j = 1; j < T[0].length; j++) { 44 private static void firstColumn(int[][] T) { 45 for (int i = 0; i < T.length; i++) { 50 private static void fillTable(int[] M, int[][] T) { 51 for (int i = 1; i < T.length; i++) { 52 for (int j = 1; j < T[i].length; j++) { 54 T[i][j] = Math.max(T[i - 1][j], T[i - 1][j - M[i - 1]]);

62 private static void searchResult(int N, int[] M, int[][] T, 65 for (int i = T.length - 1; i >= 1; i--) { 66 if (T[i][sum] != T[i - 1][sum]) { 67 positions.add(i);

Схемы алгоритма, соответствующие тексту программы приведены на рис. 38 – 43.

Рис. 39. Схема главного алгоритма Рис. 40. Схема заполнения первого столбца Рис. 41. Схема алгоритма заполнения строки i 9. Преобразование схем алгоритма в графы переходов системы автоматов В соответствии с методом, изложенным в работе [58], определим состояния, которые будут иметь автоматы Мура, соответствующие схемам алгоритма. Для этого присвоим номера последовательностям операторных вершин (последовательность может состоять и из одной вершины).

Рис. 44. Автомат aFR, реализующий заполнение первой строки Рис. 45. Автомат aFC, реализующий заполнение первого столбца Рис. 46. Автомат aTR, реализующий заполнение одной строки таблицы Рис. 47. Автомат aR, реализующий поиск результата Отметим, что если автоматы на рис. 44-47 получены непосредственно с помощью метода, изложенного в работе [58], то остальные автоматы требуют использовании этого преобразования, парные состояния, соответствующие вызову вложенной процедуры, будут иметь состояния S и S'.

• «>>» – сделать шаг алгоритма, пропуская все переходы первого • «>>>» – сделать шаг алгоритма, пропуская все переходы первого и второго уровня детализации;

• «Заново» – начать алгоритм заново;

• «Авто» – перейти в автоматический режим;

• «» – изменение паузы между автоматическими шагами Среднюю часть визуализатора занимает область комментариев, в которой на каждом шаге отображается номер состояния и опис выполняемого в этом состоянии.

Визуализатор в исходном состоянии, которое соответствует начальному состоянию автомата, представлен на рис. 51.

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

Состояние 0 главного автомата aM (рис. 49) представлено на рис. 51.

В состояниях 1 и 1' главного автомата aM работает вложенный автомат aFR (рис. 44), который имеет только одно интересное состояние 2. В этом состоянии отображается заполнение нулями первой строки таблицы T (рис. 52).

Рис. 52. Состояние 2 автомата aFR при состоянии 1 или 1' автомата aM В состояниях 2 и 2' главного автомата aM работает вложенный автомат aFC (рис. 45). В этом автомате также присутствует только одно интересное состояние 2, в котором отображается заполнение единицами первого столбца таблицы T (рис. 53).

Рис. 53. Состояние 2 автомата aFC при состоянии 2 или 2' автомата aM В состояниях 3 и 3' главного автомата aM (рис. 49) работает вложенный автомат aT (рис. 48), отвечающий за заполнение таблицы T значениями. Как отмечено выше, автомат aT не имеет интересных состояний. Однако в состояниях 2 и 2' автомата aT работает вложенный автомат aTR (рис. 46), который имеет интересные состояния. Наличие интересных состояний в автомате aTR делает состояния 2 и 2 автомата aT также визуализируемыми, что в свою очередь делает визуализируемыми состояния 3 и 3' главного автомата aM.

Автомат aTR имеет два интересных состояния. В состоянии 2 (рис. 54) отображается перенос значения из предыдущей строки, в то время как в состоянии 3 (рис. 55) отображается появление альтернативного варианта Тем самым значение в текущей ячейке заполняется большим из альтернативн значений.

Рис. 54. Состояние 2 автомата aTR при состоянии 2 или 2' автомата aT и состоянии Рис. 55. Состояние 3 автомата aTR при состоянии 2 или 2' автомата aT и состоянии В состояниях 4 и 4' главного автомата aM работает вложенный автомат aR (рис. 47), реализующий поиск результирующего набора. Как отмечалось выше, у этого автомата интересными являются пять состояний. Рассмотрим каждое из интересных состояний в отдельности.

автомата aR отображает факт существования решения (рис. 56).

Рис. 56. Состояние 0 автомата aR при состоянии 4 или 4' автомата aM Состояния 1 и 4 автомата aR отображают выбор альтернативных вариантов при обратном проходе по таблице T. При этом состояние отображает эту альтернативу на первом шаге обратного прохода таблицы, а состояние 4 – при последующих шагах ( Рис. 57. Состояние 4 автомата aR при состоянии 4 или 4' автомата aM Состояния 2 и 3 автомата aR отображают результат выбора альтернативных вариантов при обратном проходе по таблице T. В состоянии отображается ситуация, в которой следующий предмет найден, в то время как в состоянии 3 отображается ситуация, в которой происходит переход к следующей ячейке (рис. 58–59).

Рис. 58. Состояние 2 автомата aR при состоянии 4 или 4' автомата aM Рис. 59. Состояние 3 автомата aR при состоянии 4 или 4' автомата aM соответствующее случаю, в котором решение отсутствует.

соответствующее случаю, в котором решение найдено.

Архитектура визуализатора выбрана аналогично базовому методу. Она построена на основе паттерн MVC [52]. При этом полученные на предыдущих шагах автоматы Мура реализуют контроллер, поскольку они обрабатывают глобальные данные, представляющие модель ( Как видно из схемы взаимосвязей компонент визуализатора, он взаимодействующих автоматов самостоятельно обеспечивает не только логику алгоритма, но также логику разбиения на уровни визуализации.

15. Программная реализация визуализатора Поскольку в рассматриваемом примере используются автоматы Мура, то программная реализация каждого автомата выполняется с помощью двух операторов switch, первый из которых реализует переходы между состояниями, а второй – действия в них. Как было отмечено выше, формирователь (листинг 7).

Листинг 7.

1 switch (globals.aM.state()) { 3 // Иллюстрация: начальное состояние 4 case 11: // в состояниях 1’ и 1 иллюстрации совпадают 6 switch (globals.aFR.state()) { 8 // Иллюстрация: заполнение первой строки 10 case 21: // в состояниях 2’ и 2 иллюстрации совпадают 11 case 2:

12 switch (globals.aFC.state()) { 14 // Иллюстрация: заполнение первого столбца 16 case 31: // в состояниях 3’ и 3 иллюстрации совпадают 17 case 3:

18 switch (globals.aT.state()) { 19 case 21: // в состояниях 2’ и 2 иллюстрации совпадают 21 switch (globals.aTR.state()) { 23 // Иллюстрация: перенос значения из предыдущей строки 25 // Иллюстрация: альтернатива – выбор большего из значений 28 case 41: // в состояниях 4’ и 4 иллюстрации совпадают 29 case 4:

30 switch (globals.aR.state()) { 32 // Иллюстрация: набор существует 33 case 1: // в состояниях 1 и 4 иллюстрации совпадают 35 // Иллюстрация: альтернатива обратного прохода при поиске набора 37 // Иллюстрация: новый предмет найден 39 // Иллюстрация: переход к предыдущей строке 41 case 5:

42 // Иллюстрация: набор не существует 43 case 6:

44 // Иллюстрация: конец, набор найден Для пропуска неинтересных состояний используется следующий код (листинг 8).

Реализация шага визуализации с учетом пропуска неинтересных, а Листинг 8.

также детализированных переходов 2 * Один шаг визуализатора состоит из нескольких переходов автомата 4 public final void step() { 5 // осуществить автомата (если есть вложенный автомат, 6 // то переход будет осуществлен у вложенного автомата) 7 makeAutomationStep();

8 // пропустить неинтересные детальные состояния 9 skipHiddenStates();

11 /** 12 * Пропуск неинтересных состояний 14 private void skipHiddenStates() { 15 // если состояние скрытое либо текущий автомат находится ниже уровня пропуска 16 while (!stopped() && (isHidden() || level < g.skipLevel)) { 17 // при завершении вложенного автомата – убрать на него ссылку 18 if (inner != null && inner.stopped()) { 21 // если текущий автомат находится выше уровня пропуска, 22 // то пропуск надо завершить 23 if (g.skipLevel = 0;

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

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

Таблица 5. Сравнение метрик автоматов для примера «задача о рюкзаке»

Число автоматов Общее число состояний автоматов Число строк кода для реализации автоматов Дальнейшее развитие метода изложенного в третьей главе реализовано в статье [74], а также в системе визуализации Vizi [42, 43].

1. В главе изложен формализованный метод построения визуализаторов алгоритмов на основе системы взаимодействующих автоматов.

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

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

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

ГЛАВА 4. АВТОМАТНЫЙ ПОДХОД К ОБЕСПЕЧЕНИЮ

ПРОСТОЙ АНИМАЦИИ В ВИЗУАЛИЗАТОРАХ АЛГОРИТМОВ

ДИСКРЕТНОЙ МАТЕМАТИКИ

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

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

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

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

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

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

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

Для построения визуализатора с анимацией предлагается применять четыре автомата:

• автомат, реализующий алгоритм (формируется на восьмом этапе • автомат визуализации (формируется на девятом этапе);

• преобразованный автомат визуализации;

• автомат анимации.

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

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

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

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

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

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

Рис. 63. Формирование состояний автомата визуализатора На этом этапе вводится выходное воздействие z0, осуществляющее формирование статического изображения и комментария в рассматриваемом состоянии. Различия в изображениях и комментариях формализуются с помощью функции FS (S), параметром которой является номер состояния S. В каждом состоянии, формирующем выходное воздействие z0, переход к следующему состоянию выполняется по событию e0 (нажатие клавиши «шаг» в интерфейсе визуализатора).

4.1.3. Введение анимационных состояний в автомат визуализации Поясним каждый из вновь вводимых этапов a – e.

На этапе a выполняется выбор анимационных состояний в соответствии с особенностями алгоритма и принятыми решениями по анимации на четвертом этапе исходного метода («Анализ алгоритма для визуализации»). Так как в алгоритме обхода двоичного дерева наибольший интерес представляет процесс перехода между вершинами, то состояния, в которых происходит переход, и будут выбраны в качестве анимационных.

На этапе b в автомате визуализации для получения преобразованного автомата этого типа каждое анимационное состояние формально заменяется тремя состояниями (рис. 64).

Опишем это преобразование. Предположим, что состояние S выбрано для визуализации. Предположим также, что в этом состоянии изменяются значения визуализируемых переменных v1, …, vn. При этом переменной vi присваивается значение выражения < expri >. Преобразование состоит в замене выбранного состояния на три состояния – S', S и SA.

В состоянии S' значения переменных v1, …, vn предварительно сохраняются в переменных old_v1, …, old_vn, а также проводятся все действия, выполняемые в состоянии S автомата визуализации.

В состоянии S' преобразованного автомата визуализации в отличие от состояния S исходного автомата этого типа не происходит ожидания события, а выполняется переход в одно из состояний SA или S.

Переход в состояние SA производится, если переменная x1A принимает значение истина (анимация включена). Анимация осуществляется, пока преобразованный автомат визуализации находится в состоянии SA. При входе в это состояние выполняется запуск автомата анимации при помощи события e1A: старт и отображается иллюстрация FA(S, 0), соответствующая началу анимации.

Выход из состояния анимации и переход в состояние S происходит, как по событию e0 (нажатие клавиши), так и по событию e3A (окончание обеспечивается как автоматическое, так и ручное завершение анимации. Схема взаимодействия [59] преобразованного автомата визуализации представлена на рис. 65.

Рис. 65. Схема взаимодействия преобразованного автомата визуализации Состояние S является завершающим. В нем выполняется отображение статической иллюстрации FS (S). Отметим, что поскольку в преобразованном анимационном автомате присутствуют действия на дугах, то этот автомат является смешанным автоматом – автоматом Мура-Мили.

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

На этапе c строится автомат анимации (рис. 66). Следует отметить, что он является смешанным автоматом, поскольку содержит действия как на дугах, так и в вершинах графа перехода.

Из рассмотрения этого рисунка следует, что автомат предназначен для изменения значения переменной step, которая хранит номер шага анимации.

Автомат анимации формирует следующие выходные воздействия и события:

• z1A: запустить таймер – запускает таймер, который через период времени T генерирует событие eTA;

необходимости перерисовать иллюстрацию;

• e3A: конец анимации – сигнализирует о том, что анимация Анимационный автомат реагирует на следующие события:

• e1A: старт – автомат визуализации перешел в состояние, в котором должна начаться анимация;

• e2A: стоп – автомат визуализации перешел в состояние, в котором анимация должна закончиться;

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

Описанный автомат является универсальным и может быть использован в любом визуализаторе.

На этапе d автомат визуализации и автомат анимации связываются посредством событий и выходных воздействий, как показано на рис. 67.

4.1.5. Обеспечение отображения анимации сопоставления номера состояния с текстовым комментарием и статической иллюстрацией расширяется. В режиме анимации «рисовальщик» принимает на вход значение номера шага. Другими словами, если функция FS реализует статические иллюстрации, а функция FA – динамические (анимационные) иллюстрации, то при переходе от статики к анимации осуществляется преобразование вида:

При этом справедливы следующие соотношения: