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

Введение.

Глава 1. Основные теоретические предпосылки и анализ существующего состояния.

1.1. Алгоритмические сети: основные определения.

1.1.1. Аналитическое и графическое представления алгоритмической сети.

1.1.2. Основные проблемы разработки системы автоматизации на основе алгоритмических сетей.

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

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

1.2.2. 20-Sim.

1.2.3. VisSim.

1.2.4. Simulink.

1.2.5. Существующие системы автоматизации на основе алгоритмических сетей.

1.2.6. Заключительные замечания по средствам визуального моделирования.

Выводы по первой главе.

Глава 2. Методы графического представления моделей на основе алгоритмических сетей и их алгоритмизация.

2.1. Развитие языка моделирования

2.1.1. Отказ от фиксированного базиса операторов.

2.1.2. Возможность обращения к другой модели, считаемой со своим шагом расчета.

2.1.3. Ввод новых типов переменных.

2.2. Технология создания алгоритмической сети при графическом вводе

2.2.1. Объекты, описывающие графическое представление алгоритмической сети.

2.2.2. Графический ввод алгоритмической сети.

2.2.3. Блочно-фрагментарная и шаблонная технологии ввода алгоритмических сетей.

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. Алгоритмы поиска контуров в алгоритмической сети.

Выводы по второй главе

Глава 3. Реализация методов графического представления моделей на основе алгоритмических сетей в системе КОГНИТРОН.

3.1. Краткий обзор особенностей системы.

3.2. Настроечный файл системы.

3.3. Ввод модели в графическом редакторе.

3.3.1. Ввод операторов алгоритмической сети.

3.3.2. Изменение атрибутов графических элементов.

3.3.3. Удаление графических элементов.

3.3.4. Синтаксическая проверка.

3.3.5. Задание общих свойств и сохранение модели.

3.3.6. Дополнительные возможности и пример построения модели.

3.3.7. Пример построения блочно-фрагментарной модели.

3.3.8. Операции по работе с буфером обмена.

3.4. Формат хранения модели в системе.

3.5. Сравнение функциональных возможностей подсистемы построения моделей с предыдущей версией.

3.5.1. Общие свойства системы.

3.5.2. Ввод модели в графическом редакторе.

3.5.3. Ввод модели в редакторе повершинного ввода.

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

Выводы по третьей главе

Глава 4. Примеры моделей, реализованных в системе КОГНИТРОН

4.1. Модель решения системы линейных уравнений методом Гаусса

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

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

4.2.2. Описание блок-схемы модели.

4.2.3. Описание типового блока жизненного цикла вооружений и военной техники.

4.2.4. Блок ремонтных мощностей.

4.2.5. Результаты модельных экспериментов.

4.2.6. Общие замечания по созданию модели в системе моделирования

Выводы по четвертой главе.

Актуальность работы:

Проблема снижения барьера между пользователем и ЭВМ появилась сразу же, как появилась ЭВМ и остается актуальной и в настоящее время. Эта проблема формулируется также как задача разработки дружественного интерфейса.

Одним из возможных путей решения проблемы является использование графического представления, поскольку оно отличается наглядностью, позволяет, в ряде случаев, снизить требования к подготовке пользователей и реально уменьшить барьер между человеком и ЭВМ. Разрабатывались и разрабатываются все новые средства графического представления алгоритмов, программных спецификаций, моделей. Здесь уместно перечислить такие средства как сети Петри, семантические сети, граф-схемы алгоритмов, информационные графы, сети ограничений, case-технологии и язык UML. В этом ряду стоит и формализм алгоритмических сетей (АС), предназначенный для описания алгоритмических моделей.

АС и алгоритмическое моделирование развиваются в СПИИРАН начиная с 1980 года. Первая версия системы автоматизации моделирования на основе АС появилась в 1982 году и с тех пор регулярно обновляется со сменой аппаратных и программных платформ, развиваясь в сторону уменьшения требований к математической и компьютерной подготовке пользователей системы. С использованием системы автоматизации на основе АС было разработано и внедрено более 100 моделей в экономике, технике, экологии. Модели эти в свое время практически использовались в Госплане РФ, край и облпланах, вузах, промышленных предприятиях, Министерстве обороны РФ. Использование системы автоматизации моделирования позволяет уменьшить затраты на разработку модели как минимум на порядок.

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

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

Цели и задачи диссертации:

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

1. Расширение функциональных возможностей формализма АС.

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

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

4. Разработка алгоритмов синтаксического контроля, реализующих предложенную систему правил.

Объект и предмет исследования:

Объектом исследования данной работы являются модели на основе алгоритмических сетей. Предметом исследования являются методы графического представления моделей на основе алгоритмических сетей.

Методы исследования:

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

