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

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

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

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

Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (образование)

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

1 6 2Г.1

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

004617795

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики (СПбГУ ИТМО)

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

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

Парфенов Владимир Глебович

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

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

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

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

Тимченко Борис Дмитриевич

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

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

Защита диссертации состоится 27 декабря 2010 года в 11 часов 00 минут на заседании диссертационного совета Д 212.227.06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр. 49.

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

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

Ученый секретарь диссертационного совета, ,

доктор технических наук, профессор ¿¡г^Р__ Л.С. Лисицына

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. На кафедре КТ при разработке визуализаторов для образовательного портала «Интернет-школа программирования» (http://ips.ifmo.tu).

2. В учебном процессе на кафедре КТ по курсу «Теория автоматов в программировании».

3. На кафедре КТ при разработке визуализаторов в рамках учебного курса «Дискретная математика» (http://rain.ifmo.ru/cat/).

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

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

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

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

Награды. В 2008 году автор стал лауреатом премии Правительства Российской Федерации в области образования в составе авторского коллектива научно-практической разработки «Инновационная система поиска и подготовки высококвалифицированных специалистов в области производства программного обеспечения на основе проектного и соревновательного подходов». В рамках этого проекта автор работал над разработкой

методов построения визуализаторов и созданием Интернет-школы программирования ОШрМра.П'то.гиЛ.

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

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

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

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

Визуализатор - это программа, иллюстрирующая выполнение алгоритма при определенных входных данных. В задачи визуализатора алгоритма входит:

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

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

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

4. Пошаговое исполнение алгоритма.

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

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

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

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

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

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

• Отсутствует формализованный подход к переходу от алгоритма к визуализатору.

• Отсутствует метод выделения визуализируемых контрольных точек.

• Отсутствует метод перехода между контрольными точками визуализатора

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

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

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

1. Наличие готовых библиотек по построению пользовательского интерфейса

2. Возможность встраивать приложения в страницы.

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

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

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

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

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

Платформа 1 2 3 4 5

Flash + + + - +

Adobe AIR + + + + -

Silverlight + + - - -

Delphi + - - + -

Java Applets + + + + +

JavaScript ± + + ± +

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

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

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

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

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

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

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

Визуализатор «по-крупному» предлагается строить на основе паттерна проектирования Model - View - Controller.

• по алгоритму формализованным способом строится автомат, описывающий поведение визуализатора (контроллер - Controller);

• выбираются визуализируемые переменные (модель - Model)-,

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Анализ алгоритма для визуализации.

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

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

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

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

9. Формирование набора нсвизуализируемых переходов (состояний).

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

11. Сопоставление иллюстраций и комментариев с состояниями автомата.

12. Выбор архитектуры программы визуализатора.

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

В табл. 2 выполнено сравнение модификаций предлагаемого метода на примере «Задачи о рюкзаке».

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

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

Особенность Автоматы Мили Автоматы Мура

Число состояний 10 18

Исключение иллюстраций «Неинтересные» переходы «Неинтересные» состояния

Иллюстрации Состоянию соответствует одна или несколько иллюстраций Каждому состоянию соответствует одна иллюстрация

Число строк кода для реализации автоматов 85 187

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

• несмотря на большую распространенность традиционный эвристический подход методом не является;

• для алгоритмов дискретной математики явное выделение состояний по словесной формулировке может быть выполнено сравнительно редко. Однако когда это удастся, применение автоматного метода для построения визз'ализаторов весьма эффективно;

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

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

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

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

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

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

b) При построении схемы алгоритма по программе на седьмом этапе строится не одна, а несколько схем: одна схема строится для главного алгоритма и по одной схеме для каждой процедуры.

c) На восьмом этапе проводятся преобразования для каждого автомата.

с1) На девятом этапе, происходит формирование набора неинтересных состояний системы автоматов.

е) На одиннадцатом этапе при формировании иллюстраций, они сопоставляются не состояниям автомата, а состояниям системы автоматов.

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

Выполнение процедуры Р

