автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Разработка моделей и методов синтеза модульной структуры автоматизированных информационных систем с использованием сетей Петри

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

Ищенко Михаил Алексеевич

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

05.25.05- информационные системы и процессы, правовые аспекты

информатики

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 О ДЕК 2009

Москва - 2009 г.

003487926

Работа выполнена в ГОУ ВПО «Российский государственный гуманитарный университет».

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

Косяченко Станислав Анатольевич

Официальные оппоненты доктор технических наук, профессор

Максимов Николай Вениаминович

кандидат технических наук Сергеев Станислав Алексеевич

Ведущая организация ГУ «Российский научно-исследовательский

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

Защита состоится «25» декабря 2009 г. в 14-00 часов на заседании диссертационного совета Д 212.198.02 при ГОУ ВПО «Российский государственный гуманитарный университет» по адресу: 125993, г. Москва, Миусская площадь, д.6

С диссертационной работой можно ознакомиться в библиотеке РГГУ по адресу: 125993 г.Москва, Миусская площадь, д.6

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

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

Меркулов В.Н.

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

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

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

систем, сократить сроки проектирования, отладки и внедрения систем в промышленную эксплуатацию на 20-30%, повысить качество проектных решений. Большие масштабы работ по созданию и внедрению АИС, а также недостаточная адекватность имеющихся моделей и методов формализации и автоматизации процесса разработки оптимальных модульных СОД, учитывающих расширенные возможности современных ЭВМ и их комплексов, обуславливают актуальность выполненных научных исследований.

Степень разработанности проблемы. Основы методологии синтеза структур автоматизированных информационных систем были заложены в работах ряда российских и зарубежных ученых: Котова В.Е., Питерсона. Дж., Кульбы В.В., Урбански Ф., Спиридонова A.M. и др.

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

Объект исследования - модульные структуры автоматизированных информационных систем.

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

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

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

разработка методов моделирования модульных АИС с использованием аппарат сетей Петри.

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

- разработка комбинаторных алгоритмов синтеза основанных на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов и схеме «ветвей границ».

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

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

На защиту выносятся следующие положения:

1. Методология анализа и синтеза оптимальных модульных АИС с использованием аппарата сетей Петри.

2. Модели, методы, алгоритмы и программы анализа и синтеза оптимальных модульных АИС по заданным критериям эффективности.

3. Формализованные критерии синтеза оптимальной структуры

модульных АИС: максимум информационной производительности системы,

5

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

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

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

6. Методы определения оптимального состава информационных массивов при заданном программном обеспечении АИС.

7. Методы и алгоритмы синтеза оптимальной функциональной модульной блок-схем обработки данных.

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

Внедрение. Эффективность разработанных в диссертационной работе

моделей, методов, алгоритмов и программ синтеза с использованием

аппарата сетей Петри модельных АИС подтверждена положительным опытов

их использования при проектировании ряда систем. При непосредственном

6

участии автора они внедрены при разработке АИС «ИНИОН АН РФ». Использование разработанных моделей и методов, алгоритмов и программ позволило сократить временные и стоимостные затраты на разработку и внедрение систем в среднем на 20-30% за счет оптимизации получаемых проектных решений.

Апробация работы. Основные результаты работы докладывались автором и обсуждались на международных конференциях: «Проблемы управления Безопасностью Сложных Систем», Москва 2006, 2007 гг., «Проблемы регионального и муниципального управления», Москва, 2009.

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

Публикации. По теме диссертации опубликованы 6 печатных работ, в том числе 2 в изданиях, перечень которых утвержден ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и включает 146 страниц машинописного текста, 25 рисунков и 9 таблиц.

II. Основное содержание работы

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

В первой главе проведены анализ и классификация различных

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

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

7

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

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

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

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

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

Сетью Петри называется четвёрка элементов: С = (Р,Т,1,0),

гдеР = { рьр2.....р„},п>0

множество позиций (конечное), Т={11,12,...,1га},т>0 множество переходов (конечное), I: Т —> Р

функция входов (отображение множества переходов во входные позиции),

О: Т Р

функция выходов (отображение множества переходов в выходные позиции).

