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

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

Давудпур Марьям

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2006 г.

Работа выполнена в Московском государственном техническом университете им. Н. Э. Баумана.

Научный руководитель: к.т.н., доцент Рудаков И.В.

Официальные оппоненты: д.т.н., проф. Черненький В.М.

к.т.н., доцент Козлов А.Д.

Ведущая организация: Центр исследований экстремальных

ситуатций (ЦИЭКС)

Защита состоится ^ » 9( 2006 года в ¡j' часов на заседании

диссертационного совета Д 212 141.15 при Московском государственном техническом университете им. Н.Э.Баумана по адресу: 105005, Москва, 2-я Бауманская улица, дом 5.

Отзыв на автореферат в двух экземплярах, заверенный печатью организации, просим выслать по адресу: 105005, Москва, 2-я Бауманская ул., дом 5, МГТУ им.Н.Э.Баумана, ученому секретарю диссертационного совета Д 212.141.15.

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н. Э. Баумана.

Автореферат разослан « J j » ^/¡/iJJa. L % 2006 г.

Ученый секретарь диссертационного совета, д.ф.-м.н., профессор

/

Волков И.К.

/орб А

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

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

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

Большинство современных методик исследования и анализа сложных дискретных структур (Баранов С.И., Норенков И.П., Черненький В.М., Емельянов C.B., Советов Б.Я., Яковлев С.А., М. Франк, А.Явор и др.) основываются на иерархических принципах, которые требуют обеспечения сквозного проектирования структур и возможности создания или использования эффективных средств анализа, ориентированных на соответствующие методы проектирования.

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

Для достижения поставленной цели в работе решены следующие основные задачи:

- выполнен анализ методов проектирования и формализации дискретных иерархических структур при исследовании соответствующего класса объектов;

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

дискретных структур и программного обеспечения таких методов;

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

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

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

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

Цель диссертации

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

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

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

Научная новизна диссертационной работы заключается в следующем:

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

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

Практическая значимость и реализация результатов работы:

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

ции и планирования машинного эксперимента.

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

Апробация работы и публикации.

Основные результаты работы докладывались и обсуждались на конференциях «Технологии Microsoft в теории и практике программирования», Москва, 2005, 2006; Девятом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах», Москва, 2006.

Публикации по теме диссертации.

По теме диссертации опубликовано 7 печатных работ. Из них 4 статьи, 3 тезиса докладов на научных конференциях и семинарах.

Структура и объём диссертационной работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 152 стр., включая 56 рис., 7 таб., список литературы из 204 наименований, 14 стр. приложений и актов об использовании результатов работы.

Содержание работы

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

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

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

Рис.1. Методы декомпозиции

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

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

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

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

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

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

1. Для каждой дуги конечного автомата создается переход в сети Петри, получая множество переходов Т = где к — число дуг графа, определяющего функционирование конечного автомата.

2. Для каждой вершины графа создается позиция Рд, сети Петри, где / = 1 ,...,т - вершина графа.

3. Для символа х, из входного алфавита X конечного автомата создается позиция Рх,.

4. Для символа у, из выходного алфавита У конечного автомата создается позиция Ру^

5. Задается отношение инцидентности в сети Петри.

На рис.2, представлен фрагмент сети Петри, созданный на базе конечного автомата.

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

Рис.2. Фра; мент сети Петри

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

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

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

Алгоритм состоит из следующих действий:

1. Каждому разбиению множества состояний яг, ставится в соответствие некоторая функция /г.

2. Образуются вспомогательные разбиения х, , на множестве состояний С, модели Б и 2Ъ на множестве входных воздействий Хг , подаваемых на модель Б .

3. Строится сеть компонентных автоматов М, для которой определяются:

- входной алфавит 2п сети N. равный входному алфавиту модели 8;

- выходной алфавит Шп сети N. равный выходному алфавиту модели Э;

- множество компонентных автоматов КА сети 14, т.е.

где 1 = 1, и, п - количество компонентов. Количество состояний КА1 равно количеству блоков в разбиении ж, т.е. С, = тг„ где л, е {я-}.

Входной алфавит КА, определяется следующим выраженем:

где и 2г, - внутренний и внешний входной алфавит КА1; Функция переходов компонентного автомата КА, определяются:

д, =7Г( -»7Г(

КА, =(С,2Л),

Функции соединения компонентных автоматов: /г :лл *7Та *...*жа —> 7„, где тс, - разбиения на множестве состояний модели;

Множество входной функций сети: ^ : 2и, где »= 1 ,п ;

Множество выходной функций сети: g|■.я|*z¡->Wl ;

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

где г = \,п, п - количество компонентных автоматов; ],к - номера состояний компонентного автомата;

Из анализа алгоритма декомпозиции модели функционального блока сделан вывод о том, что

- свойства компонентных автоматов и их связи между собой зависят от выбранного множества {п,};

- число разбиений во множестве {к1} равно число компонентных автоматов в сети N1;

- число блоков разбиений в множестве {ж,} равно числу внутренних состояний компонентных автоматов.

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

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

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

Выделены два этапа проведения имитационного эксперимента: организация и непосредственное проведение эксперимента и обработка результатов эксперимента.

Непосредственное проведение эксперимента можно разбить на следующие этапы:

1. Выбор факторов и откликов на сети Петри.

2. Задание области определения значений факторов в виде диапазона значений.

3. Выбор плана эксперимента.

Если в модели присутствуют случайные факторы, как например, вероятности срабатывания переходов, то задается количество повторных опытов г для каждой точки плана в пределах 5..7.

4. Установка соответствующих характеристик сети Петри в соответствии со значениями факторов рассматриваемой точки плана

5. Задание критерия останова моделирования сети Петри.

6. Запуск процесса моделирования сети Петри гы раз для и -й точки плана. Регистрация параметра сети Петри, выбранного в качестве отклика, по завершении каждого прогона сети.

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

• количество маркеров в позиции, обозначающей определенный входной сигнал (Рх,);

• наличие маркера в позиции, обозначающее состояние (Pq). Значение заданного фактора равно true, если маркер есть и false, если его нет. Такой фактор может быть только один в эксперименте, поскольку устройство может одновременно находится только в одном состоянии, а значит в сети Петри в любой момент времени может существовать только один маркер для всего множества позиций Pq, q=l,...,u, где и -число состояний устройства;

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

В качестве откликов модели можно выбрать один из следующих

параметров:

• количество срабатываний сети Петри до завершения процесса моделирования;

• количество маркеров в заданной позиции на момент останова моделирования;

• количество срабатываний заданного перехода на момент останова моделирования.

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

• инициализирующее значение для атрибута маркера в заданной

позиции;

• одна из констант,участвующих в предикате возбуждения перехода;

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

В качестве откликов, помимо вариантов предложенных для простой сети Петри, также можно использовать следующие:

• значение заданного атрибута маркера в заданной позиции на момент окончания моделирования;

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

Общая схема проведения эксперимента изображена на рис.3.

_и:_

Вычисления оценок козффиц4«нтоо функции огишка

Рис.3. Схема эксперимента

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

где т - количество оцениваемых коэффициентов модели;

уи - среднее значение результатов наблюдения в и-й точке плана,

у ы— значение отклика в этой же точке, предсказанное на модели.

Количество степеней свободы дисперсии адекватное ги }а = N - т.

При насыщенном планировании нет степеней свободы и сумма

отклонений равна нулю.

Проверка адекватности сводится к проверке гипотезы об однородности оценки дисперсии воспроизводимости <тг(_у) с количеством степеней свободы j(y) и оценке дисперсии адекватности. Проверка осуществляется по критерию Фишера.

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

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

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

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

В четвертой главе разработана программная система, реализующая решение поставленной задачи, с использованием структурного и объектно-ориентированного подходов. Язык программирования Object Pascal позволяет в полной мере использовать всю мощь этих подходов.

При разработке были выделены следующие модули:

• модуль TModel - содержит реализацию функциональности, связанной с созданием модели из отдельных объектов и визуализацией модели;

• модуль TDecomposition - содержит реализацию всех функций, связанных в декомпозицией модели;

• модуль TmainForm - содержит общие процедуры, используемые в

нескольких модулях;

• модуль ТУег№\¥ - модуль для заполнения структуры новых вершин после декомпозиции;

• модуль ТБга\у - содержит графические средства.

Рис.4. Структура модулей программного комплекса

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

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

11

Для обоих случаев используется одна и та же грамматика в]:

$-+£\Е>Е\Е>=Е\ЕоЕ\Е<=Е\Е<Е\Е = Е\е;

Е^Е+Т\Е-Т\Т;

т -+т*Р\Т / Р\ТапйР\ТогР\Р;

Р -> (5) 11й | яoíF.

После устранения левой рекурсии и проведения левой факторизации получаем грамматику С,: -

8-+Е\Е>Е\Е>=Е\ЕоЕ\Е<=Е\Е<Е\Е = Е\е;

Е-*- ТЕ';

£"—> +ТЕ'\ -ТЕ'\ е;

Т ->■ РГ;

Г'—» *РТ'| /¿ТI ап<1РТ'\ огРТ\ е;

Р -> (5) | к/ | по1Р.

Таким образом, в грамматике определены (терминалы):

• операции сравнения: <, >, <=, >=, =, о;

• операции сложения: -I, -, ог;

• операции умножения: *, /, аш1;

• унарный оператор: по!;

• идентификаторы: числовые константы, именованные константы и названия переменных;

• круглые скобки.

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

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

Транслятор выражений предназначен для преобразования списка лексем в список команд для стековой машины. Каждая команда - это объект соответствующего класса. Все классы, представляющие команды, реализуют интерфейс ХСоттапё. Этот интерфейс содержит метод ВоСошшап<1( ). Стековая машина использует список команд, вызывая для каждого объекта из этого списка метод ОоСоттапс!.

Поскольку в качестве основной технологии разработки был выбран ООП, необходимо выделить классы в разрабатываемой системе и пред-12

ставить их в виде диаграмм.

Рис.5. Основные классы программного комплекса

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

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

13

дложенного метода исследования.

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

J type Colorí int 'varNsk, Nin.Nout int

i const Msell, Osell int | const Mbuy, Dbuy int i function normRand(int,int)

Кол-во проданных компьютеров

(по1тРагк)(Мве11,Озе11))

Работа

(Nsk+Nin-Nout)

(Nak)

Товарные остатки магазина

