Моделирование и проектирование систем

Моделирование и проектирование систем

 

 

Содержание

 

 

1. Введение в моделирование и проектирование систем... 3

2. Моделирование систем... 9

2.1. Системы и модели. 9

2.2. Концептуальное моделирование систем. 17

2.3. Математическое моделирование систем. 18

2.3.1. Моделирование непрерывных систем.. 20

2.3.2. Моделирование непрерывных систем.. 28

2.3.3. Обобщённые модели (A-схемы) 38

2.4. Анализ и оптимизация математических моделей. 40

2.5. Физическое моделирование систем. 40

2.6. Информационно-логическое моделирование систем. 41

2.7. Моделирование бизнес-процессов. 44

2.8. Алгоритмическое моделирование систем. 49

2.9. Объектное моделирование систем. 50

3. Проектирование систем... 61

3.1. Введение в проектирование систем. 61

3.2. Моделирование предметной области на UML. 72

3.3. Анализ предметной области и построение модели “как должно быть”. 84

3.3.1. Анализ модели предметной области. 84

3.3.2. Построение модели “как должно быть”. 86

3.3.3. Разработка технического задания на создание АС. 88

3.4. Построение UML-модели автоматизированной системы.. 89

3.4.1. Элементы диаграмм UML для моделирования автоматизированной системы.. 89

3.4.2. Диаграмма вариантов использования. 89

3.4.3. Диаграмма деятельности. 91

3.4.4. Диаграмма последовательности. 91

3.4.5. Диаграмма классов. 92

3.4.6. Диаграмма объектов. 94

3.4.7. Диаграмма композитной структуры.. 94

3.4.8. Диаграмма пакетов. 95

3.4.9. Диаграмма конечных автоматов. 96

3.4.10. Диаграмма обзора взаимодействий. 96

3.4.11. Диаграмма коммуникации. 97

3.4.12. Диаграмма синхронизации. 98

3.4.13. Диаграмма компонентов. 99

3.4.14. Диаграмма развертывания. 100

 

Моделирование систем

Системы и модели

Основные вопросы:

- отношение оригинал-модель;

- основы теории подобия: первая теорема подобия (необходимые условия подобия), вторая теорема подобия (ПИ-теорема), третья теорема подобия (необходимые и достаточные условия установления подобия);

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

- сложность, адекватность и оптимизация модели;

- структурная и объектная методологии моделирования систем;

- этапы моделирования системы.

 

Модель – это объект любой природы, способный с определенной точностью замещать реально существующий объект.

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

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

1) модель не существует сама по себе, а выступает в единстве с некоторым объектом-оригиналом, который она представляет (замещает) в процессе его изучения или проектирования;

2) для естественных материальных объектов модель вторична, т.е. появляется как следствие изучения и описания этого объекта (например, модель солнечной системы), а для искусственных материальных объектов (создаваемых человеком или техникой) модель первична, т.к. предшествует появлению самого объекта (например, модель самолета или двигателя);

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

4) модель должна быть подобна объекту, который она замещает, т.е. модель в определенном смысле является аналогом (копией) объекта. Если в исследуемых ситуациях модель ведет себя так же, как и моделируемый объект, или это расхождение невелико и устраивает исследователя, то говорят, что модель адекватнаоригиналу. Адекватность – это воспроизведение моделью с необходимой полнотой и точностью свойств объекта, существенных для целей данного исследования;

5) построение модели не самоцель. Она строится для того, чтобы можно было экспериментировать не с самим объектом, а с более удобным для этих целей его представителем – моделью.

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

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

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

Первая теорема подобия (теорема Ньютона-Бертрана): подобные явления характеризуются численно равными критериями подобия.

Теорема задает необходимые условия подобия и устанавливает, что единственным количественным условием подобия процессов является равенство критериев подобия объекта-оригинала и модели. Она указывает, какие величины следует измерять при проведении опытов, результаты которых требуется обобщить: надо измерять те величины, которые входят в критерии подобия.