Если Р1 ^ I , то р1 - входная позиция 3 - го перехода, если р( е I то - выходная позиция 3 - го перехода.

Для наглядного представления сетей Петри используются графы. Граф сети Петри есть двудольный ориентированный мультиграф: 0 = (У,Е),

где V = Р и Т, причём Р Л Т = 0.

Исходя из графического представления сети Петри, её можно определить и так: С = (Р,Т,А),

где А - матрица инцидентности графа сети.

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

Маркировка ц сети Петри С = (Р, Т, I, О) есть функция: N = |д(Р), N е Ы,

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

где п = | Р |, а е N. Между этими определениями есть связь:

И; = ^ (РО

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

Таким образом, маркированная сеть Петри представляет собой пятёрку элементов:

М = (Р,Т,1,0, ц).

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

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

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

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

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

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

При решении практических задач часто необходимо совместное рассмотрение различных характеристик исследуемых объектов. Рассмотрим обобщенную сеть Петри (ОбСП) и дадим ее определение.

Обобщенная сеть Петри определяется как упорядоченный набор вида Мо6 =(Р,Т,0.,Г,Н,Х,Ч'А<?> Но), где Р = {р} - не пустое конечное множество позиций; Т = Г4 и Т - не пустое конечное множество переходов, которое разбивается на два непересекающихся подмножества: Т4 содержащее

простые переходы, и Т = содержащее составные переходы (агрегаты первого уровня), которые имеют сложную структуру и сами являются сетями Петри (возможно, обобщенными); П = {со}- конечное не пустое множество цветов маркеров; F:^, хТ -* N и Н:Т X Р -* N • функции инцидентности множеств позиций и переходов (И- множество целых натуральных чисел); Х:(Р х 0) х Т—*{1, 0} - функция распределения цветов маркеров по входным позициям переходов сети; ц>:Т х (Р х 0) —* Р х Л - функция распределения цветов маркеров по выходным позициям переходов сети; в: Ь(1V) —► - функция, отображающая множество слов свободного языка сети Петри во множество неотрицательных вещественных чисел; 0(1): (I 6 Ь(Ы)) - минимальное время, за которое данное слово может быть получено в сети Ыо6; <р: Ь(АГ) —> й+ - функция, отображающая множество слов свободного языка ЦЫ) в = {[а\, а"]: а\, а" 6 6 Ы} множество отрезков с концами из Значение ср(1) определяет

набор отрезков [(р\(1). <р\1(1)], -[<Рк(?)> ФкО)] таких, что слово 1 может быть получено только в течение промежутков времени Ш), ф"(07 = [а\, а]1], <р%(1)]= [а[, аЦ]; 3?- вероятностная

мера, заданная на множестве всех подмножеств достижимых маркировок 2ят, (т.е. 9} # 2т ->/0, !])■ ¡л0: Р хС1—> Ы,2т = {$}, Д с ЩЫ)

И

начальная маркировка сети, задаваемая матрицей размера |(2|х|Р|, проиндексированной по строкам множеством цветов маркеров, а по столбцам множеством позиций сети.

Обобщенная сеть Петри является наиболее общей моделью и содержит (в зависимости от наличия в описываемом ее наборе тех или иных элементов) различные подклассы СП. Можно выделить тридцать два подкласса обобщенных сетей Петри.

При исследовании объектов, описанных на языке сетей Петри возможны случаи, когда объект моделируется СП одного из подклассов, а при решении некоторых частных задач анализа системы ряд характеристик не требуется, что затрудняет анализ сети. Поэтому полезным является понятие проекции сети класса ДО,- на класс Nj (1,7 е 0,31). Проекция определена, если набор, описывающий СП из класса включает в себя элементы набора сети класса ДО,-.

Проекцией Пр^. сети Петри класса ДО,- на класс ДОу назовем сеть Петри из класса Л/,-, в которой соответствующие элементы совпадают с элементами исходной сети либо определяются по заданным правилам, описание которых приведено ниже.

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

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

определяются множеством информационных элементов

£> = и множеством процедур их обработки Л =

{а1,а2,...,аг, - .ад}.

Используемые в настоящее время традиционные модели АИС (сетевые, графовые модели, и др.) не полностью учитывают перечисленные выше характерные особенности современных ЭВМ и систем обработки данных. Для учета этих особенностей при моделировании АИС предлагается использовать сети Петри, позволяющие адекватно описывать дискретные процессы обработки данных на современных ЭВМ или в сетях ЭВМ. Представим процесс функционирования АИС с помощью сети Петри, определенной набором N = {Р, Т, Н, М0}. Поставим в соответствие каждому элементу 6 вершину-состояние р1 сети Петри, а процедуре обработки данных аг £ А вершину-переход 6 Т. В соответствии с матрицей взаимосвязи процедур и информационных элементов соединяем дугами элементы множеств Р и Т. Поскольку информационный элемент СОД может являться входным для нескольких процедур обработки данных, то для восстановления маркерных точек состояния р( соединим его с такими переходами £г, для которых существуют дуги (р(, Пометим маркерными точками все состояния сети Петри, соответствующие входным информационным элементам СОД. Тогда Ь - мерный вектор М0, координаты которого равны числу маркерных точек в соответствующих состояниях, будет определять начальную разметку сети Петри, моделирующую заданную систему обработки данных.

На элементах сети Петри введены теоретико-множественные операции, необходимые для выделения множеств элементов сети, обладающих заданными свойствами:

1) Л(Р) = М- Этакие,чтоН(^р)(1 - ^'(р.О) = 1

2) ЛСО = {р}~ V такие, что ^(р, 0 = 1

3) f(p) = - {такие,чтоР(р,0 = 1

4) f{t) = {p}~ p такие, что H(t, p)( 1 - F(p, t)) = 1

5) h.(N,P) = {p} - p такие,что p ё liter/(О

6) T) = {t}~ t такие, что h(t) с h(N, P)

7) f(N,P) = {p} — p такие, что /(p) 0

8) /(tf.r) = {t} - такие, что f(t) П f(N, P) * 0

Операции 1 и 3 выделяют входные и выходные переходы для заданного состояния р. Операции 2 и 4 выделяют входные и выходные состояния для заданного перехода t. Операции 5 и 7 выделяют входные и выходные состояния сети Петри, операции 6 и 8 соответствующие переходы. При этом h(t) соответствует множество входных информационных элементов процедуры обработки данных a, a fit) - множество выходных информационных элементов.

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

Фрагментом переходов Вк сети Петри N для заданного множества переходов Тк = (tkl,tkz, ...,tkm) назовем такую сеть Петри вк = (Л- Tkl Fk, Нк, Мок}, в которой

Fk(p,t)= F(P>О V t 6 Tk,Vp€ Pk\ Hk(p, t) = H(t,p) V t 6 7*. V p e Pk; Mofe(p)= M0(p)vpe Pk.

Заданное множество Tk переходов, позволяющее однозначно построить некоторый фрагмент переходов, назовем ядром фрагмента переходов. Аналогично вводятся понятия фрагмента состояний и ядра фрагмента состояний.

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

обработки данных в реальном масштабе времени, в том числе модульных АИС. Программному модулю АИС при этом соответствует ядро Вк фрагмента переходов Вк = {Рк, Тк, Fk, Нк, Мок), а внутренний и внешний интерфейс модуля Вк соответствует множеству

t6Tk

Внешним интерфейсом модуля Вк будет множество состояний K = h(BklPk)Uf(Bk,Pk).

Информационному массиву АИС соответствует ядро фрагмента состояний^ = (Pf,Tf,Ff,Hf,M0f).

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

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

Пусть система обработки данных S описана сетью Петри N, состоящей из L состояний и R переходов. В систему поступают запросы на выдачу содержания заданных наборов информационных

элементов (состоянии) 6а) (ш=1 ,W) с вероятностями qw. Каждый из наборов состояний вы может принимать некоторые значения с вероятностями = 1 ,nw). Вероятности запросов и вероятности их значений попарно несовместимы, независимы и образуют полные группы событий.

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