Запуск автомзта

InltiaP);

Выполнение автомата aP.stepO;

3D-

1: aP.stopped{)

Алгоритм

Этап 2

Т~

J2 L

Рис. 1. Преобразование вызова вложенной Рис. 2. Назначение уровней каждому

процедуры автомату

На рис. 2 используются следующие обозначения: Р - процедура, выполняющая крупных шаг алгоритма; аР - автомат, полученный преобразованием схемы алгоритма процедуры Р в граф переходов автомата Мура; aP.stopped() — булево выражение, которое принимает значение true в случае окончания работы автомата; aP.stepQ - выполнение одного перехода вложенного автомата Мура.

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

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

Формирователь иллюстраций должен реализовывать функцию Fj(S) = Fs(su sb ...,%), переводящую состояния системы автоматов в иллюстрацию. Поскольку до построения формирователя иллюстраций строится список «интересных» К к

состояний {V,-}J=i={ {vi,v2.....vv)j};-=1, то при формировании операторов switch необходимо

построить иллюстрации лишь для интересных состояний.

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

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

7. Преобразование схем алгоритма в графы переходов системы автоматов Мура.

8. Формирование набора «неинтересных» состояний для каждого автомата.

9. Назначение уровня детализации каждому из автоматов.

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

11. Сопоставление иллюстраций и комментариев с состояниями автоматов.

12. Выбор архитектуры программы визуализатора.

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

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

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

Особенность Одни автомат Система автоматов

Число автоматов 1 б

Общее число состояний автоматов 16 32

Число строк кода для реализации автоматов 187 455

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

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

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

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

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

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

a) выбор состояний автомата визуализации, в которых выполняется анимация (такие состояния будем назвать анимационными);

b) построение преобразованного автомата визуализации путем замены каждого из анимационных состояний тремя состояниями по схеме указанной ниже;

c) разработка анимационного автомата и обеспечение его взаимодействия с преобразованным автоматом визуализации;

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

Отметим, что формирование автомата визуализации состоит во введении в каждое состояние 5 выходного воздействия гО, осуществляющего формирование статического изображения и комментария ¡''$(3). При этом переход к следующему состоянию осуществляется по событию еО (нажатие клавиши «шаг» в визуализаторе).

На этапе Ь в автомате визуализации для получения преобразованного автомата этого типа каждое анимационное состояние формально заменяется тремя состояниями (рис. 3). При этом 5 - «интересное» состояние, в котором визуализируемым переменным V,-присваивается значение выражений <ехрг1>. Преобразование состоит в замене выбранного состояния на три состояния — 5', 5 и 3А.

В состоянии 5" старые значения переменных V/,..., V,, предварительно сохраняются в переменных ои_у/,..., оШ_у„, а также проводятся все действия, выполняемые в состоянии 5 автомата визуализации. В состоянии 5' преобразованного автомата визуализации, в отличие от состояния 5 исходного автомата этого типа, не происходит ожидания события, а выполняется переход в одно из состояний или 5.

Рис. 3. Преобразование анимационного состояния При этом х1л принимает значение истина, если анимация включена. Анимация выполняется, пока преобразованный автомат визуализации находится в состоянии SA. При входе в это состояние выполняется запуск автомата анимации при помощи события elA: старт и отображается иллюстрация FA(S, 0), соответствующая началу анимации. Выход из состояния анимации и переход в состояние S происходит, как по событию еО (нажатие клавиши), так и по событию еЗл (окончание анимации), и сопровождается событием е2А: стоп. Таким образом, обеспечивается как автоматическое, так и ручное завершение анимации. Состояние S - завершающее, в нем выполняется отображение статической иллюстрации Fs(S).

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

На этапе с строится автомат анимации (рис. 4), изменяющей по таймеру значения переменной step, которая хранит номер шага анимации.

Рис. 4. Автомат анимации

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

• zlа'- запустить таймер - запускает таймер, который через период времени Т генерирует событие еТА;

