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

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

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

Шифр специальности: 05.13.12

Научная степень: Кандидатская

Год защиты: 2006

Место защиты: Санкт-Петербург

Количество страниц: 181 с. ил.

Артикул: 3301324

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

Стоимость: 250 руб.

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

ОГЛАВЛЕНИЕ.
СПИСОК ТЕРМИНОВ.
ВВЕДЕНИЕ
ГЛАВА 1. СИСТЕМЫ ВИЗУАЛИЗАЦИИ АЛГОРИТМОВ ДИСКРЕТНОЙ
МАТЕМАТИКИ
1.1. Применение визуализаторов в учебном процессе
1.1.1. Варианты применения визуализаторов.
1.1.2. Требования к визуализаторам алгоритмов.
1.2. Обзор визуализаторов на примере алгоритмов сортировок
1.2.1. Подходы к визуализации алгоритмов сортировки.
1.2.2. Обзор визуализаторов алгоритмов сортировок.
1.2.3. Анализ визуализаторов алгоритмов сортировок
1.3. Обзор систем визуализации.
1.3.1. Развитие систем визуализации.
1.3.2. Классификация систем визуализации
1.3.3. Обзор общих систем визуализации
1.3.4. Обзор систем визуализации алгоритмов.
1.3.5. Анализ систем визуализации.
Выводы ПО ГЛАВЕ
ГЛАВА 2. ПРОЦЕСС ПОСТРОЕНИЯ ВИЗУАЛИЗАТОРОВ.
2.1. Структура визуализатора.
2.1.1. Варианты использования визуализатора.
2.1.2. Выделение основных частей визуализатора
2.2. Разработка визуализаторов.
2.2.1. Ручная разработки визуализаторов.
2.2.2. Автоматизация разработки визуализаторов
2.3. Модель данных визуализатора.
2.3.1. Требования к модели данных.
2.3.2. Подходы к построению модели данных
2.4. Логика визуализатора
2.4.1. Требования к логике визуализатора.
2.4.2. Подходы к реализации обратимого исполнения
2.4.3. Автоматный подход к построению логики визуализаторов
2.5. Язык ОПИСАНИЯ ВИЗУАЛИЗАТОРОВ
2.6. Задачи, решаемые в диссертационной работе.
Выводы ПО ГЛАВЕ
ГЛАВА 3. ПОСТРОЕНИЕ МОДЕЛИ ДАННЫХ И ПРЕОБРАЗОВАНИЕ
ПРОГРАММЫ К ПРИВЕДЕННОЙ ФОРМЕ
3.1. Построение модели данных
3.1.1. Этапы построения модели данных
3.1.2. Требования к исходной программе.
3.2. Построение модели данных по итеративной программе.
3.2.1. Создание модели данных
3.2.2. Модификация программы.
3.2.3. Упрощенная запись нотация.
3.2.4. Пример построения модели данных.
3.3. Построение модели данных по рекурсивной программе.
3.3.1. Построение модели данных
3.3.2. Модификация программы.
3.3.3. Пример выделения модели и модификации программы
3.3.4. Обращение правил именования.
3.4. Преобразование программы к приведенной форме
3.4.1. Типы операторов.
3.4.2. Оператор цикла с постусловием.
I 3.4.3. Оператор цикла со счетчиком
3.4.4. Оператор продолжения цикла
3.4.5. Оператор выхода из цикла
3.4.6. Оператор возврата из процедуры
3.4.7. Оператор выбора
3.4.8. Порядок преобразования операторов
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 4. ПРЕОБРАЗОВАНИЕ ПРОГРАММЫ В СИСТЕМУ
ВЗАИМОДЕЙСТВУЮЩИХ КОНЕЧНЫХ АВТОМАТОВ
4.1. Основные понятия
4.1.1. Исходная программа.
4.1.2. Фрагменты автоматов
4.2. Преобразование процедуры в автомат
4.2.1. Оператор присваивания
4.2.2. Последовательность операторов
4.2.3. Оператор вызова процедуры
4.2.4. Оператор ветвления.
4.2.5. Цикл с предусловием
4.2.6. Завершение построения автомата
4.2.7. Пример преобразования процедуры в автомат
4.3. Построение обратного автомата.
4.3.1. Обратные автоматы
4.3.2. Обращение операторов.
4.3.3. Обращение оператора присваивания.
4.3.4. Обращение последовательности операторов
4.3.5. Обращение оператора вызова.
4.3.6. Обращения операторов ветвления.
4.3.7. Обращение оператора цикла с предусловием.
4.3.8. Варианты построения обратного автомата.
4.3.9. Пример построения обратного автомата.
4.4. Процедуры и вызовы автоматов
4.4.1. Итеративные программы
4.4.2. Рекурсивные программы.
4.5. Формализация преобразования программы
4.5.1. Свойства автоматов.
4.5.2. Текстовая нотация
4.5.3. Преобразование оператора присваивания
4.5.4. Преобразование оператора ветвления.
4.5.5. Преобразование оператора цикла.
4.5.6. Преобразование оператора вызова процедуры.
4.5.7. Преобразование последовательностей операторов.
4.5.8. Преобразование процедуры
4.5.9. Завершение доказательства.
Выводы по главе 4.
ГЛАВА 5. ЯЗЫК ОПИСАНИЯ ВИЗУАЛИЗАТОРОВ.
5.1. Структура языка.
5.2. Описание визуализируемого алгоритма
5.2.1. Описание алгоритма
5.2.2. Описание процедур
5.2.3. Описание операторов
5.2.4. Переменные.
5.2.5. Пример описания визуализируемого алгоритма.
5.3. Описание конфигурации визуализатора
5.3.1. Группы, свойства и сообщения
5.3.2. Таблицы стилей.
5.3.3. Элементы управления
Выводы по главе 5.
ГЛАВА 6. ВНЕДРЕНИЕ ПРЕДЛОЖЕННЫХ МЕТОДОВ
6.1. Система визуализации Уш
6.1.1. Структура визуализатора.
6.1.2. Статическая часть
6.1.3. Отладка описания визуализатора.
6.1.4. Процесс построения визуализатора.
6.2. Пример построения визуализатора
6.2.1. Постановка задачи и анализ литературы
6.2.2. Создание визуализируемой программы.
6.2.3. Проектирование визуализатора.
6.2.4. Построение описания визуализируемой программы
6.2.5. Реализация визуального представления.
6.2.6. Реализация элементов управления
6.2.7. Интеграция и отладка визуализатора.
6.2.8. Выводы.
6.3. Сравнение с существующими подходами
6.3.1. Сравнение проектов визуализаторов
6.3.2. Визуализаторы, построенные на основе Vii
6.3.3. Выполнение требований к визуализаторам.
6.4. Практическое использование результатов работы
Выводы по главе 6.
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Печатные издания на русском языке.
Печатные издания на английском языке
Ресурсы сети I.
Публикации
ПРИЛОЖЕНИЯ
Приложение 1. Пример Xописания визуализатора.
Приложение 2. Исходный код визуализатора поиска максимума
СПИСОК ТЕРМИНОВ
Визуализаторы и системы визуализации
Визуализатор алгоритма визуализатор программа, отображающая на экране ход иили результаты выполнения алгоритма программы.
Визуализатор программы визуализатор, отображающий действия, осуществляемые при выполнении программы.
Визуализатор данных визуализатор, отображающий изменения в структурах данных, происходящих при выполнении алгоритма.
Система визуализации программный комплекс, позволяющий создавать и исполнять визуализаторы.
Система визуализации алгоритмов система визуализации, предназначенная для создания визуализаторов алгоритмов.
Система визуализации данных система визуализации алгоритмов, предназначенная для создания визуализаторов данных.
Система визуализации программ система визуализации алгоритмов, предназначенная для создания визуализаторов программ.
Интересное состояние управляющее состояние программы, отображаемое пользователю.
Состояние алгоритма вычислительное состояние алгоритма включает в себя значения всех переменных.
Части визуализатора
Визуальное представление часть визуализатора, определяющая, что и как будет отображаться пользователю на различных стадиях визуализации.
Интерфейс визуализатора часть визуализатора определяющая, каким образом остальные части визуализатора отображаются на экране и I взаимодействие пользователя с элементами управления.
Логика визуализатора часть визуализатора, обеспечивающая трассировку алгоритма и предоставляющая данные другим частям визуализатора для отображения их пользователю.
Модель данных часть визуализатора, хранящая значения переменных, используемых в программе, и предоставляющая к ним доступ другим частям визуализатора.
Набор комментариев часть визуализатора, определяющая какие комментарии будут отображаться пользователю в каждом интересном состоянии.
Проектная документация часть проекта визуализатора, содержащая информацию обо всех стадиях разработки визуализатора и описывающая получившийся продукт.
Элементы управления часть визуализатора, при помощи которой пользователь управляет визуализатором.
Программы
Итеративная программа программа без рекурсии.
Рекурсивная программа программа, использующая рекурсию.
Приведенная форма программы программа, записанная в форме, содержащей только операторы присваивания, блочные, цикла с предусловием, ветвления и вызова процедур.
Приведение программы преобразование программы в приведенную
Явная рекурсия рекурсивная процедура непосредственно содержит вызов самой себя.
Косвенная рекурсия рекурсивная процедура может осуществлять вызов самой себя посредством других процедур.
Построение модели данных создание модели данных по программе и модификация программы к виду, использующему модель данных.
Автоматы
Управляющее состояние состояние, управляющего автомата непосредственно влияет на выполняемые переходы.
Вычислительное состояние состояние управляемого объекта влияет на исполняемые переходы только косвенно.
Прямой автомат автомат, осуществляющий трассировку программы в прямом направлении.
Обратный автомат автомат, осуществляющий трассировку программы в обратном направлении.
Пара автоматов прямой и обратный автоматы, построенные по одной процедуре и имеющие общие состояния.
Фрагмент автомата набор состояний и переходов, при этом начальные иили конечные состояния переходов могут быть не определены.
Вход фрагмента автомата переход, у которого не определено начальное состояние.
Выход фрагмента автомата переход, у которого не определено конечное состояние.
Замыкание объединение входа фрагмента автомата с выходом другого фрагмента автомата в один переход.
Прочие термины
Визуализируемая программа конкретная реализация алгоритма, на основе которой строится визуализатор.
Визуализируемый алгоритм алгоритм, который поясняет визуализатор.
Описание визуализатора запись информации о визуализаторе для последующей автоматизированной обработки.
Описание визуализируемой программы запись визуализируемой программы для последующей автоматизированной обработки.
ВВЕДЕНИЕ
Актуальность