I Агде 0)

£¡0=1 Чш а<1

Но = Чт и Нш = -Е£?1<гГ1°82<7гУ соответственно энтропия

запросов и среднего количества информации, содержащегося в одном ответе на запрос. Вероятности и ц^ удовлетворяют ограничениям:

Л (2)

ч»=г>

Ш=1

•"Ш ¡=1

Vco = T/W

(3)

Если АИС работает в справочном режиме без оперативного обновления информации, то в этом случае Ны = 0 Veo = 1,W и функция (1) примет вид:

; _ -Sa=l<7(.)log2<?co s Yw а а

¿"ÜJ = 1 4t¡) "й>

Исследованы зависимости информационной производительности от вероятностей запросов наборов информационных элементов. Показано, что информационная производительность системы обработки данных при заданном времени формирования наборов информационных элементов принимает свое максимальное значение, если вероятное™ их запросов определены следующим образом: qM = lfm2Ha,V(a =1 ,W, где £ находится из уравнения: = i.

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

С использованием критерия максимума информационной производительности поставлена и решена задача синтеза оптимальной модульной блок-схемы обработки данных (критерий 1). Для решения данной задачи разработан комбинаторный алгоритм, основанный на методе локальной оптимизации. Показано, что разработанный алгоритм является сходящимся. Рассмотрена также задача синтеза структуры программного обеспечения оптимальных модульных АИС по критерию максимума их информационной производительности. Поставленная задача является задачей математического программирования. Алгоритм ее решения основан на методе последовательного построения, анализа и отбора вариантов. В процессе конструирования программных модулей определяется последовательность их выполнения, а также последовательность выполнения процедур обработки данных. Для сокращения числа рассматриваемых вариантов (в среднем на 10-30%) доказано следующее утверждение, основанное на особенностях модульных АИС и свойствах сетей Петри, описывающих данную СОД:

Утверждение 1. Пусть имеется последовательность выполнения и состав допустимых фрагментов п = (В1,В2,-"Вк,--ш ,Bk+i, •••,ВК). Переход Тг 6 Tk+i является таким, что

1) h (tr) с h (N, Р) U h(BK Pk ) U (Utr„er*/(V')),

2) Э tr,eTk и Эре f(tr,) такие, что F (р, tr) = 1,

4)

где

г

Ур.еАС^^^г^Х),