• z0\: вывести FA(Sa. step) - информирует «рисовальщик» о необходимости перерисовать иллюстрацию;

• еЗл: конец анимации - сигнализирует о том, что анимация закончилась.

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

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

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

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

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

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

Г FJ state);

F(state) -»< 1

[FA(state,step)

При этом F¿state) = F(state), F¿(state, 0) = F^state - 1), FA{state,N) = F¡(state). Другими словами преобразованный автомат визуализации формирует статические иллюстрации, совпадающие с иллюстрациями исходного автомата. Формирование анимационных иллюстраций в состоянии state происходит таким образом, что начальная иллюстрация совпадает со статической иллюстрацией в предыдущем состоянии автомата, а конечная - со статической иллюстрацией в состоянии state.

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

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

11. Замена каждого из выбранных состояний тремя состояниями.

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

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

14. Сопоставление иллюстраций и комментариев с состояниями автомата.

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

16. Выбор архитектуры программы визуализатора.

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

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

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

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

В рамках проекта «Интернет-школа программирования», выполняемого в 1999 -2001 гг. на кафедре КТ, визуализаторы алгоритмов дискретной математики разрабатывались традиционным методом. Начиная с 2002 г. в процессе построения визуализаторов, использовался метод, предложенный в настоящей работе. При этом сначала использовался ручной метод, а в дальнейшем визуализаторы создавались на базе системы визуализации Vizi, которая основана на совместной статье автора настоящей диссертации с Г.А. Корнеевым.

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

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

Подход Затраты студента Затраты преподавателя

Простые алгоритмы Сложные алгоритмы

Традиционный эвристический 80-120 120-180 8-10

Автоматный эвристический 10-20 40-80 2-3

Автоматный формализованный 2-5 20-40 менее одного часа

Система Vizi 5-10 10-20 менее одного часа

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

1. Казаков Ы. А., Васильев В. П., КорнеевГ. А., Парфенов В. Г., Шалыто А. А. Три кита подготовки программистов II Открытые системы. 2009. № 3, с. 54-56.

2. Казаков М. А., Шалыто А. А. Методы построения логики визуализаторов алгоритмов // Открытое образование. 2005. № 4, с. 53-58.

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

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

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

Другие публикации

6. Казаков М. А., Остова Т. Г., Парфенов В. Г., Столяр С. Е. Интернет-школа программирования в СПбГИТМО (ТУ) / Тезисы докладов Всероссийской научно-методической конференции «Телематика'99». СПбГИТМО (ТУ). 1999, с. 165,166.

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

8. КазаковМ. А., Столяр С. Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования / Тезисы докладов международной научно-методической конференции «Телематика'2000». СПбГУ ИТМО. 2000, с. 189-191.

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

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

11. Казаков М. А. Создание системы проведения Интернет-соревнований и дистанционного обучения программированию //Телекоммуникации и информатизация образования. 2002. № 6, с. 81-100.

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

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

14. Казаков М. А. Использование автоматного подхода для построения визуализаторов I Вестник конференции молодых ученых СПбГУ ИТМО. 2004, с. 166-180.

15. Казаков М. А. Система автоматического тестирования программных решений и проведения соревнований в режиме on-line / Вестник конференции молодых ученых СПбГУ ИТМО. 2004, с. 181-189.

16. Казаков М. А., ШалытоА.А. Реализация визуализаторов на основе автоматного программирования / Тезисы докладов Всероссийской научно-методической конференции «Телематика'2004». СПбГУ ИТМО. 2004, с. 191, 192.

17.КазаковМ.А., ШалытоА.А. Технология построения визуализаторов алгоритмов на основе автоматного подхода / Тезисы докладов Всероссийской научно-методической конференции «Телематика'2005». СПбГУ ИТМО. 2005, с. 507-509.

18.КазаковМ.А. Реализация концепции многоуровневой системы дистанционного обучения на базе Интернет школы программирования. / Вестник конференции молодых ученых СПбГУ ИТМО. 2005, с. 176-183.