Научная новизна:

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

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

3. Разработанная система правил проверки допустимости графического представления АС независима от состава операторов. Сформулирована и доказана теорема о корректности предложенной системы правил.

Практическая значимость: 1. В новой версии системы автоматизации моделирования КОГНИТРОН реализовано расширение функциональных возможностей формализма АС, блочно-фрагментарной технологии формирования АС и системы правил допустимости графического представления АС. В систему были заложены разработанные алгоритмы синтаксического контроля. Новая система позволила существенно снизить трудоемкость создания моделей на основе АС и может применяться для решения более широкого класса задач.

2. С использованием системы КОГНИТРОН решен ряд практических задач по разработке моделей:

- Модели изменения состояния вооружений и военной техники для Министерства обороны РФ. Применение системы позволило на порядок сократить трудоемкость разработки и модификации моделей, рассмотреть более десятка вариантов структуры моделей.

- Моделирование процесса размещения пунктов сбыта для ЗАО "Экогазсервис"

Результаты работы внедрены

- в министерстве обороны РФ (система КОГНИТРОН)

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

Апробация работы:

Основные результаты исследований по теме диссертации докладывались на:

- VI Санкт-Петербургской Международной Конференции "Региональная информатика - 98"

- Двенадцатой международной конференции «Математические методы в технике и технологиях ММТТ - 12», Новгород. 1999

- VII Санкт-Петербургской Международной Конференции "Региональная информатика - 2000"

- Конференции "Amazing World of Science" (С.-Петербург, кафедра иностранных языков РАН, 2000)

Публикации:

По теме диссертационной работы опубликовано 6 печатных трудов.

Структура и объем работы:

Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы и приложения. Объем основного текста диссертационной работы: 159 страниц, 62 рисунка и 13 таблиц. Список литературы включает 39 наименований. Объем приложения составляет 3 страницы.

Выводы по четвертой главе

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

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

Заключение

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

- более мощным языком моделирования

- удобной технологией построения моделей

- удобным и полным графическим синтаксисом

- развитым графическим интерфейсом, включающим в себя графический редактор для редактирования графического представления АС

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

- способностью работать под управлением наиболее популярных операционных систем

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

- развитие языка моделирования (отказ от фиксированного базиса, достижение алгоритмической полноты, ввод новых типов переменных)

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

- независимую от состава операторов систему правил проверки допустимости графического представления АС

- алгоритмы синтаксического контроля, реализующие предложенную систему правил

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

- для модификации операторного базиса система использует настроечный файл

- в системе заложена возможность обращения к другой модели, считаемой со своим шагом расчета

- ввод новых типов переменных

- заложена измененная технология моделирования, объединяющая ввод фрагментарных и блочных моделей

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

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

- система является многоплатформенной на уровне исходного кода

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

К основным результатам диссертационной работы относятся:

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

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

154

3. Разработана независимая от состава операторов система правил проверки допустимости графического представления АС. Сформулирована и доказана теорема о корректности предложенной системы правил.

4. Разработаны алгоритмы синтаксического контроля, реализующие предложенную систему правил.

5. Осуществлена программная реализация разработанных методов в рамках системы моделирования КОГНИТРОН.

6. С помощью системы КОГНИТРОН решен ряд практических задач по разработке моделей, часть которых создавалась при непосредственном участии диссертанта, а именно:

- Модели изменения состояния вооружений и военной техники для Министерства обороны РФ

- Моделирование процесса размещения пунктов сбыта для ЗАО "Экогазсервис"

Система КОГНИТРОН внедрена в ряде организаций.

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

1. Пономарев В.М. Алгоритмические модели в задачах исследования систем. // Алгоритмы и системы автоматизации исследований и проектирования. М.: Наука, 1980, с.4-8.

2. Пономарев В.М., Александров В.В. Алгоритмические модели как средство автоматизации исследований. // Автоматизация исследований и проектирования. М.: 1978, с.5-8.

3. Иванищев В.В. Алгоритмический базис для описания механизмов экономики. // Алгоритмические модели в автоматизации исследований. М.: Наука, 1980, с.37-42.

4. Иванищев В.В. Автоматизация моделирования потоковых систем. Д.: Наука, 1986, 142с.

5. Марлей В.Е. Моделирование сложных систем на основе распределенных алгоритмических сетей. Диссертация на соискание ученой степени доктора технических наук, 1998.

6. Иванищев В.В., Марлей В.Е., Морозов В.П. Язык алгоритмических сетей: Препринт №63 ЛНИВЦ АН СССР. Л.,1984. 37с.

7. Иванищев В.В., Марлей В.Е., Морозов В.П. Система автоматизации моделирования САПФИР-ИСКРА. Основы построения системы: Препринт №99 ЛИИАН. Л, 1989. 63с.

