Разработка методов проектирования и реализации поведения программных систем на основе автоматного подхода

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ОБЗОР МЕТОДОВ, ПАТТЕРНОВ И ЯЗЫКОВ, ПРИМЕНЯЮЩИХСЯ ДЛЯ ОПИСАНИЯ ПОВЕДЕНИЯ ПРОГРАММ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ

1.1. Методы преобразования процедурных программ в автоматные

1.2. Паттерны проектирования. Паттерн

1.3. Графический язык описаний и спецификаций

1.4. Унифицированный язык моделирования V

1.5. Язык .
1.6. Ixii.
Выводы.

ГЛАВА 2. ПРИМЕНЕНИЕ КОНЕЧНЫХ АВТОМАТОВ ДЛЯ РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ.

2.1. Задача о Ханойских башнях.
2.1.1. Классическое рекурсивное решение задачи
2.1.2. Обход дерева действий
2.1.3. Непосредственное перекладывание дисков.
2. Задача о ходе коня
2.2.1. Методы оптимизации.
2.2.2. Определение клеток, обход из которых невозможен
2.2.3. Выявление заблокированных клеток.
2.2.4. Применение правила Варнсдорфа
2.2.5. Использование различных массивов ходов коня
2.2.6. Итеративная программа
2.2.7. Рекурсивная программа
2.2.8. Автоматная программа.
2.3. Обход деревьев
2.3.1. Постановка задачи обхода двоичного дерева.
2.3.2. Описание структур данных для представления двоичных деревьев.
2.3.3. Ввод деревьев.
2.3.4. Обход двоичного дерева без использования стека
2.3.5. Обход двоичного дерева с использованием стека.
2.3.6. Обход винного дерева без использования стека
2.4. Реализация рекурсивных алгоритмов на основе
автоматного подхода
2.4.1. Введение
2.4.2. Изложение метода
2.4.3. Факториал.
2.4.4. Числа Фибоначчи.
2.4.5. Задача о ханойских башнях.
2.4.6. Задача о ранце
Выводы.
ГЛАВА 3. ПАТТЕРН ПРОЕКТИРОВАНИЯ I.
3.1. Описание паттерна.
3.1.1. Назначение
3.1.2. Мотивация.
3.1.3. Применимость
3.1.4. Структура.
3.1.5. Участники.
3.1.6. Отношения.
3.1.7. Результаты
3.1.8. Реализация.
3.1.9. Пример кода
3.2. Повторное использование классов состояний
3.2.1. Расширение интерфейса автомата.
3.2.2. Расширение логики введением новых состояний
ГЛАВА 4. ЯЗЫК ПРОГРАММИРОВАНИЯ I.
4.1. Особенности языка i
4.2. Пример использования языка i.
4.2.1. Описание примера.
4.2.2. Описание состояний.
4.2.3. Описание автомата
4.2.4. Компиляция примера.
4.3. Грамматика описания автоматов и состояний
4.3.1. Грамматика описания состояния
4.3.2. Грамматика описания автомата.
4.4. Повторное использование
4.4.1. Допустимые способы повторного использования.
4.4.2. Описание примеров
4.4.3. Наследование состояний.
4.4.4. Использование одного состояния в различных автоматах.
4.5. Реализация препроцессора.
4.5.1. Генерация Уашклассов по описанию состояний
4.5.2. Генерация Латклассов по описанию автоматов
Выводы.
ГЛАВА 5. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ
5.1. Область внедрения
5.1.1. Система vi .
5.1.2. База данных СУДС.
5.2. Постановка задачи
5.3. Применение паттерна i для проектирования класса
5.3.1. Формализация постановки задачи.
5.3.2. Проектирование автомата
5.3.3. Диаграмма классов реализации автомата
5.3.4. Реализация контекста автомата
5.3.5. Пример реализации класса состояния автомата
5.4. Приложение, визуализирующее работу класса

5.5. Сравнение реализации класса на основе паттерна i и традиционного подхода
5.6. Сравнение реализации класса на основе паттерна i и Iтехнопогии
Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


В данной работке неоднократно будут применяться диаграммы классов на языке UML. Недостатки языка UML применительно к теме настоящей работы (для описания поведения системы) состоят в том, что диаграммы переходов весьма громоздки, и их нельзя построить по коду программы. В настоящее время в компании Microsoft развивается язык AsmL (Abstract State Machine Language), предложенный Ю. Гуревичем []. Этот язык применим в ситуациях, когда необходимо точно специфицировать компьютерную систему в части ее функциональности. Менеджеры, разработчики и тестеры могут использовать язык AsmL для спецификации задач. В языке вводится понятие абстрактное состояние. При этом язык предоставляет возможность обеспечить компактное высокоуровневое описание состояния системы. Описание модели системы производится по шагам. Любое состояние машины может рассматриваться как словарь пар (имя, значение) переменных состояния. Прогон машины состоит из серии состояний и переходов. На рис. Рис. В настоящее время язык AsmL еще не получил достаточного распространения, особенно в сфере коммуникации. С года в России развивается SWITCH-технопогня, которая предназначена для проектирования программ на основе конечных автоматов. Качество программ, построенных с ее использованием достигается за счет выразительных средств графов переходов и изоморфного перехода от графов к программам. Эта технология успешно зарекомендовала себя при создании систем логического управления. С применением этой технологии студентами и аспирантами СПоГУ ИТМО было создано более пятидесяти проектов [] в самых разных областях разработки программного обеспечения. Это позволило рассмотреть технологию с самых разных сторон и проанализировать ее сильные и слабые стороны. Для 5Л7ГС#-технологии разработана графическая нотация для описания конечных автоматов. Для автоматизации построения диаграмм в этой нотации разработан инструмент проектирования Unimod [7], подключаемый к среде разработки Eclipse []. Отмстим, что SWITCH-технология обладает рядом недостатков. Монолитность — в отличие от реализации на основе паттерна State Machine невозможно повторно использовать составные части кода класса ThreadFactory. При необходимости добавления входных и (или) выходных воздействий могут возникать ситуации, при которых компилятор не сможет обнаружить некоторые семантические ошибки, такие как, например, несоответствие метода интерфейса класса с вызовом автомата с соответствующим событием. Из изложенного выше следует. В настоящее время отсутствует метод преобразования рекурсивных программ в автоматные, например, для языков, в которых нет рекурсии. В настоящее время среди паттернов проектирования для описания объектов с варьирующимся поведением используется паттерн State, обладающий рядом недостатков. Настоящая работа направлена на устранение недостатков во всех трех указанных направлениях. Глава 2. Одной из наиболее известных рекурсивных задач является задача о ханойских башнях [], которая формулируется следующим образом. Имеются три стержня, на первом из которых размещено N дисков. Задача состоит в определении последовательности перекладываний по одному диску со стержня на стержень, которые должны выполняться так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы, в конце концов, все диски оказались на другом стержне. В работах [, ] приведены примеры преобразований рекурсивных программ в итеративные, однако подходы, обеспечивающие такие преобразования, не формализованы. Настоящая работа призвана устранить этот пробел. В работе предлагаются три метода. Первый из них обеспечивает формальное построение автоматной программы (программы, построенной с использованием автоматов) на основе раскрытия рекурсии с применением стека. Второй метод также обеспечивает раскрытие рекурсии и состоит в построении автомата, осуществляющего обход дерева действий, выполняемых рекурсивной программой. Третий метод состоит в непосредственном управлении дисками и стержнями, и не использует таких абстракций как деревья и стеки.