19 .Казаков М. А., Васильев В. Н., Корнеев Г. А., Парфенов В. Г., ШалытоА.А.

Инновационная система поиска и подготовки высококвалифицированных разработчиков программного обеспечения на основе проектного и соревновательного подходов / Труды Первого Санкт-Петербургского конгресса «Профессиональное образование, наука, инновации в XXI веке». СПбГУ ИТМО. 2007, с. 84-97.

20 .Казаков М. А., Васильев В. П., Корнеев Г. А., Парфенов В. Г., ШалытоА.А.

Применение проектного подхода на основе автоматного программирования при подготовке разработчиков программного обеспечения / Труды Первого Санкт-Петербургского конгресса «Профессиональное образование, наука, инновации в XXI веке». СПбГУ ИТМО. 2007, с. 98-100.

21 .Казаков М. А., Васильев В. Н., Корнеев Г. А., Парфенов В. Г., ШалытоА.А.

Автоматное программирование и проектный подход при подготовке разработчиков программного обеспечения / Труды научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях». СПбГПУ. 2008, с. 248-250.

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

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

ВВЕДЕНИЕ.

ГЛАВА 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. Сравнение традиционного и автоматных (эвристического и формализованного) методов-разработки визуализаторов алгоритмов73

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.107.

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

4.1. Метод обеспечения простой анимации.

4.1.1. Дополнительные этапы метода для обеспечения анимации.

4.1.2. Формализация построения автомата визуализации.

4.1.3. Введение анимационных состояний в автомат визуализации

4.1.4. Построение автомата анимации.

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

4Л-.6. Введение новых-этапов в метод.1Д

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

4.3. Построение визуализатора на примере алгоритма обхода двоичного дерева.

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

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

5.1. Применение эвристического автоматного подхода.

5.2. Применение автоматного подхода.

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

5.2.2. Применение автоматного подхода студентами.

5.3. Использование в Интернет-школе программирования.

5.4. Дальнейшее развитие предлагаемого подхода.

5.5. Сравнение трудозатрат на создание визуализаторов различными методами.

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

Актуальность проблемы. С вводом Федеральных государственных образовательных стандартов (ФГОС) [1] усиливается роль самостоятельной, работы студентов (СРС) [1], что требует разработки, новых образовательных технологий для ее поддержки. Кроме того ФГОС содержат требование к обеспечению не-менее 10-20% аудиторных занятий студентов в интерактивной форме. Это обстоятельство ставит новые задачи по разработке интерактивных средств обучения, призванных индивидуализировать образовательный процесс массовой подготовки, выпускников вузов. При уровневой подготовке выпускников'вузов,информационной направленности важное место занимают методы и алгоритмы* дискретной математики, изучение1 которых создает базис (базовые знания, умения и навыки) для формирования различных универсальных (общекультурных) и профессиональных навыков выпускников. Уже сейчас во многих вузах РФ применяются виртуальные лаборатории, тренажеры и электронные тьюторы, для поддержки практических и самостоятельных занятий по изучению. алгоритмов дискретной математики. Многие годы эти* алгоритмы изучались по книгам; в- которых практически невозможно было- отразить динамику [2-6]'. В восьмидесятых- годах двадцатого века в нескольких американских университетах [7], а в конце девяностых годов; также и в Санкт-Петербургском государственном университете- информационных технологий, механики и оптики (СПбГУ ИТМО) [8, 9, 78, 80] и Санкт-Петербургском государственном университете (СПбГУ) [10; 11] пришли к выводу, что алгоритмы следует изучать не только в статике в виде диаграмм, но- и-в динамике (в процессе-работы). Для. этого необходимо строить специальные программы, которые должны представлять алгоритмы в удобной для обучающихся форме: наряду с текстовыми комментариями должны отображаться динамические иллюстрации. Программы для реализации динамических иллюстраций, были названы визусишзаторами. В' течение последних 10 лет проблемами построения визуализаторов занимались