Вторая теорема подобия (π-теорема или теорема Бэкингем-Федермана): всякое полное уравнение физического процесса, записан­ное в определенной системе единиц, может быть представлено функ­циональной зависимостью между критериями подобия К, полученными из участвующих в процессе параметров. Такие уравнения называются уравнениями обобщенных переменных, или критериальными уравнениями.

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

Третья теорема подобия (обратная теорема или теорема Кирпичева-Гухмана): необхо­димыми и достаточными условиями для создания подобия являются про­порциональность сходственных параметров, входящих в условия одно­значности, и равенство критериев подобия сопоставляемых явлений. Условия однозначности – это условия, определяющие индивидуальные особенности исследуемого явления, например, начальные, граничные или краевые условия. Эти условия не зависят от механизма самого исследуемого явления.

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

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

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

Положение 3. Осуществление модели согласно положениям 1 и 2 возможно в сколь угодно сложных анизотропных, нелинейных или имеющих вероятностно заданные параметры системах при условии одновременного соблюдения соответствующих дополнительных положений:

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

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

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

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

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

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

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

Основную классификацию видов подобия осуществляют по степени соответствия параметров модели и оригинала: абсолютное подобие и практическое подобие.

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

причем возможно m_j = const,   m_j = var,   m_j = f (P_j-r, P_j+h,...) и т.д.

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

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

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

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

В практическом подобии выделяют полное, неполное и приближенное подобия.

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

Неполноеподобие – это подобие параметров модели оригиналу только во времени или только в пространстве.

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

По параметру физической природы различают физическое и математическое подобие объектов.

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

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

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

Модели характеризуются тремя основными признаками:

- принадлежностью к определенному классу задач (например, управление техническими объектами, управление технологическими процессами, планово-экономические задачи и др.);

- принадлежностью к определенному классу объектов (физические, биологические и др.);

- способом реализации.

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

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

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

Моделирование может быть статическим и динамическим.

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

Моделирование может быть детерминированным и стохастическим.

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

Моделирование может быть дискретным и непрерывным.

Модель является дискретной, если она описывает поведение системы только в дискретные моменты времени, в дискретных состояниях и дискретными значениями параметров. Модель будет непрерывной, если она описывает поведение системы для всех моментов времени из некоторого промежутка с помощью вещественных значений параметров. Возможны дискретно-непрерывные модели, в которых время и/или часть параметров могут быть дискретными и непрерывными (например, дискретные системы в непрерывном времени или непрерывные системы в дискретном времени).

Моделирование может быть полным, неполным и приближенным.

Полным называется моделирование, при котором достигается полное практическое подобие исследуемого объекта и модели во времени и в пространстве.

Неполным называется моделирование, при котором реализуется неполное подобие исследуемого объекта и модели во времени и в пространстве.

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

Классификация видов моделирования систем приведена на рисунке 1.

Все моделируемые объекты имеют следующие характеристики:

- сложность – степень "непредсказуемости", "запутанности", противоречия "здравому смыслу" и т.д. статической структуры или поведения объекта;

- управляемость – способность объекта переходить из одного состояния в другое под действием управляющих воздействий и находиться в этом состоянии с заданной точностью необходимое время;

- степень воспроизводимости результатов – если наблюдать объект в одном и том же состоянии в различные моменты времени, то разница в наблюдениях не должна превышать некоторого заданного значения (точности измерения).

 

Полное

Неполное

Приближенное

Моделирование систем

Детерминированное

Стохастическое

Статическое

Динамическое

Непрерывное

Дискретное

Абстрактное

Физическое

Дискретно-непрерывное

Наглядное

Символическое

Математическое

Натурное

Физическое

 

Рис. 1. Классификация видов моделирования систем.

 

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

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

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

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

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

По параметру сложности различают простые системы, сложные или большие системы и сверхбольшие системы.

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

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

Оптимальной считается модель, обладающая наименьшими сложностью и размером, которая способна целостно и четко восприниматься исследователем.

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

Моделирование объектов всегда осуществляется в рамках некоторой методологии.

Методология определяет наиболее общие принципы и подходы к моделированию систем определенного класса.

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