/=1 р

/=1

к г

г'=1 /= 1

( 1 - если 6 Вк, Хгк ~ (О - в противном случае;

II - если переход срабатывает- м в последовательности,/' = 1,Д, О - впротивном случае;

_ ( 1 - если Рг еЛр — (0 — в противном случае;

я

^с _ 11 - если ^ «I/ 2 {г) > О,

1 = 1 г—1

О-в противном случае;

и п.

1 - если £ г,, 2 ХткНОг, р,) (1 - ^(рг;г)) > О,

{=1 Г=1

О-в противном случае;

_ Г 1 - если г;^ + > О, О-в противном случае;

8Г- объем оперативной памяти, занимаемый -ой процедурой; Мг - ограничение на объем фрагментов переходов. В этих условиях последовательность фрагментов переходов п' = (В1,В2, —^'к,-1 является оптимальной, если оптимальна

последовательность л. Здесь Т'к — Тк II Т'к+1 = Т^+Д^.

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

£/тт = тах^Д-Ер!1!^- - 1)}, где - количество

состояний во фрагменте состояний Ар, М5 - ограничение на число фрагментов состояний.

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

В заключение главы рассматривается пример использования разработанных моделей и методов синтеза оптимальных модульных СОД.

В четвертой главе рассматриваются вопросы модульного построения обработки данных, функционирующих в справочном режиме. В системах такого класса запрашивается, как правило, набор информационных элементов, содержащий в совокупности все выходные состояния системы. В этом случае IV = 1,= {/(Л/, Р)} и <?1 = 1. Для того, чтобы максимизировать информационную производительность таких систем, необходимо минимизировать время получения всех выходных информационных элементов, которые в основном определяются временем обмена программных модулей с внешней памятью ЭВМ.

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

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

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

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

Рассмотрим постановку и решение задачи синтеза состава модулей

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

заданном информационном обеспечении системы, которая является частной

20

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

Д-1 к к / я \

Я-1 К К / К \

Хср 2 X X хгкУг> (1 ~ 2 хг'кУг,]+1}

]=1г=1к=1 \ п=1 '

при ограничениях (2), (3) и дополнительных ограничениях:

• число переходов в каждом фрагменте переходов не более заданного;

Л __(5)

^Хгк^Мв, к = 1,К ,

Г=1

• интерфейс между отдельным модулем и системой не более заданного:

Л __(6)

^ \РкПРк,\<М9, к = 1,К . к'=1

• межмодульный интерфейс системы ограничен: к (7)

^ £ \РкПРк.\<М10,

к=1 к'=к+1

где тср - среднее время обращения к заданным информационным массивам, размещенным во внешней памяти ЭВМ.

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

21

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

Утверждение. Пусть Вк и В'к - допустимые фрагменты переходов такие, что Т'к = ТкШга переход £> удовлетворяет следующим условиям:

а) /(*г) и с Рк

б)А(4г)сА(]У.Р)и(игет1к/(0.)

в)Л(«г)П(и46гкЯ0.)*0.