6 . многие специалисты в, СПбГУ ИТМО, [12] и СПбГУ [10, 11, 13], в том-числе автор настоящей диссертации- [76,7В]. Однако все эти работы обладали? существенным недостатком: визуализаторы для- каждого алгоритма индивидуально и- отсутствовали какие-либо1 методы их формализованной;: реализации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

1. Федеральный портал «Российское образование» http://www.edu.ru

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

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

4. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск. М.: DiaSoft, 2001. 687 с.

5. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильяме, 2010.-400 с.

6. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский Диалект, 2008.-352 с.

7. Lawrence A., Badre A., Stassko J. Empirically evaluating the use of animations to teach algorithms. Technical report. Graphics Visualization and Usability Center, Georgia Institute of Technology, 1993.

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

9. Романовский И. В. Демонстрационные программы: 1. Решето Эратосфена // Компьютерные инструменты в образовании. 2007. № 1, с. 63-65.

10. Романовский И. В., Дьяченко В. В. Демонстрационные программы: 2. Суффиксный массив // Компьютерные инструменты в образовании. 2007. № 2, с. 56-60.

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

12. Романовский И. В., Черкасова П. Г. Пакет демонстрационных программ по курсу дискретного анализа «DADemo» // Компьютерные инструменты в образовании. 2002. № 1, с. 55-61.

13. Удов Г. Г., Шалыто А. А. Классическая и автоматная реализация визуализатора алгоритма пирамидальной сортировки набора чисел. СПбГУ ИТМО, 2004. http://is.ifino.ru/vis/pyr/

14. Принг Э. Конечные автоматы в JavaScript. Часть 1. Разработаем виджет. http://v\Avw.ibm.com/developerworks/m/HbraiVwa-finitemachl/

15. Принг Э. Конечные автоматы в JavaScript. Часть 2. Реализация^виджета. http://www.ibm.com/developerworks/ru/library/wafïnitemach2/twa-finitemac ru.html

16. Принг Э. Конечные автоматы в JavaScript. Часть 3. Тестируем виджет. http.7/www.ibm.com/developerworks/ru/library/wa-finitemach3/

17. Коломейцева О. М., Шалыто A.A. Преимущества автоматического* синтеза программ на языке JavaScript по автоматной спецификации (на примере реализации элемента управления ToolTip). СПбГУ ИТМО, 2007. http,7/is.ifmo.ru/projects/javascript/

18. Андерсон Д. Дискретная математика и комбинаторика. М.: Вильяме, 2004. 960 с.

19. Колмогоров А. ff. Теория информации и теория алгоритмов. — М.: Наука, 1987.-304 с.

20. Sim Oracle Java, http://www.oracle.com/technetwork/iava/index.html

21. Пратт. Т., Зелковиц M. Языки программирования: разработка и реализация. СПб.: Питер, 2002. 688 с.

22. Агапонов С. В., Джалиашвили 3. О., Кречман Д. JI. и др. Средства дистанционного обучения. Методика, технология, инструментарий. СПб.: БХВ-Петербург, 2003.-336 с.

23. Васильев В. Н., Елизаров Р. А., Парфенов В. Г., Столяр С. Е. Организация дистанционного обучения программистов / Тезисы докладов Всероссийской научно-методической конференции «Телематика'98». СПбГУ ИТМО. 1998, с. 172, 173.

24. Brown М., Sedgewick R. A system for Algorithm Animation / Proceedings of the 11th annual conference on Computer graphics and interactive techniques. 1984.

25. Интернет-школа программирования, http://ips.ifmo.ru/

26. GittaD. Tutorial on Visualization. http://www.siggraph.org/education/materials/HyperVis/domiic/folien.html

27. Owen G. S. Visualization Concepts: Overview, http://www.siggraph.org/ education/materials/HyperVis/concepts/overview.htm

28. Complete Collection of Algorithm Animations, http://www.cs.hope.edu/ -alganim/ccaa/

29. Interactive Data Structure Visualizations, http://www.student.seas.gwu.edu/ —idsv/idsv.html