8. Иванищев В.В. Об одной модели региона. // Алгоритмы и системы автоматизации исследований и проектирования. М.: Наука, 1980, с. 13-16.

9. Иванищев В.В. Система автоматизации представления проблемной области, формирования программ и решений (САПФИР). Л.: ЛНИВЦ АН СССР, 1982, 26с.

10. Ю.Иванищев В.В., Игнашкина Е.М., Марлей В.Е., Пономарев В.В. Укрупненная алгоритмическая потоковая модель региона. Л.: ЛНИВЦ АН СССР, 1981,48с.

11. П.Иванищев В.В., Мовчан B.C., Пономарев В.В. Структура алгоритмического описания отраслей непроизводственной сферы региона. // Алгоритмические модели в автоматизации исследований. М.: Наука, 1980, с.46-51.

12. Морозов В.П., Федоров В.П. Укрупненная алгоритмическая модель "автомобильный транспорт" региона. // Вычислительные системы и методы автоматизации исследований и управления. М.: Наука, 1982, с.14-19.

13. Иванищев В.В. Об автоматизации построения алгоритмических граф-моделей. // Информационно-вычислительные проблемы автоматизации научных исследований. М.: Наука, 1983, с.5-9.

14. Тубольцева В.В. Система автоматизации моделирования экологических объектов ЭКО-САПФИР. // Проблемы обработки информации и интегральной автоматизации производства. Л.: Наука ЛО, 1986, с. 102-110.

15. Михайлов В.В. Блок настройки параметров в системе ЭКО-САПФИР. // Проблемы обработки информации и интегральной автоматизации производства. Л.:Наука ЛО, 1986, с. 111-118.

16. Иваншцев В.В., Михайлов В.В., Тубольцева В.В., Флегонтов А.В., Абакумов А.В. и др. Имитационное моделирование природной системы "озеро-водосбор". Л.: ЛИИАН, 1987, 232с.

17. Михайлов В.В., Тубольцева В.В. Особенности системы автоматизации Экологического моделирования. // Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с 26-31.

18. Егоров М.Б., Каширская Е.В. Программное обеспечение системы автоматизации САПФИР-РС. // Вопросы алгоритмического моделирования сложных систем. Л.: ЛИИАН, 1989, с 97-113.

19. Быков Я. А. Система автоматизации моделирования на основе визуализированного представления моделей в формализме алгоритмических сетей. Диссертация на соискание ученой степени кандидата технических наук, 2001.

20. Янив Р.И. Организация вычислений на алгоритмических сетях. // Информационные технологии и интеллектуальные методы. Выпуск №3. -СПб.: СПИИРАН, 1999, с. 140-146.

21. Дал. У., Дейкстра Э., Хоар К. Структурное программирование. М.: Мир, 1976, 90с.

22. Королев О.Ф. Синтаксис графического построения алгоритмических сетей. // Информационные технологии и интеллектуальные методы. Выпуск №3. -СПб.: СПИИРАН, 1999, с.112-131.

23. Иванищев В.В. Технология множественного моделирования на основе формализма алгоритмических сетей.-В кн.: Сборник научных трудов КИИ-96 в трех томах. Том III. Казань, 1996

24. Иванищев В.В., Михайлов В.В. Проблемы объединения фрагментарных моделей. V Санкт-Петербургская международная конференция "Региональная информатика-96". Тезисы докладов. Санкт-Петербург, 1996.

25. Морозов В.П. Алгоритмы синтаксического контроля при автоматической генерации программ в системе САПФИР Искра.87 // Методы и средства информационной технологии в науке и производстве. С.-Петербург: Наука, 1992. С.114-130.

26. Королев О.Ф. Алгоритмы поиска контуров в алгоритмической сети. // Информационные технологии и интеллектуальные методы. Выпуск №3. -СПб.: СПИИРАН, 1999, с.147-156.

27. Stanislav Alekseev, Viacheslav Ivanischev, Oleg Korolev, Vladimir Marley, Roman Yaniv The system for automation modeling based on algorithmic nets.

28. Second International Conference ; Simulation, Gaming, Training and Business Process, Reengineering in Operations. Riga, Latvia, September 8-9, 2000, pg. 359.

29. Королев О.Ф. Microsoft Excel: средство представления алгоритмических сетей. // Информационные технологии и интеллектуальные методы. Выпуск №2. СПб.: СПИИРАН, 1997, с.190-193.

30. Иванищев В.В., Марлей В.Е., Тубольцева В.В., Нехорошкин Н.И., Радчинский М.А., Таранцев А.А. Моделирование процессов обеспечения требуемой готовности техники. Пожаровзрывобезопасность. №3, 2002, стр.42-47.