Тогда, если существует оптимальное множество фрагментов, содержащее фрагмент переходов Вк, то существует и оптимальное множество фрагментов, содержащих фрагмент переходов В'к.

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

Полученные в диссертационной работе результаты использования при проектировании АИС «ИНИОН АН РФ».

Основные результаты работы заключаются в следующем:

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

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

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

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

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

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

4. Решена задача определения множества наборов

вероятностей запросов, на котором значение информационной

производительности не менее заданного. Решение данной задачи

позволяет для каждой конкретной АИС определить изменение

23

информационной производительности при заданных изменениях вероятностей запросов.

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

• определение оптимального состава программных модулей при заданном информационном обеспечении АИС;

• определение оптимального состава системы информационных массивов при заданном программном обеспечении АИС;

• синтез оптимальной функциональной модульной блок-схемы обработки данных.

Для решения поставленных задач разработаны комбинаторные алгоритмы, основанные на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов и схеме «ветвей и границ».

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

7. Поставлены и решены задачи синтеза программных

модулей при заданном информационном обеспечении АИС по

критерию минимума общего времени обмена с внешней памятью и по

критерию минимума общего числа обращений к внешней памяти ЭВМ.

Данные задачи решены с использованием метода последовательного

построения, анализа и отбора вариантов. Сокращение числа

24

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

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

9. Полученные в работе модели и методы использовались при разработке АИС «ИНИОН АН РФ».

Основные положения диссертации отражены в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Ищенко М.А. Задача синтеза структуры автоматизированных информационных систем II Инженерная физика. №5; 2009.0,6 п.л.

2. Ищенко М.А. Постановка и решение задачи синтеза структуры оптимальных модульных автоматизированных информационных систем по критерию максимума информационной производительности // Приборы и Системы. Управление, Контроль, Диагностика. №5; 2009. 0,7 п.л.

Статьи и материалы конференций

3. Ищенко М.А. Синтез оптимальных модульных структур информационно-управляющих систем. Труды XIV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2006. 0,1 п.л.

4. Ищенко М.А. Применение сетей Петри для решения задач анализа и синтеза ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.0,1 п.л.

5. Ищенко М.А. Этапы эволюции индустрии разработки ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.0,1 п.л.

6. Ищенко М.А. Моделирование систем обработки данных с использованием сетей Петри. Сборник докладов международной научной конференции: Проблемы регионального и муниципального управления. Москва, 2009. 0,2 п.л.

Заказ № 296. Объем 1 п.л. Тираж 100 экз. Отпечатано в ООО «Петроруш». г.Москва, ул.Палиха 2а.тел.250-92-06 www.postator.ru

Введение.

Глава 1. Задачи анализа и синтеза автоматизированных информационных систем.

1.1. Технология проектирования автоматизированных информационных систем.

1.2. Формализованное описание сетей Петри. Основные понятия и определения.

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

Краткие выводы.

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

2.1. Использование сетей Петри для моделирования процессов в АИС.

2.2. Характеристики обобщенных сетей Петри.

2.3. Моделирование и анализ автоматизированных информационных систем с использованием сетей Петри.

Краткие выводы.

Глава 3. Синтез оптимальных модульных АИС по критерию максимума информационной производительности.

3.1. Определение информационной производительности автоматизированных информационных систем.

3.2. Анализ информационной производительности как целевой функции задач синтеза оптимальных модульных АИС.

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

3.4. Синтез оптимальной системы обработки данных для подсистем АИС «ИНИОН АН РФ».

Краткие выводы.

Глава 4. Синтез оптимальных модульных АИС по критерию минимума общего времени обмена с внешней памятью ЭВМ.

4.1. Синтез оптимального состава модулей программного обеспечения АИС.

4.2. Синтез оптимальной функциональной блок-схемы обработки данных и оптимального состава информационных массивов АИС.

4.3. Использование методов синтеза программного и информационного обеспечения оптимальных модульных АИС при проектировании задач АИС «ИНИОН АН РФ»

