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

• Автор: Казаков, Матвей Алексеевич
• Шифр специальности: 05.13.06
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Санкт-Петербург
• Количество страниц: 178 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

ГЛАВА 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.7 .
ГЛАВА 4. АВТОМАТНЫЙ ПОДХОД К ОБЕСПЕЧЕНИЮ ПРОСТОЙ АНИМАЦИИ В ВИЗУАЛИЗАТОРАХ АЛГОРИТМОВ ДИСКРЕТНОЙ МАТЕМАТИКИ
4.1. Метод обеспечения простой анимации.
4.1.1. Дополнительные этапы метода для обеспечения анимации
4.1.2. Формализация построения автомата визуализации
4.1.3. Введение анимационных состояний в автомат визуализации.
4.1.4. Построение автомата анимации.
4.1.5. Обеспечение отображения анимации.
4.1.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
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСТОЧНИКОВ


Эта теория рассматривает общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления []. Одной из актуальных проблем в обучении дискретной математике и про! Автор настоящей диссертации занимается проблемами обучения дискретной математике с г. Проблема обучения алгоритмам дискретной математики существует с начала их использования в вычислительной технике. Сначала алгоритмы' изображались в текстовом виде, потом - в виде схем алгоритма (блок-схем), а затем в виде псевдокода. Современные книги описывают алгоритмы в виде набора примеров входных и выходных данных, а также исходного кода алгоритма; реализованного на одном из императивных языков программирования, таких как C/C++, Pascal или Java []. Статическое восприятие текста с динамической прокруткой в голове. Реализация алгоритма на выбранном языке программирования, либо копирование алгоритма из. Первый способ является достаточно сложным для большинства учащихся, поскольку требует программистского воображения. Он доступен лишь опытным программистам, а не учащимся старших классов школы или младших курсов института, только приступающим к изучению алгоритмов дискретной математики. Второй способ является более прямолинейным и доступным, однако акцентирует внимание не на сути алгоритма, а на его программной реализации-и тонкостях используемого языка программирования. Таким образом, традиционное статическое изложение материала по дискретной математике является- неэффективным с точки зрения изучения алгоритмов. Если первый способ требует определенных усилий, то второй и вовсе невозможно реализовывать на лекционных занятиях. Дальнейшие исследования в области преподавания дискретной математики привели к возникновению в середине восьмидесятых годов [7, ] нового подхода к преподаванию — появились визуализаторы алгоритмов дискретной математики. Визуализатор — это программа, иллюстрирующая выполнение алгоритма при определенных входных данных. Примерами визуализаторов могут служить, например, программа, занимающаяся построением графика функции, либо программа, визуально моделирующая какой-либо физический процесс. Применительно к дискретной математике и программированию, визуализаторы обычно моделируют некоторые алгоритмы, давая возможность обучающемуся при. Перечислим отличительные характеристики визуализаторов. Простота использования, определяемая понятностью интерфейса. Поэтому для работы с визуализатором обычно не требуется специальная подготовка. Четкость и простота представления визуализируемого процесса. Компактность визуализаторов. Эго при необходимости упрощает передачу визуализаторов в сети Интернет, что особенно важно при дистанционном обучении. Визуализаторы в рассматриваемой области решают следующие задачи, возникающие в процессе обучения. Графическое и текстовое разъяснение действий алгоритма на конкретных наборах входных данных. При этом понимание алгоритма не требуется, поскольку именно визуализатор должен объяснить действие алгоритма. Предоставление пользователю инструмента, реализующего данный алгоритм. В результате учащийся освобождается от необходимости выполнять шаги алгоритма, так как их автоматически выполняет визуализатор. Визуализатор выполняет обычно следующие функции. Пошаговое выполнение алгоритма. Просмотр действия алгоритма при разных наборах входных данных, в том числе и введенных пользователем. Просмотр действия алгоритма в динамике. Перезапуск алгоритма на текущем наборе входных данных. Для некоторых алгоритмов (например, машины Тьюринга) динамический вариант демонстрации вообще представляется более естественным, чем любой набор статических иллюстраций. Отображение входных и выходных данных в наглядной форме — доходчивое представление абстрактного понятия данные: в виде картинки. Такое представление необходимо, как для учащихся с начальным уровнем, подготовки, так и для более продвинутых учащихся с целью упрощения восприятия. Отображение внутренних служебных переменных. Изменение данных. Копирование и перемещение данных. Процесс принятия решений. Комментарии к каждому действию алгоритма. Огображение работы алгоритма по шагам.