30. Jawaa examples, http://www.cs.duke.edu/csed/iawaa2/examples.html

31. Sorting Algorithms. http:/Avww.cs.rit.edu/~atk/Java/Sorting/sorting.html

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

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

34. Stasko J. Tango: A Framework and System for Algorithm Animation.

35. Technical Report. Brown University Providence, 1989. 31.Rdfiling G„ Freisleben B. ANIMAL: A System for Supporting Multiple Roles in Algorithm Animation //Journal of Visual Languages and Computing. Vol. 13. 2002. Issue 3.

36. Crescenzi P., Demetrescu C., Finocchi I:, Petreschi R. Reversible execution and visualization of programs with Leonardo // Journal of Visual Languages and Computing (JVLC). Vol. 11. 2000: Issue 2.

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

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

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

40. Корнеее Г. А., Шалыто А. А. Требования к визуализаторам алгоритмов, выполняемых на базе технологии Vizi, http://is.ifmo.ru/vis/req/

41. Корнеее Г. А. Автоматизация построения визуализаторов алгоритмов дискретной математики на основе автоматного подхода. Диссертацияна-соискание ученой степени канд. техн. наук. СПбГУ ИТМО, 2006.1http://is.ifmo.ru/disser/korndisser.pdf

42. Шалыто А. А. Технология автоматного программирования // Мир ПК. 2003. № Ю, с.74-78. http://is.ifmo.ru/works/tech aut prog/

43. Adobe Flash. http://\vww.adobe.com/flashplatform/

44. Microsoft Silverlight. http://www.silverliglit.net/

45. Флэнаган Д. JavaScript. Подробное руководство. СПб.: Символ-Плюс, 2008. 992 с.

46. Adobe AIR. http://www.adobe.com/products/air/

47. Sun Oracle Java Applets, http://java.sun.com/applets/

48. Туккель Н. К, Шалыто А. А., Шамгунов Н. Н. Реализация рекурсивных алгоритмов на основе автоматного подхода // Телекоммуникации и информатизация образования. 2002. № 5, с. 72-99. http://is.ifmo.ru/works/recurse/

49. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий. М.: Вильяме, 2008. — 652 с.

50. Гамма Э., Хэлм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001.-325 с.

51. Фаулер М. Архитектура корпоративных программных приложений. М.: Вильяме, 2004. 544 с.

52. Портянкин И. Swing. Эффектные пользовательские интерфейсы. СПб.: Питер, 2005. 528 с.

53. Крейн Д., Бибо Б., Сонневелъд Дж. Ajax на практике. — М.: Вильяме, 2007. 464 с.

54. Conway J. Н., Guy R. К. The Book of Numbers. NY: Springer-Verlag. 1996, pp. 127-130.

55. Решето Эратосфена. http .7/ru. w i kip e d i a. or g/wiki/P e шето Эратосфена

56. Шалыто А. А., Туккель H. И. Преобразование итеративных алгоритмов в автоматные // Программирование. 2002. № 5, с. 12-26. http://is.ifíno.ru/works/iter/

57. Шалыто А. А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. — 628 с. http://is.ifmo.ru/books/switch/l

58. Шалыто А. А., Туккель Н. И. От тьюрингова программирования к автоматному // Мир ПК. 2002. № 2, с. 144-149. http ://is. i fino .ru/works/turing/

59. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М.: ДМК Пресс, 2001.-432 с.

60. Шенъ А. Программирование: теоремы и задачи. М.: МЦНМО, 2004. 296 с.

61. Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 1999. -240 с.

62. Сайт по автоматному программированию, http://is.ifmo.ru

63. Добровольский В. А., Степук А. В. Сортировка подсчетом. СПбГУ ИТМО, 2004. http://is.ifino.ru/vis/countsort/

64. Корниенко А. А. Автоматный подход к реализации элементов графического пользовательского интерфейса. СПбГУ ИТМО, 2004. http://is.ifmo.ru/papers/komienko/