Краткие выводы.

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

Формализация моделей и разработка эффективных алгоритмов решения задач синтеза оптимальных модульных АИС на этапе технического проектирования позволяют автоматизировать процесс проектирования систем, сократить сроки проектирования, отладки и внедрения систем в промышленную эксплуатацию на 20-30%, повысить качество проектных решений. Большие масштабы работ по созданию и внедрению АИС, а также недостаточная адекватность имеющихся моделей и методов формализации и автоматизации процесса разработки оптимальных модульных СОД, учитывающих расширенные возможности современных ЭВМ и их комплексов, обуславливают актуальность выполненных научных исследований.

Степень разработанности проблемы. Основы методологии синтеза структур автоматизированных информационных систем были заложены в работах ряда российских и зарубежных ученых: Котова В.Е., Питерсона Дж., Кульбы В.В., Урбански Ф., Спиридонова A.M. и др.

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

Объект исследования - модульные структуры автоматизированных информационных систем.

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

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

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

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

- разработка комбинаторных алгоритмов синтеза основанных на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов и схеме «ветвей границ».

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

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

На защиту выносятся следующие положения:

1. Методология анализа и синтеза оптимальных модульных АИС с использованием аппарата сетей Петри.

2. Модели, методы, алгоритмы и программы анализа и синтеза оптимальных модульных АИС по заданным критериям эффективности.

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

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

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

6. Методы определения оптимального состава информационных массивов при заданном программном обеспечении АИС.

7. Методы и алгоритмы синтеза оптимальной функциональной модульной блок-схем обработки данных.

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

Внедрение. Эффективность разработанных в диссертационной работе моделей, методов, алгоритмов и программ синтеза с использованием аппарата сетей Петри модельных АИС подтверждена положительным опытов их использования при проектировании ряда систем. При непосредственном 5 участии автора они внедрены при разработке АИС «ИНИОН АН РФ». Использование разработанных моделей и методов, алгоритмов и программ позволило сократить временные и стоимостные затраты на разработку и внедрение систем в среднем на 20-30% за счет оптимизации получаемых проектных решений.

Апробация работы. Основные результаты работы докладывались автором и обсуждались на международных конференциях: «Проблемы управления Безопасностью Сложных Систем», Москва 2006, 2007 гг., «Проблемы регионального и муниципального управления», Москва, 2009.

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

Публикации. По теме диссертации опубликованы 6 печатных работ, в том числе 2 в изданиях, перечень которых утвержден ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и включает 146 страниц машинописного текста, 25 рисунков и 9 таблиц.

Заключение

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

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

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

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

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

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

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

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

• определение оптимального состава программных модулей при заданном информационном обеспечении АИС;

• определение оптимального состава системы информационных массивов при заданном программном обеспечении АИС;

• синтез оптимальной функциональной модульной блок-схемы обработки данных.

Для решения поставленных задач разработаны комбинаторные алгоритмы, основанные на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов и схеме «ветвей и границ».

6. Формализована и решена задача синтеза блок-схемы модульных АИС, функционирующих в справочном режиме по

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

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

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

9. Полученные в работе модели и методы использовались при разработке АИС «ИНИОН АН РФ».

1. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ.— М.: Мир, 984.— 264 с.

2. А.А. Лескин П.А. Мальцев A.M. Спиридонов. Сети Петри в моделировании и управлении. Наука, 1989, 133 с.

3. Бодянский Е.В., Кучеренко Е.И., Михалев А.И. Нейро-фаззи сети Петри в задачах моделирования сложных систем Монография (научное издание). Дншропетровськ: Системш технологи, 2005 г. 311 с.

4. Кельтон С., Лоу Дж. Имитацинное моделирование. Computer Science. СПб.: Питер, 2004

5. Котов В.Е. Сети Петри. М.: Наука 1984.

6. Ломазова И.А. Моделирование мультиагентных динамических систем вложенными сетями Петри. М.: Наука. Физматлит, 1999.

7. Воевода А.А., Саркенов Д.О. Сети Петри: симметричные графы состояний // Сб. науч. тр. НГТУ. 2005. - №3 (41). - С. 133-137.

8. Girault, С., Valk, R. Petri Nets for Systems Engineering: a Guide to Modeling, Verification, and Applications, Springer-Verlag, 2002. 607 p