(погтВвп(1(МЬиу, ОЬиу))

Рис.6. Формализация работы магазина в виде цветной сети Петри

После проведения полнофакторного эксперимента и варьирования значения параметров на двух уровнях, получена матрица результатов, где среднее значении функции отклика уи, несмещенная оценка дисперсии функции отклика д\ и оценка дисперсии воспроизводимости Б(уи) представлены в таблице 1.

Таблица 1.

№ опыта У. 5\ D(y»)

1 6,2 0,2 0,04

2 5 0,5 0,1

3 12,2 3,7 7,4

4 6,6 0,3 0,06

Из анализа полученных результатов, следует сделать вывод о том, что дисперсия функции отклика неоднородна, и, вероятно, присутствуют неучтенные в эксперименте факторы (например, ЭЬиу или ВБеН).

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

Рис.7. Экспериментальная проверка декомпозиционного метода исследования

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

15

ионирования сложных дискретных структур.

5. Основные положения метода исследования дискретных устройств апробированы на ряде практических приложений.

Публикации по теме диссертационной работы:

1. Давудпур Марьям. Классификация методов декомпозиции дискретных устройств // Информатика и системы управления в XXI веке: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Н.Э. Баумана (М.). - 2004. -№ 2. - С.171-173.

2. Давудпур Марьям. Декомпозиция дискретных систем средствами визуального программирования // Технологии Microsoft в теории и практике программирования: Сб. трудов конференции МГТУ им. Н.Э. Баумана. - Москва ,2005. - С.47.

3. Давудпур Марьям. Программный комплекс исследования функционирования дискретных устройств // Сборник трудов молодых учёных, аспирантов и студентов МГТУ им. Н.Э. Баумана. - М., 2005. -С. 121-126.

4. Давудпур Марьям. Проведение имитационных экспериментов над дискретными устройствами, формализованными в виде сети Петри //Тезисы девятого научно-практического семинара Новые информации-онные технологии в автоматизированных системах. - Москва , 2006. -С.174-175.

5. Давудпур Марьям, Рудаков И.В. Декомпозиционный метод исследования дискретных устройств //Информационные технологии. -(Москва) . - 2006. - № 2. - С.44-49.

6. Давудпур М. Формализация процесса функционирования сложного дискретного устройства в виде сети Петри // Конференция студентов, аспирантов и молодых ученых Технологии Microsoft в теории и практике программирования МГТУ им. Н.Э. Баумана. -Москва, 2006. - С.54-55.

7. Давудпур Марьям, Рудаков И.В. Алгоритм декомпозиции формальной модели функционального блока дискретного устройства //Вестник МГТУ им. Н.Э. Баумана. Сер. приборостроение. — 2006. - № 1. -С. 90-98;

Подписано к печати /^.¿Ю 06т Заказ 7% Объем 1,0 п.л. Тираж 100 зкч. Типография МГТУ им. Н Э Баумана

Л006h

H-7772

ВВЕДЕНИЕ.

1. АНАЛИЗ МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ИЕРАРХИЧЕСКИХ СИСТЕМ ПРОЕКТИРОВАНИЯ

СЛОЖНЫХ ДИСКРЕТНЫХ СТРУКТУР.

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

1.2Анализ видов и методов декомпозиции Сложных дискретных структур.

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

ВЫВОДЫ.

2. ДЕКОМПОЗИЦИОННЫЙ МЕТОД ИССЛЕДОВАНИЯ

ПРОЦЕССА ФУНКЦИОНИРОВАНИЯ СЛОЖНОЙ ДИСКРЕТНОЙ

СТРУКТУРЫ НА БАЗЕ МОДЕЛИ ФУНКЦИОНАЛЬНОГО БЛОКА.

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

2.2 Алгоритм декомпозиции сложной дискретной структуры.

ВЫВОДЫ.

3. ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ЭКСПЕРИМЕНТА

ПРИ ИССЛЕДОВАНИИ ФУНКЦИОНИРОВАНИЯ ДИСКРЕТНОЙ

СТРУКТУРЫ.

3.1 Задача постановки эксперимента при анализе функционирования сложной структуры.

3.2 Проверка адекватности модели функционального блока Дискретной структуры.

3.3 Методика проведения эксперимента при анализе функционирования сложной структуры.

ВЫВОДЫ.

4 .ПРОГР АММНО-А ЛГОРИТМИЧЕСКИЙ КОМПЛЕКС ДЕКОМПОЗИЦИОННОГО МЕТОДА ИССЛЕДОВАНИЯ

СЛОЖНЫХ ДИСКРЕТНЫХ СТРУКТУР.

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

4.2 Программное обеспечение подсистемы декомпозиции сложного дискретной структуры.

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

ВЫВОДЫ.

Одним из известных методов исследования процесса функционирования сложных дискретных структур является их формализация в виде простых и цветных сетей Петри [13,28,81,82,113,146,148,163]. К достоинствам сетей Петри [29,64,159,177] можно отнести возможность их графическое представление, явное описание и действий и состояний системы, отображение результатов моделирования непосредственно на схеме сети. Это определяет актуальность разработки и исследование методов формализации сложных дискретных структур именно в виде простых и цветных сетей Петри.

Большинство современных методик исследования и анализа сложных дискретных структур [31,32,59,60,79,118,168] основываются на иерархических принципах, которые требуют обеспечения сквозного проектирования структур и возможности создания или использования эффективных средств анализа, ориентированных на соответствующие методы иерархического проектирования [18,101].

Этим проблемам посвящены работы Бадулина С.С. [3,20], Баранова С.И. [22,23,24,25,26], Гаврилова М.А. [40,41], Девяткова В.В. [41,51], Ниссена К. [106], Норенкова И.П. [108,109], Петренко А.И. [1], Пупырева Е.И. [41],

Советова Б. Я. [126,127], Черненьког В.М. [139,140], Яковлева С.А. [127], Фридмана Т. [167], Ульмана Дж. [137,175], Янга С. [167], и др.

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

Одной из задач при разработке дискретных структур является задача анализа и контроля правильности функционирования структуры на ранних этапах его разработки. В результате системного проектирования определяется структурная схема, то есть набор функциональных блоков и их взаимодействие. На последующих этапах осуществляется моделирование работы отдельных блоков на уровне элементов без учета взаимодействия друг с другом, Предлагаемый метод иерархического исследования позволяет осуществить анализ и контроль правильности функционирования сложной структуры с использованием методов моделирования и декомпозиции, при котором структура описывается с разной степенью детализации [16,117,142,166].

Предлагаемый метод моделирования [10,11,17,36,68,145,189,197,198,202] позволит осуществить временной анализ работы структур и контроль правильности функционирования, определить скорость выполнения отдельных команд или последовательностей команд и определить загрузку аппаратных средств. Метод анализа дискретных структур только на основе моделей функциональных блоков недостаточен, так как не позволяет учитывать такие характеристики структуры как, например, временные параметры элементов, составляющих модель, а, следовательно, выполнять надежную верификацию проекта [27,73,150,152].

Моделирование больших систем [74,94,119,144] представляет собой задачу большой размерности, поэтому одним из методов исследования таких систем является метод декомпозиции, позволяющий разбивать исследуемую схему на части, проверяя работу каждой части и последовательно добавлять к проверенной части новые фрагменты.

В работах по моделированию [76,115,141,143,147,161,192] и многоуровневому анализу [21,99,116] предлагается использовать принцип "увеличительного стекла", когда различные участки схемы структуры анализируются с разной степенью детализации. Но в этих работах предполагалось, что переход с одного иерархического уровня на другой выполняется разработчиком схемы. Предлагаемый в работе метод декомпозиции моделей, реализованный в виде программного комплекса, позволяет реализовать принцип "увеличительного стекла" путем автоматического перехода от моделей функциональных блоков к моделям элементов.

Следующим этапом после создание математической модели и ее программной реализации является постановка вычислительного эксперимента. Данному направлению посвящен целый ряд работ [8,9,39,58]. Использование вычислительного эксперимента существенно уменьшает время исследования модели. Целями эксперимента могут быть: выяснение закономерностей функционирования системы, анализ влияния факторов на показатели качества систем, проверка адекватности модели. Традиционные методики проведения экспериментов из-за зависимости компонентов восстанавливаемого аналитического описания не позволяют определить раздельное влияние каждого фактора на результирующий показатель. В отличие от них теория планирования эксперимента дает возможность оценить вклад каждого параметра в значение показателя, т.е. приближенно восстановить закон функционирования объекта по экспериментальным данным. Полученное аналитическое описание объекта можно использовать для предварительного исследования вариантов построения системы. Основные методы теории планирования эксперимента рассмотрены, в частности, в [62,96,114]. Однако существует определенный пробел в научной литературе, связанный с методикой проведения экспериментов именно над цветными сетями Петри. В настоящей работе предложена методика проведения экспериментов над сетями Петри с использованием методов теории планирования эксперимента.

Для разработанных формализованных методов исследование сложных дискретных структур в виде сети Петри создано соответствующее программное обеспечение [77,97,98,102,129,130].

Данные программные продукты требуют существенных временных и аппаратных затрат при анализе процесса функционировании сложных структур.

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

- проводится анализ методов проектирования и формализации дискретных структур, реализующих иерархический подход при исследовании таких структур;

- дается классификация методов декомпозиции сложных дискретных структур и программного обеспечения таких методов;

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

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

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

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

выводы

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

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

3. Выбран объектно-ориентированный подход при разработке программного обеспечения и создана диаграмма классов объектов.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработана методика проведения машинного эксперимента над моделями дискретных структур, формализованных в виде сети Петри, для доказательства адекватности модели и корректности применения иерархического метода исследования дискретных структур.

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

5. Основные положения метода исследования дискретных структур проверены рядом практических примеров.

1. Автоматизация конструирования больших интегральных микросхем / А. И. Петренко, А. Я. Тетельбаум ,П. П. Сыпчук, и др.; - Киев: Висшая школа, 1983.-312 с.

2. Автоматизация проектирования структурных элементов ЭВМ: Учебное пособие / И.В.Герасимов, А.Х.Мурсаев и др.; Под ред. Е.П.Угрюмова. JL: ЛЭТИ, 1984. - 80 с.

3. Автоматизированное проектирование цифровых устройств / С.С.Бадулин, Ю. М. Барнаулов, В. А. Бердушев и др.; Под ред. С.С.Бадулина. М.: Радио и связь, 1981. -240с.

4. Агибалов Г. П. , Евтушенко Н. В. Каскадные сети автоматов и их характеризация в терминах кодирований и покрытий // VIII Всесоюзная конференция по теории кодирования и передачи информации. -Москва-Куйбышев, 1981.-С. 11-17.

5. Агибалов Г. П., Евтушенко Н. В. Алгебраическая характеризация перестановочных автоматов, разложимых в каскадное соединение меньших компонент // Кибернетика. 1984. - № 1. - С. 9-15.

6. Агибалов Г. П., Евтушенко Н. В., Декомпозиция конечных автоматов. — Томск :Изд-во Том. ун-та 1985 . 127 с.

7. Агибалов Г. П., Оранов A.M. Лекции по теории конечных автоматов. -Томск: Изд-во Том. ун-та, 1984. 185 с.

8. Адлер Ю. П., Марков Е. В., Грановский Ю. В. Планирование эксперимента при пойске оптимальных условий. М.: Наука, 1976 . - 278с.

9. Акофф Р. Л. Планирование в больших экономических системах. М.:Сов. Радио, 1972. - 224 с.

10. Алексеенко А. Г., Зуев И. А. Макромоделирование ИС операционных усилителей // Зарубежная радиоэлектроника. 1987. - №8. - С. 22-28.

11. И. Альянах И. Н. Моделирование вычислительных систем. Ленинград: Машиностроение, 1988 . -223 с.

12. Анисимов В. Программирование распределенных вычислительных систем // Системная информатика-3 / Под ред. В.Е.Котова. М.: Наука, 1993.-С. 210-247.

13. Анисимов Н. А., Композициональный подход к разработке параллельных и распределенных систем на основе сетей Петри //Программирование. 2001. - № 6. - С. 30-43.

14. Анисимова К. А. Математика. Учебно-методический комплекс-Якутск: Изд-во ЯГУ, 2000 120 с.

15. Арбиб М.А. Алгебраическая теория автоматов, языков и полугрупп. — М.: Мир, 1975.-216 с.

16. Артамонов Г. Т., Брехов О. М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978 . - 368с.

17. Ахо К. Иерархические системы. М.: Мир, 1979. - 319 с.

18. Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах / Под ред. О. Л . Бандман. М.: Радио и связь, 1987. - 134 с.

19. Бадулин С. С. , Барнаулов Ю.М., Бердушев В.А. Автоматизированное проектирование цифровых устройств / Под ред. С.С.Бадулина. М.: Радио и связь, 1981.-240с.

20. Балыбердин В. А. Методы анализа мультипрограммных систем. М.: Радио и связь, 1982.- 153с.

21. Баранов С. И., Журавина Л.Н., Песчанский В. А. Выбор разбиения при декомпозиции граф-схем алгоритмов // Автоматика и вычислительная техника. 1982. - №2. - С. 27-35.

22. Баранов С. И. , Журавина Л.Н., Килленберг X. Декомпозиция граф-схем алгоритмов // Автоматика и вычислительная техника. 1979. - №1. -С. 16-22.

23. Баранов С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Л.: Энергия, 1979. - 232 с.

24. Баранов С.И., Килленберг X. Декомпозиция микропрограммных автоматов // Автоматика и вычислительная техника .— 1978. —№6. С. 5-11.

25. Баранов С. И., Янцен Н. Я. Квазипараллельная декомпозиция микропрограммных автоматов // Автоматика и вычислительная техника. -1980.- №5.-С. 8-13.

26. Бахов В.А. Макромоделирование цифровых и импульсных схем при помощи макроэлементов // Радиоэлектроника. — 1980. — №6. С. 13-21.

27. Башкин В.А. Методы насыщения сетей Петри с невидимыми переходами // Моделирование и анализ информационных систем (Ярославль). 1999. - Вып. 6. - С. 16-20.

28. Башкин В.А., Ломазова И. А. Бисимуляция ресурсов в сетях Петри // Известия академии наук. Теория и системы управления. 2003. - №4. -С.115-123.

29. Бежанова М. М., Поттосин И. В. Современные понятия и методы программирования. -М.: Научный мир, 2000. -192 с.

30. Белоусов А. И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э. Баумана, 2004 . - 744с.

31. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1998. - 368с.

32. Боровков А. А. Математическая статистика. -М.: Наука, 1984. 462с.

33. Брауэр В. , Рудакова К. В. Введение в теорию конечных автоматов /Под ред. Ю. И. Журавлева. М.: Радио и связь, 1987. - 391 с.

34. Бузанов В. А. ,0 вычислении неисправностей в структурном автомате // Алгоритмы решения задач дискретной математики( Томск). 1987. -Вып. 2.-С. 127-129.

35. Бусленко Н. П. Моделирование сложных систем. -М.: Наука, 1978. -400с.

36. Бутаков Е. А. Методы создания качественного программного обеспечения ЭВМ. М.: Энергоатомиздат, 1984. -240с.

37. Быкова С. В. , Иволга В. П. Оценка эффективности некоторых алгоритмов минимального разбиения // Вычислительная техника в машиностроении. Минск: ИТК АН БССР, 1974. - С. 79-86.

38. Вентцель Е. С. Исследование операций: Задачи, принципы, методология. М.: Наука, 1980. -208 с.

39. Гаврилова М. А. Логический язык для представления алгоритмов синтеза релейных устройств. М.: Наука, 1966. - 342 с.

40. Гаврилова М. А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов (языки, методы, алгоритмы). М.: Наука, 1987.-352 с.

41. Гобземис А. Ю.Теория конечных автоматов и ее применения. -Рига.: Зинатне, 1983.- 197 с.

42. Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.- 119 с.

43. Давудпур Марьям, Рудаков И.В. Алгоритм декомпозиции формальной модели функционального блока дискретного устройства //Вестник МГТУ им. Н.Э. Баумана. Сер. приборостроение. 2006. — № 1. - С. 90-98;

44. Давудпур Марьям, Рудаков И.В. Декомпозиционный метод исследования дискретных устройств //Информационные технологии. -(Москва) . 2006. - № 2. - С.44-49.

45. Давудпур Марьям. Декомпозиция дискретных систем средствами визуального программирования // Технологии Microsoft в теории ипрактике программирования: Сб. трудов конференции МГТУ им. Н.Э. Баумана. Москва ,2005. - С.47.

46. Давудпур Марьям. Классификация методов декомпозиции дискретных устройств // Информатика и системы управления в XXI веке: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Н.Э. Баумана (М.). -2004. — № 2. — С.171-173.

47. Давудпур Марьям. Программный комплекс исследования функционирования дискретных устройств // Сборник трудов молодых учёных, аспирантов и студентов МГТУ им. Н.Э. Баумана. М., 2005. - С. 121-126.

48. Девятков В. В., Гиматдинова С. Г. Пакет прикладных программ для моделирования и исследования на ЭВМ дискретных систем. М.: ЦФАП ВНТИЦентра, 1978 . - 127 с.

49. Деев Г. Е. ,Конспект лекций по курсу "Теория конечных автоматов". -Обнинск : ОИАЭ , 1988. 79 с.

50. Дрягин Ю. С. Некоторые условия существования декомпозиции автомата // Алгоритмы решения задач дискретной математики (Томск). — 1987.-Вып. 2.-С. 40-52.

51. Евтушенко Н. В. К декомпозиции конечных автоматов в каскадное соединение стандартных компонент // Автоматика и вычислительная техника. 1979. - № 2. - С. 50-54.

52. Евтушенко Н. В. О принадлежности последовательности множеству контрольных последовательностей автомата // Алгоритмы решения задач дискретной математики (Томск). 1987. -Вып. 2. - С. 130-133.

53. Евтушенко Н. В., Лебедев A.B., Петренко А.Ф. Построение проверяющего множества для компоненты последовательной автоматной сети // Автоматика и телемеханика. 1994. - № 8. - С. 145-153.

54. Евтушенко Н. В., Матросова А.Ю. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей // Автоматика и вычислительная техника. 1991. - № 2. - С. 3-7.

55. Евтушенко Н. В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и вычислительная техника. -1989. -№ 3. С. 9-14.

56. Евтушенко Н. В., Прокопенко С.А. Построение проверяющих тестов для входо-выходных полуавтоматов // Новые информационные технологии . Екатеринбург: УрО РАН, 1998. - С. 216-218.

57. Евтушенко Н. В., Тренькаев В.Н. Методы синтеза тестов для компоненты автоматной сети // Новые информацион-ные технологии в исследовании дискретных структур. Екатеринбург: УрО РАН, 1998. - С. 219-223.

58. Ермаков С. М., Михайлов Г. А. Статистическое моделирование.-М.: Наука, 1982.-296с.

59. Ермакова С.М. Математическая теория планирования эксперимента .М.: Наука, 1983.-392 с.

60. Задорожный В. Н. Статистическое моделирование : Учебное пособие. -Омск, 1996.- 92с.

61. Зайцев Д. А. Верификация протокола BGP с помощью декомпозиции модели Петри на функциональные подсети // Труды симпозиума по проектированию, анализу и моделированию распределённых систем. Сан Диего (Калифорния, США), 2005. - С. 72-78.

62. Зайцев Д. А. Основанное на декомпозиции вычисление инвариантов сетей Петри // Труды семинара по вычислениям управляемым фишками 25-й международной конференции по приложениям и теории сетей Петри. Болонья ( Италия), 2004. - С. 79-83.

63. Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971.-512 с.

64. Закревский А. Д. Синтез асинхронных автоматов на ЭВМ. -Минск: Наука и техника, 1975. 184 с.

65. Зобов Б. И., Сурков А. В. Основы моделирования Вычислительных систем. -М.: МЛТИ, 1982. 32с.

66. Иванов Н. Н., Михайлов Г. И., Руднев В. В. Конечные автоматы: эквивалентность и поведение . -М.: Наука, 1984. 192 с.

67. Иванова Г.С., Ничушкина Т.Н., Пугачев Е.К. Объектно-ориентированное программирование. М.:Изд-во МГТУ им.Н.Э.Баумана, 2003.-368с.

68. Ивченко Г. И., Каштанов В. А., Коваленко И. Н. Теория массового обслуживания. -М.: Вьющая школа, 1982. 256с.

69. Иглхарт Д. Л., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания / Под ред. В.В.Калашникова. М.: Радио и связь, 1984.- 136 с.

70. Ильин В. Н. Проблемы макромоделирования // Автоматизация пректирования в радиоэлектронике и вычислительной технике: Материалы семинара МДНТП им.Ф.Э.Дзержинского. -М. ,1989. С. 23-30.

71. Калашников В. В. Организация Моделирования сложных систем. М.: Знание, 1982 . — 168с.

72. Карпов Ю. Г. Теория автоматов. СПб. Литер,2003 . - 208с.

73. Келтон В., Лоу А. Имитационное моделирования. — СПб. Киев: Питер - Издательская группа ВНУ, 2004 . - 847с.

74. Киндлер Е. Языки Моделирования. М.: Энергоатомиздат, 1985 . -288с.

75. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.-432 с.

76. Клини С. Введение в метаматематику. М.: Изд-во иностр. лит., 1957. -528с.

77. Конопка Р. Создание оригинальных компонент в среде Delphi. Киев: ДиаСофт, 1996.-512 с.

78. Котов В. Е. Алгебра регулярных сетей Петри // Кибернетика. -1980. -N5.-C. 10-18.

79. Котов В. Е. Сети Петри. М.: Наука, 1984. - 160 с.

80. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов . -М.:Наука , 1985. 319 с.

81. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Элементы теории автоматов . -М.: Изд-во МГУ, 1978. 216 с

82. Кудрявцев В. Б., Подколзин А. С., Ушчумлич Ш. Введение в теорию абстрактных автоматов : Учебное пособие для ун-тов по спец. "Математика" . -М.: Изд-во МГУ, 1985. 173 с.

83. Курейчик В. М., Карелин В.П., Ориентированные графы и конечные автоматы . -М.: Наука , 1971. 17 с.

84. Кутузов О. И., Задорожный В. Н., Олзоева С. И. Имитационное моделирование сетей массового обслуживания: Учебное пособие. Улан-Удэ: Изд-во ВСГТУ, 2001. - 228 с.

85. Куфарева И.Б., Евтушенко Н.В., Петренко А.Ф. Синтез проверяющих тестов для недетерминированного автомата относительно редукции //Автоматика и вычислительная техника. 1998. - № 3. - С. 10-20.

86. Лавров И. А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1984. - 223 с.

87. Лазарев В. Г. Автоматы и управление сетями связи. М.: Наука, 1971. -211 с.

88. Лазарев В. Г. Автоматы и управление. М.: Наука, 1972. - 128 с.

89. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989 . - 328с.

90. Левин В. И.,Теория автоматов и моделирование сложных систем : Учебное Пособие. Пенза :Изд-во Пенз. гос. техн. ун-та ,1995. - 82 с.

91. Левин И. С. Декомпозиционный синтез автоматов на ПЛМ с памятью //Автоматика и вычислительная техника. 1986. - №2. - С. 66-73.

92. Логическое проектирование БИС / В.А.Мищенко, А.И.Аспидов, В.В.Биттер и др.;Под ред.В.А.Мищенко. -М.: Радио и связь, 1988. 312 с.

93. Ломазова И. А. Анализ семантических свойств некоторых классов программ и сетей Петри : Автореферат диссертации на соискание ученой степени доктора физико-математических наук. -Москва: ВЦ РАН, 2001. -32 с.

94. Ломазова И. А. Объектно-ориентированные сети Петри: формальная семантика и анализ//Системная информатика (Новосибирск). 2002. - № 8. - С.60-61.

95. Ломазова И. А., Лысенко Н.В. Моделирование задачи разделенного доступа средствами модульных сетей Петри // Моделирование и анализ информационных систем (Ярославль). 1998. -Вып. 5. - С.62-73.

96. Майника Э. Алгоритмы оптимизации на сетях и графах /Под ред. Е.К.Масловского -М.: Мир, 1981.-322 с.

97. Мангейм М.Л. Иерархические структуры, модель процессов проектирования и планирования. -М.: Мир, 1970. 180 с.

98. Международный стандарт представления сетей Петри языком XML http://www.daimi.au.dk/pn2000/Interchange

99. Мелихов А. Н. Ориентированные графы и конечные автоматы. -М.: Наука, 1971.-416 с.

100. Моделирование коммутируемых ЛВС раскрашенными сетями Петри //Математика и компьютеры в моделировании . 2004. - Том 65, № 3. - С. 245-249.

101. Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 2006.-396 с.

102. Ниссен К. Методология и средства иерархического проектирования СБИС // Тр. ИИЭР. 1999. - Том 71. - №1. - С.81-94.

103. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304с.

104. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем. М.: Высшая школа, 1986. - 304 с.

105. Норенков И.П. Основы автоматизированного проектирования:Учеб.для вузов. 2-е изд.,перераб.и доп. М.:Изд-во МГТУ им.Н.Э.Баумана, 2002. -336с.:ил. (Сер.Информатика в техническом университете)

106. Окунишникова Е. В., Чурина Т. Г. Способ построения раскрашенных сетей Петри, моделирующих Estelle-спецификации // Проблемы спецификации и верификации параллельных систем. ~ Новосибирск, 1995. -С. 95-123.

107. Орлик C.B. Секреты Delphi на примерах. М.:Бином , 1996. - 352 с.

108. Панкратова И. А., Быкова C.B., Николаева JI.A., Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины. 1991. - № 1. - С. 3-9.

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

110. Планирования эксперимента и моделирования http://www.csa.ru/skif/kurs 5/3intt.htm

111. Полляк Ю.Г. Вероятностное моделирование на ЭВМ. М.: Сов. радио, 1971.-400 с.

112. Поспелов Д. А. Логические методы анализа и синтеза схем. -М.: Энергия, 1974.- 368 с.

113. Роджерс С. Теория рекурсивных функций и эфективная вычислимость. -М.:МИР, 1972.-624с.

114. Ручкин К. А. Учебное пособие по курсу "Основы дискретной математики".Теория графов. -Донецк: ДонГТУ, 2004. 110с.

115. Самарского А. А. Математическое моделирование: Методы, описания и исследования сложных систем . М.: Наука, 1989. - 128 с.

116. Сачков В. Н. Комбинаторные методы дискретной математики. М.: Наука, 1977.-317 с.

117. Сидорова Н. С. Преобразования сетей Петри: Автореферат Диссертация на соискание учёной степени канд. техн. наук. Ярославль , 1998.- 15с.

118. Синтез асинхронных автоматов на ЭВМ / А.Д. Закревский, Л.И. Балаклей, Н. А. Елисеева и др. -Минск: Наука и техника, 1975. 181 с.

119. Скурихин Н. А., Яхонтов Ю. К. Математические основы теории и способы описания дискретных автоматов : Конспект лекций для студентов спец. 0901 А, 0902А. -Л.: ЛТА ,1983.-42 с.

120. Слепцов А. И., Григорьев A.B. Математические модели дискретных систем: Учебное пособие. -Одесса: ОНАС им. А.С.Попова, 2004. 40с.

121. Слепцов А. И., Миланин A.A. Методические материалы к программной системе моделирования дискретных параллельных процессов, встраивания в автоматизированные системы и обучения специалистов . Донецк: ДПИ, 1991,- 59 с.

122. Советов Б. Я. Моделирование систем. Практикум . -М.: Высшая школа, 2003. 295 с.

123. Советов Б. Я.,Яковлев С.А. Моделирование систем . -М.: Высшая школа, 2001.-343 с.

124. Султан-Заде Н. М., Щеголева А. П., Теория дискретных автоматов : Учебное пособие по спец. 0636 . М.: ВЗМИ , 1983. - 86 с.

125. Таль А. А. Юдитский С. А. Иерархия и параллелизм в сетях Петри.Сложные автоматные сети Петри с параллелизмом // Автоматика и телемеханика. 1982. - № 9. - С. 83-88.

126. Тарасюк И. В. Понятия эквивалентностей для разработки параллельных систем с использованием сетей Петри // Программирование . 1998. -№ 4. - С.19-39.

127. Теория сетей Петри, простые сети Петри, цветные сети Петри, язык предписаний http://www.iacp.dvo.ru/labl 1 /otchet/ot2000/pn3.html

128. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. М.:Наука, 1987. - 288 с.

129. Федосеева JI. И. / Информационные основы цифровых автоматов : Учебное пособие. Пенза :Изд-во Пенз. гос. техн. ун-та , 1995. - 15.с

130. Функциональные сети Петри // Записки лаборатории LAMS ADE,Университет Париж-Дофин. 2005. -№ 224. - 62с. (www.lamsade. dauphi ne. fr/cah i ers .htm 1 ).

131. Xoap 4. Взаимодействующие последовательные процессы. M.: Мир, 1989.-264 с.

132. Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 2004. - 320с.

133. Хопкрофт Джон. Э., Мотвани Раджив, Ульман Джеффри.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Перевод с англ. — М.:Издательский дом Вильяме, 2002. 528 с.

134. Цвиркун А. Д. Основы синтеза сложных систем. М.: Наука, 1982. -200 с.

135. Черненький В.М. Имитационное моделирование. -М.:Высшая школа ,1990. -112с.

136. Черненький В.М., Байкенов A.C. Анализ вложенных декомпозиционных методов расчёта Семо // Методологические проблеми автоматизации проектирования АСОЦУ: Тезиси докладов НТК. -Ереван, 1985.-С. 34-35.

137. Шеннон Р. Дж. Имитационное моделирование систем искусство и наука. М. : Мир, 1978 . - 418 с.

138. Шестаков Е. А. Об одном методе решения задачи декомпозиции дискретных автоматов // Автоматика и вычислительная техника. 1979. -№ 5. - С.7-15.

139. Якимов И. М. Моделирование систем. Казань: КАИ, 1980 . - 104 с.

140. Якимов И.М., Мосунов В.Е., Яхина 3. Т. Имитационное моделирование сложных систем. Казань: КАИ, 1984 . - 78 с.

141. Alan Pritsker A. Introduction to Simulation & SLAM. New Jersey: John Wiley & Sons Inc, 1986. - 588 p.

142. Alekseev G. I., Bystrov A. V., Churina T. G. Petri-Net Based Environment for the Specification, Analysis and Simulation of Concurrent Systems //Specification, verification and net models of concurrent systems. -Novosibirsk, 1994.-P. 116-127.

143. Andradottir S. A Review of Simulation Optimization techniques // Winter Simulation Conference. Washington D.C., 1998.-P. 151-158.

144. Anisimov N.A., Kharitonov D.I., Kovalenko A.A. Modeling and Verification of Communication Protocols Using Petri Nets // Proc. Pacific Int. Conf. Mathematical Modeling and Cryptography (PMMC-95). Vladivostok, 1995. - P. 12-13.

145. Antsaklis Panos J., Moody John O. Supervisory Control of Discrete Event Systems Using Petri Nets. Boston: Kluwer Academic Publishers, 1998. -208p.

146. Bagrodia R.L. Perils and Pitfalls of parallel Discrete Events Simulation //Winter Simulation Conference. San Diego, 1996. - P. 136-143.

147. Baldassari M., Bruno G. An Environment for Object-Oriented Conceptual Programming Based on PROT Nets Advances in Petri Nets // Lecture Notes in Computer Science 340. Berlin, 1988. - P. 1-19.

148. Banks Jerry, Carson John S. Discrete-Event System Simulation. London: Prentice-hall, 2004. - 608 p.

149. Battiston E., Cindio F. de, Mauri G. OBJSA Nets: A Class of High-level Nets having Objects as Domains Advances in Petri Nets // Lecture Notes in Computer Science 340. Berlin, 1988. - P.20-43.

150. Bause F. , Kritzinger P. Stochastic Petri Nets. Berlin: Friedrich Vieweg & Sohn-Verlag , 2002.-218 p.

151. Bause Falko, Kritzinger Pieter S. Stochastic Petri Nets. Berlin: Friedrich Vieweg & Sohn Verlag, 2002. -218p.

152. Berthomieu B., Diaz M. Modeling and Verification of Time Dependent Systems Using Time Petri Nets // IEEE Transact. On Software Eng. 1991. -Vol. 17, N.3.- P. 259-273.

153. Borger E., Kleine Buning H. The Reach Ability Problem for Petri Nets and Decision Problems for Skolem Arithmetic // Theoretical Computer Science. -1980.-№2.-P. 123-143.

154. Carroll John L.,Darrell Long D. Theory of Finite Automata. Englewood Cliffs,(New Jersey): Prentice-hall, 1989. - 432 p.

155. Christensen S. Petrucci L. Towards a Modular Analysis of Coloured Petri Nets Application and Theory of Petri Nets. Heidelberg: Springer-Verlag, -1992.-133 p.

156. Christensen S., Hansen N.D. Coloured Petri Nets Extended with Channels for Synchronous Communication // Proceedings of 15th International Conference on the Application and Theory of Petri Nets. Zaragoza, 1994. - P. 159-178.

157. Christopher T., Evens M. Structure of a Distributed Simulation Systemj

158. The 3 International Conference on Distributed Computing systems. New York, 1983.-P. 584-589.

159. Claude Girault. Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications. Berlin and Heidelberg GmbH & Co. K: Springer-Verlag, 2001. - 622p.

160. Cortadella Jordi, Reisig Wolfgang Applications and Theory of Petri Nets. -New York: Springer-Verlag, 2004. -505 p.

161. David R., Alia H. Petri Nets and Grafcet: Tools for Modeling Discrete Event Systems . Englewood Cliffs, (New Jersey): Prentice-hall, 1992. - 671 p.

162. Desel Jorg, Esparza Javier. Free Choice Petri Nets. — Cambridge: Cambridge University Press, 2002. -252p.

163. Evtushenko N.V. Conditions for existence of nontrivial parallel decompositions of sequential machines // Lecture notes in computer science (Berlin).—1987. -№ 278. P. 123-126.

164. Fridman T.D., Yang S.C. Methods used in an automatic logic design generator (ALERT) // IEEE Transactions on Computers. -1999. -V.C-19, N 7. -P. 593-614.

165. Gamier R., Taylor J. Discrete Mathematics for New Technology. — New York: Institute of Physics Publishing, 2001. 700p.

166. Goldschlager L.,Lister A.M., Lister A. Computer Science: A Modern Introduction. — London: Prentice-Hall International Series in Computer Science, 1988.-330p.

167. Grabowski Jens, Nielsen Brian. Formal Approaches to Software Testing. -Berlin: Springer-Verlag and Heidelberg GmbH, 2005. -235 p.

168. Haas Peter J. Stochastic Petri Nets: Modelling, Stability, Simulation. New York: Springer-Verlag, 2001. - 53 lp.

169. Hassane Alia, Rene David. Discrete, Continuous, and Hybrid Petri Nets . -Berlin: Springer-Verlag Berlin and Heidelberg GmbH & Co. K, 2004. -546p.

170. Holliday M.A., Vernon M.K., A Generalized Timed Petri Net Model for Performance Evaluation // Proc. Int. Workshop on Timed Petri Nets. Torino, 1985.-P. 181-190.

171. Honnef Bad. Advanced Course on Petri Nets. Berlin: Advances, 1987. -255p.

172. Hopcroft J.E., Ullman J.D., Introduction to Automata Theory, Languages, and Computation. -New York: Addison-Wesley, 1979. 505 p.

173. Humboldt University of Berlin, Department of Computer Sciences, Petri Net Kernel http://www.informatik.hu-berlin.de/top/pnk/index-engl.html

174. Jensen K. An Introduction to the Theoretical Aspects of Coloured Petri nets // Lecture Nots in comput.Sci. -1994. -No803. P. 70-120.

175. Jensen K. Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use. Berlin: Springer-Verlag, 1992. - 90p.

176. Johnsonbaugh R. Discrete Mathematics. New Jercy: Prentice Hall, 2001. -814p.

177. Kam Timothy, Synthesis of Finite State Machines. Boston: Kluwer Academic Publishers, 1997. -296p.

178. Kleijnen J. P. C., Statistical Techniques in Simulation. New York: Dekker, 1974. -775p.

179. Knuth D. E., The Art of Computer Programming: Semi Numerical Algorithms. -New York: Addison-Wesley, 1997. 896 p.

180. Koffman Elliot, Maxim Bruce Software Design and Data Structures in Turbo PASCAL. New York: Addison Wesley, 1994. - 600p.

181. Kohavi Zvi. Switching and Finite Automata Theory.-London: Mc Graw-Hill, 1986.-658p.

182. Kristensen Lars M., Jensen Kurt. The practitioner's Guide to Coloured Petri Nets. Aarhus:Aarhus, 1998. -35p.

183. Lakos Charles. From Coloured Petri Nets to Object Petri Nets-Sydney: Tasmania, 1995.-20p.

184. Lawson Mark V. Finite Automata. London: Chapman & Hall/CRC, 2003.-320p.

185. Lindemann Christophe. Performance Modelling with Deterministic and Stochastic Petri Nets. Sydney: John Wiley and Sons Ltd., 1998. -422 p.

186. Mitrani I., Probabilistic Modelling of Distributed Computing Systems //Conf. in Distributed Computing Systems Programme. London, 1984. - P. 139-153.

187. Molloy M.K., Performance Analysis Using Stochastic Petri Nets // IEEE Trans, on Computers. -1982. Vol.31, N.9. - P.913-917.

188. Murata T. Petri Nets: Properties, Analysis and Applications // Proceedings of the IEEE. -1989. Vol. 77, No 4. - P. 541-580.

189. Narsingh Deo. System Simulation with Digital Computers. Englewood: Prentice-hall, 1989.-200 p.

190. Peterson James Lyle. Petri Net Theory and the Modeling of Systems. — London: Prentice Hall, 1981. -290p.

191. Richard Beuchi J., Siefkes Dirk.Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. New York Inc.: Springer-Verlag, 1989.-338p.

192. Rosen Kenneth H. Discrete Math & Its Applications. -Columbus: McGraw-Hill Education, 2001. -896p.

193. Rozenberg G. Advances in Petri Nets. Berlin: Springer-Verlag, 1987. -266p.

194. Sheldon M. Ross. Simulation, Statistical Modeling & Decision Science.— London: Academic Press Inc., 1996.-304p.

195. Sheldon M. Ross. Simulation. New York: Macmillan USA, 2001.- 120 p.

196. Taubner Dirk A. Finite Representations of Ccs and Tcsp Programs by Automata and Petri Nets. Berlin and Heidelberg GmbH & Co. K: SpringerVerlag, 1989. - 178p.

197. Venkatesh K., Zhou M. C. Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach. New Jersey: World Scientific Publishing, 1999. -428p.

198. Wilfried Brauer,Wolfgang Reisig. Advanced Course on Petri Nets. New York: Springer-Verlag, 1986. - 540p.

199. Yu-Chi Ho. Modeling, Control and Optimization of Complex Systems. -New York: Springer-Verlag, 2002. 320p.

200. Zuberek W.M., Stochastic Petri Nets and Timed Petri Nets in Modelling and Performance Evaluation // Proc. APICS Annual Computer Science Conf., -Wolfville (Canada), 1987. P. 66-82.

201. Zuberek, W.M. Timed Petri Net Models of Queuing Systems // Proc. 7-th Annual Int. Phoenix Conf. on Computers and Communications (PCCC'88). -Scottsdale, 1988. P. 324-329.