65. Wright Th. P. Learning Curve // Journal of the Aeronautical Sciences, 1936.1. Публикации автора

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

67. Казаков М. А., Шалыто А. А. Методы построения логики визуализаторов алгоритмов // Открытое образование. 2005, № 4, с. 53-58.

68. Казаков М. А., Шалыто А. А. Реализация анимации при построении-визуализаторов алгоритмов на основе автоматного подхода // Информационно-управляющие системы. 2005. №4, с. 51-60. http://is.ifmo.ru/works/visanim/

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

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

71. Казаков М. А., Васильев В. Н., Корнеев Г. А., Парфенов В. Г., Шалыто А. А. Три кита подготовки программистов // Открытые системы. 2009. № 3, с. 54-56.1621. Другие статьи

72. Казаков М. А. Создание системы проведения Интернет-соревнований и дистанционного обучения программированию // Телекоммуникации и информатизация образования. 2002. № 6, с. 81-100.

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

74. Казаков М. А., Столяр С. Е. Подготовка тестов как часть технологии автоматизированного тестирования / Тезисы докладов XXX науч.-техн. конф. проф.-преподавательского состава. СПбГИТМО (ТУ). 1999, с.105.

75. Казаков М. А., Осипова Т. Г., Парфенов В. Г., Столяр С. Е. Интернет-школа программирования в СПбГИТМО (ТУ) / Тезисы докладов Всероссийской научно-методической конференции «Телематика'99». СПбГИТМО (ТУ). 1999, с. 165, 166.

76. Казаков М. А., Столяр С. Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования / Тезисы докладов международной научно-методической конференции «Телематика'2000». СПбГУ ИТМО. 2000, с. 189-191.

77. Казаков М. А., Шалыто А. А., Туккелъ Н. И. Использование автоматного подхода для реализации вычислительных алгоритмов

78. Тезисы докладов международной научно-методической конференции! «Телематика'2001». СПбГУ ИТМО. 2001, с. 174-176.

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

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

81. Казаков- М. А. Использование автоматного подхода для построения визуализаторов; / ■ Вестник конференции; молодых ученых СПбГУ ИТМО. 2004. с. 166-180.

82. Казаков М. А. Система автоматического тестирования: программных решений', и проведения соревнований в режиме on-line / Вестник конференции молодых ученых СПбГУ ИТМО. 2004, с. 181-189.

83. Казаков М. А., Шалыто А. А. Реализация визуализаторов на основе автоматного, программирования / Тезисы докладов Всероссийской^ научно-методической конференции «Телематика'2004>>. .СПбГУ ИТМО. 2004, с. 191, 192.

84. Казаков М. А., Шалыто А. А. Технология построения визуализаторов алгоритмов на основе автоматного подхода / Тезисы докладов Всероссийской научно-методической конференции «Телематика'2005». СПбГУ ИТМО; 2005, с. 507-509;

85. Ю.Казаков М.А. Реализация концепции многоуровневой системы дистанционного обучения на; базе Интернетгшколы, программирования. / Вестник конференции молодых ученых СПбГУ ИТМО. 2005, с: 176-183.

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

87. Министерство образования РФ. НИР № 10038 «Разработка технологии создания программного- обеспечения систем управления на основе автоматного подхода». Этап 1. «Алгоритмизация программирования задач логического управления». СПбГУ ИТМО.' 2000;

88. Грант РФФИ по проекту 02-07-90114 «Разработка технологии автоматного программирования». Этап 1. «Разработка технологии автоматного программирования для событийных систем». СПбГУ ИТМО, 2002.

89. Министерство образования РФ. НИР № 10038 «Разработка технологии создания программного обеспечения систем управления на основе автоматного подхода». Этап 4. «Применение автоматного подхода в объектно-ориентированном программировании». СПбГУ ИТМО, 2003.

90. Грант РФФИ по проекту 02-07-90114 «Разработка технологии автоматного программирования». Этап 2. «Расширение области использования автоматного программирования». СПбГУ ИТМО, 2003.