9. Ищенко M.A. Задача синтеза структуры автоматизированных информационных систем // Инженерная физика. №5; 2009.

10. Ищенко М.А. Постановка и решение задачи синтеза структуры оптимальных модульных автоматизированных информационных систем по критерию максимума информационной производительности // Приборы и Системы. Управление, Контроль, Диагностика. №5; 2009.

11. Ищенко М.А. Синтез оптимальных модульных структур информационно-управляющих систем. Труды XIV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2006.

12. Ищенко М.А. Применение сетей Петри для решения задач анализа и синтеза ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.

13. Ищенко М.А. Этапы эволюции индустрии разработки ИУС. Труды XV Международной конференции: Проблемы управления Безопасностью Сложных Систем. Москва, 2007.

14. Ищенко М.А. Моделирование систем обработки данных с использованием сетей Петри. Сборник докладов международной научной конференции: Проблемы регионального и муниципального управления. Москва, 2009.

15. В.А. Башкин, И.А. Ломазова «Эквивалентность ресурсов в сетях Петри». М., Мир, 2008

16. Ломазова И.А. «Вложенные сети Петри: моделирование и анализ распределительных систем с объектной структурой.» М., мир 2004

17. Башин Ю.А., Митянов В.П. Моделирование SlMD-систем с использованием теории сетей Петри для оценки времени выполнения задачи с условием синхронной работы комплекса. — М.: ИПУ. — 2004. 39 с

18. Кулагин В.П. Анализ параллельных процессов на основе сетевых моделей: Учеб. Пособие. Пенза: ИЛИ. 1991

19. Чурина Т.Г. Способ построения раскрашенных сетей Петри, моделирующих SDL системы. - Новосибирск. - 1998. - 56 с.

20. Taubner D.A. The finite representation of abstract programs by automata and Petri nets: Diss. Dokt. Naturwiss. Univ. Munchen. Munchen. - 1988.

21. B.B. Кульба, Д.А. Миронов, Е.Б. Соколова. Отладка систем защиты с использованием сетей Петри. Препр. — М.: ИПУ. 1990. 49 с.

22. Вагнер Г. Основы исследования операций, т. 2, М.: Мир. - 443 с.

23. Котов В.Е. Алгебра регулярных сетей Петри. Новосибирск. 1978. - 38 с. - (Препринт / ВЦ СО АН СССР ; 98).

24. Кристофидес Н. Теория графов. М.: Мир, 1978. - 432 с.

25. Кульба В.В., Мамиконов А.Г. Методы анализа и синтеза оптимальных модульных систем обработки данных (обзор). Автоматика и телемеханика, 1980, № II с. 152-179.

26. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика. 1979. - 247 с

27. Мамиконов А.Г., Кульба В.В., Цвиркун А.Д. Автоматизация проектирования АСУ. — М.: Энергия. 1980. 328 с.

28. Хьюз Дж., Мичтон Дж. Структурный подход к программированию. М.: Мир, 1980.-278 с.

29. Boehm В. Soft engineering. IEEE Transactions on computers. December 1976, vol. c-25, #12, p. 1226-1241.

30. Devis A.L. The architecture and system method of DDM 1: a recursively structured data driven machine. SIGARCH NEWSLETTER, 1978, 6, #7, p. 210-215

31. Dijkstra E.W. The impact of microprocessors. GMD - Spiegel, 1977, v. 7, #4, p.8-11, 2.

32. Dolota T.A. Data processing in 1980-1985. Wiley-Interscience, N.Y., 1976.

33. Hach M. Analysis for Production Schemata by Petry Nets. Computer Structure Group. TR-94, Project MAC, M.I.T., February 1972 - 119 p.

34. Hamilton M., Zeldin S. Higher order software a methodology for defining software, IEEE Trans. Software Eng., Mar., 1976, p. 9-32

35. Langefors В., Sundgren B. Information system architecture. New York, Petrocelli / Charter, 1975

36. Martin W., Bosyj M. Requirement derivation in automatic programming in Proc. MPT Sump. Comput. Software Eng., Apr., 1976

37. Mc Gowan C.L., Kelly I.R. Top-Down Programming Techniques. New York, Petrocelli / Charter, 1975

38. Mills N.D. Mathematical found action for structured programming, IBM-ESD : rep. ES., p.72-6012, Feb 1972