Методология структурного моделирования (SADT – Structured Analysis and Design Technique) определяет структурный подход к моделированию объектов и предоставляет совокупность моделей, методов и процедур, позволяющих строить модели, отражающие структуру и функционирование объекта.

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

Методология SADT представлена семейством стандартов IDED для решения задач моделирования сложных систем, позволяющих формировать и анализировать модели деятельности широкого спектра сложных систем в различных разрезах:

IDED0 – стандарт функционального моделирования, определяющий построение функциональной модели объекта;

IDEF1X – стандарт информационного моделирования объекта, позволяющий строить модели баз данных в виде модели «сущность-связь»;

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

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

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

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

Основными элементами объектной модели являются объекты и классы.

Объект – предмет или явление, имеющее четко определенное поведение и обладающий состоянием, поведением и индивидуальностью. Класс – это множество объектов, связанных общностью структуры и поведения.

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

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

Унифицированный язык моделирования (UML – Unified Modeling Language) – это универсальный язык визуального моделирования систем.

В UML модели есть два аспекта:

- статическая структура – описывает, какие типы объектов важны для моделирования системы и как они взаимосвязаны;

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

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

     В общем случае процесс моделирования системы состоит из следующих этапов:

1. Постановка задачи и определение свойств оригинала, подлежащих исследованию.

2. Констатация сложности или невозможности исследования оригинала.

3. Выбор или построение модели, адекватной оригиналу и легко поддающейся исследованию.

4. Исследование модели в соответствии с поставленной задачей.

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

6. Проверка результатов на оригинале.

 

Т а б л и ц а 2.1

Таблица переходов и входов автомата Мили

 

Входы x i	Состояния   z k
	z0	z 1	…	…	…	z k
	Переходы
x1	φ (z 0, x 1)	φ (z 1, x 1)	…	…	…	φ (z k, x 1)
x2	φ (z 0, x 2)	φ (z 1, x 2)	…	…	…	φ (z k, x 2)
….	…..	….	….	….	….	….
	Выходы
x1	ψ (z 0, x 1)	ψ (z 1, x 1)	…	…	…	ψ (z k, x 1)
x2	ψ (z 0, x 2)	ψ (z 1, x 2)	…	…	…	ψ (z k, x 2)
….	…..	….	….	….	….	….

 

Т а б л и ц а 2.2

Таблица переходов и входов автомата Мили с тремя состояниями (z ₀, z ₁, z ₂), двумя входными (x ₁, x ₂) и двумя выходными (y ₁, y ₂) сигналами

 

Входы x i	Состояния z k
	z 0	z 1	z 2
	Переходы
x 1	z 2	z 0	z 0
x 2	z 0	z 2	z 1
	Выходы
x 1	y 1	y 1	y 2
x 2	y 1	y 2	y 1

 

Описание работы F –автоматов Мура иллюстрируется таблицей 2.3, а пример табличного способа задания F –автомата Мура с пятью состояниями (z ₀, z ₁, z ₂, z ₃, z ₄), двумя входными (x ₁, x ₂) и тремя выходными (y ₁, y ₂, y ₃) сигналами приведён в таблице 2.4.

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

 

Т а б л и ц а  2.3

Отмеченная таблица переходов автомата Мура

Входы x i	Состояния z k
	ψ (z 0)	ψ (z 1)	….	ψ (z k)
	z 0	z 1	….	z k
x 1	φ (z 0, x 1)	φ (z 1, x 1)	…	φ (z k, x 1)
x 2	φ (z 0, x 2)	φ (z 1, x 2)	…	φ (z k, x 2)
…	…	…	…	…

Т а б л и ц а 2.4

Отмеченная таблица переходов автомата Мура с пятью состояниями (z ₀, z ₁, z ₂, z ₃, z ₄), двумя входными (x ₁, x ₂) и тремя выходными (y ₁, y ₂, y ₃) сигналами

Входы x i	Состояния   z k
	y1	y1	y3	y2	y3
	z0	z1	z2	z3	z4
x1	z1	z4	z4	z2	z2
x2	z3	z1	z1	z0	z0

 

Для автоматов Мили эта разметка производится так: если входной сигнал x_k действует на состояние z_i, то, согласно сказанному, получается дуга, исходящая из z_i и помеченная x_k; эту дугу дополнительно отмечают выходным сигналом y = ψ (z _i, x _k). На рис. 2.3 приведён заданный ранее таблицей 2.2 граф F –автомата Мили. 

Рис. 2.3. Граф автомата Мили

 

Для автоматов Мура аналогичная разметка графа такова: если входной сигнал x_k, действуя на некоторое состояние z_i автомата, вызывает переход в состояние z_j, то дугу, направленную в z_j и помеченную x_k, дополнительно отмечают выходным сигналом y = ψ (z _j, x _k). На рис. 2.4 приведён заданный ранее таблицей 2.4 граф F –автомата Мура. 

 

Рис. 2.4. Граф автомата Мура

 

Матричный способ задания конечного автомата часто является более удобной формой. При этом матрица соединений автомата есть квадратная матрица C = [ c_ij ], строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода.

В случае F –автомата Мили элемент c _ij = x_k / y_s, стоящий на пересечении i -ой строки и j -го столбца, соответствует входному сигналу x_k, вызвавшему переход из состояния z_i в состояние z_j, и выходному сигналу y_s, выдаваемому при этом переходе. Для автомата Мили, рассмотренного выше, матрица соединений имеет вид

 

  .                                       (2.9)

 

Если переход из состояния z_i в состояние z_j происходит под действием нескольких сигналов, элемент матрицы c _ij представляет собой множество пар «вход-выход» для этого перехода, соединённых знаком дизъюнкции.

Для F –автомата Мура элемент c _ij = x_k / y_s равен множеству входных сигналов на переходе (z _i, z _j), а выход описывается вектором выходов, i -я компонента которого – выходной сигнал, отмечающий состояние z_i. Для автомата Мура, рассмотренного выше, матрица соединений и вектор выходов имеют вид

 

 ; .                             (2.10)

 

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

Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F –автомата состояние z_k называется устойчивым, если для любого входа x_i  Î X, для которого φ (z _k, x _i) = z_k имеет место ψ (z _k, x _i) = y_k. Таким образом, F –автомат называется асинхронным, если каждое его состояние z_k  Î Z устойчиво.

Ниже приведён пример асинхронного автомата Мура, заданного таблично (табл.2.5) и графически (рис.2.5).

Т а б л и ц а 2.5

Отмеченная таблица переходов асинхронного автомата Мура с тремя состояниями (z ₀, z ₁, z ₂), тремя входными (x ₁, x ₂, x ₃) и тремя выходными (₁ y, y ₂, y ₃) сигналами

xi	yk
	y1	y3	y2
	z0	z1	z2
x1	z2	z2	z2
x2	z1	z1	z2
x3	z0	z1	z 0

 

Рис. 2.5. Граф асинхронного автомата Мура

 

В таблице переходов асинхронного автомата некоторое состояние z_k стоит на пересечении строки x_i и столбца z_s (s ¹ k), и это состояние z_k обязательно должно встретиться в этой же строке в столбце z_k. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине z_k должна быть петля, отмеченная символами тех же входных сигналов.

Понятие F –автоматаявляется математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов, для которых характерно наличие дискретных состояний и дискретный характер работы во времени. Но широта применения не означает универсальности F –схем. Этот подход не пригоден для описания процессов в динамических системах с наличием переходных процессов, для формализации которых используются решётчатые функции и разностные уравнения, Z –преобразование и описание в пространстве состояний [14].

 

К дискретным детерминированным моделям относятся также сети Петри и алгоритмы.

2.3.2.2. Дискретно-стохастические модели (P –схемы)

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

Вероятностный автомат (англ. Probabilistic Automata) определяется как дискретный потактовый преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нём и может быть описано статистически [8].

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

Введём математическое понятие P – автомата, используя понятия, введённые для F – автомата. Рассмотрим множество G, элементами которого являютс