Разработка технологии объектноориентированного программирования с явным выделением состояний, выполняемой по гранту РФФИ 1 по государственному контракту Технология автоматного программирования применение и инструментальные средства, выполняемому в рамках ФЦНТП Исследования и разработки по приоритетным направлениям развития науки и техники на годы. Апробация результатов работы. Основные положения диссертационной работы докладывались на Второй Всероссийской научной конференции Методы и средства обработки информации Москва, МГУ, г. II и III конференции молодых ученых СПбГУ ИТМО СанктПетербург, , гг. Политехническом симпозиуме Молодые ученые промышленности СевероЗападного региона СанктПетербургский государственный политехнический университет, г. Москва, г. Телематика, Телематика СанктПетербург XXXV научной и учебнометодической конференция СПбГУ ИТМО Достижения ученых, аспирантов и студентов СПбГУИТМО в науке и образовании СанктПетербург, г. Публикации. По теме диссертации опубликовано печатных работ, в том числе в Научнотехническом вестнике СПбГУ ИТМО входит в Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации сборниках трудов конференций Методы и средства обработки информации, Телематика, Межвузовская конференция молодых учных, Политехнического симпозиума Молодые ученые промышленности СевероЗападного региона журналах Телекоммуникации и информатизация образования, Компьютерные инструменты в образовании. Структура диссертации. И страницах. Список литературы содержит 3 наименования. Работа иллюстрирована рисунками и содержит таблиц. Глава 1 содержит описание текущего состояния в области создания и применения визуализаторов и систем визуализации. В частности, рассмотрено применение визуализаторов в учебном процессе и предъявляемые к ним требования. В этой главе также приводится анализ существующих визуализаторов алгоритмов и систем визуализации с точки зрения выдвинутых требований и показывается, что они им не удовлетворяют. Таким образом, обосновывается необходимость разработки новой системы визуализации. В главе 2 предлагается процесс построения визуализаторов алгоритмов, и рассматриваются пути его автоматизации. Вначале выделяется структура визуализатора основные части и связь между ними. Далее анализируются подходы к построению основных частей визуализатора, и обосновывается необходимость автоматизации их построения. В частности, рассматривается автоматный подход к построению логики визуализаторов алгоритмов. В конце главы формулируются задачи, решаемые в диссертационной работе. В главе 3 рассматриваются преобразования, позволяющие упростить дальнейшее преобразование программы в систему взаимодействующих конечных автоматов. В начале предлагается метод построения модели данных по программе, что позволяет разделить вычислительные и управляющие состояния. Затем рассматривается преобразование программы к приведенной форме, что позволяет далее рассматривать только программы, записанные в ней. В гчаве4 предлагаются методы преобразования программ в систему взаимодействующих автоматов. При этом рассматриваются как неформальные, так и формальные методы преобразования. В начале главы разрабатывается метод построения системы взаимодействующих конечных автоматов, позволяющей исполнять программу в прямом направлении. В заключение для предложенных методов доказана корректность и другие свойства. В главе 5 предлагается язык описания визуализаторов, основанный на X. При этом отдельно рассматриваются структуры описаний визуализируемого алгоритма и конфигурации визуализатора. В главе 6 описываются результаты внедрения разработанных методов. В начале рассматривается система визуализации Vii, построенная на основе методов и подходов, разработанных в предыдущих главах. Далее приводится пример построения визуализатора на основе системы Vii. Затем производится сравнение полученных результатов с существующими подходами и приводится информация о практическом внедрении системы Vii и визуализаторов, построенных на ее основе.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.321, запросов: 244