39. Parnas D.L. The influence of software structure on reliability. Proc. Int. Conf. Reliable software, Apr. 1975, p.358-362.

40. Parnas D.L. On the criteria to be used in decomposing system into modules. GAGM, Dec. 1972, p. 1053-1058.

41. Peterson I.L. Petri-Nets. ACM Computing Surveys, v. 9, 3, September, 1977, p. 223-252

42. Petry C.A. Komminication mit Automater. Univ. Bonn, 1962

43. Riemann, Robert-Christoph (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag.

44. Storrle, Harald (2000). Models of Software Architecture Design and Analysis with UML and Petri-Nets. Books on Demand

45. Zhou, Mengchu; Frank Dicesare (1993). Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers.

46. Zhou, Mengchu; Kurapati Venkatesh (1998). Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific Publishing.

47. Desel, Jorg and Juhas, Gabriel " What Is a Petri Net? Informal Answers for the Informed ReaderHartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001.

48. AS) Decidability issues for Petri nets a survey, by Javier Esparza and Mogens Nielsen, in: Bulletin of the EATCS, 1994. Revised, 1995.

49. P. Kiingas. Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. In: Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation, SARA 2005, Airth Castle, Scotland, UK, July 26-29, 2005.

50. Petri Nets: Properties, Analysis and Applications, by Tadao Murata, in: Proceedings of the IEEE, vol. 77, no. 4, April 1989

51. T. Araki and T. Kasami, Some Decision Problems Related to the Reachability Problem for Petri Nets, in: Theoretical Computer Science, 3(1), pp. 85-104 (1977)

52. Dawis, E. P., J. F. Dawis, Wei-Pin Koo (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. Systems, Man, and Cybernetics,2001 IEEE International Conference on Volume 3, 2001 Page(s):1554 1558 vol.3

53. Jensen, Kurt (1997). Coloured Petri Nets. Springer Verlag.

54. Reisig, Wolfgang (1992). A Primer in Petri Net Design. Springer-Verlag.

55. Кузнецов H.A., Кульба B.B., Ковалевский С.С., Косяченко С.А. Методы анализа и синтеза модульных информационно-управляющих систем. — М.: ФИЗМАТЛИТ, 2002. 800 с.

56. Марка Д., Мак-Гоуэн К. Методология структурного анализа и проектирования. — М.: МетаТехнология, 1993.

57. Роберте Ф.С. Дискретные математические модели с приложением к социальным, биологическим и экономическим задачам. М.: Наука, 1986

58. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь. 1993.

59. Таль А.А., Юдицкий С.А. Иерархия и параллелизм в сетях Петри // Автоматика и телемеханика. 1982. — №7, 9

60. Трахтенгерц Э.А. Субъективность в компьютерной поддержке управленческих решений. М.: СИНТЕГ, 2001

61. Юдицкий С.А. Сценарно-целевой подход к системному анализу // Автоматика и телемеханика. — 2001. №4

62. Юдицкий С.А. Сценарный подход к моделированию поведения бизнес-систем. СИНТЕГ, 2001

63. Юдицкий С.А., Владиславлев П.Н. Предпроектное моделирование функционирования организационных систем. М.: Научтехлитиздат, 2004

64. Юдицкий С.А., Радченко Е.Г. Моделирование движения потоков при предпроектном анализе сложных систем // Приборы и системы: Управление, контроль, диагностика. 2003. - №9.

65. Юдицкий С.А., Радченко Е.Г. Построение потоковых моделей многоагентных иерархических систем // Приборы и системы: Управление, контроль, диагностика. 2004. - №2.

66. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами. -М.: Машиностроение, 1987.

67. Кононов Д.А., Кульба В.В., Ковалевский С.С., Косяченко С.А. Синтез формализованных сценариев и структурная устойчивость сложных систем (синергетика и аттрактивное поведение) / Институт проблем управления. Препринт - М., 1998

68. Кононов Д.А., Кульба В.В., Ковалевский С.С., Косяченко С.А. Формирование сценарных пространств и анализ динамики поведения социально-экономических систем / Институт проблем управления. -Препринт-М., 1999

69. Кульба В.В., Кононов Д.А., Ковалевский С.С., Косяченко С.А., Нижегородцев P.M., Чернов И.В. Сценарный анализ динамики поведения социально-экономических систем. М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН).