Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

77-30569/292620 Алгоритмическая модель описания дискретного процесса функционирования системы

# 12, декабрь 2011
Файл статьи: Черн_6_P.pdf (242.37Кб)
автор: Черненький В. М.

УДК 004.436.4

МГТУ им. Н.Э. Баумана

chernen@bmstu.ru

 

Будем  полагать заданным параметрическое множество системы Q, состоящее из параметров qi (i=1..n). Если σ(qi) -множество значений, принимаемых параметром qi., то пространство состояний системы SQ определяется как .

Определим процесс Z в соответствии с [1] как четверку:

Z=< S, T, F, α >

где:

S - пространство состояний системы, определенное ранее;

T - множество моментов времени изменения состояний системы;

F – график процесса, определяемый как отображение T→S, причем это отображение должно быть функциональным (однозначным);

α- отношение линейного порядка на T.

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

Пространство состояний  объекта Ol определяется аналогично системе, как . Будем предполагать, что система всегда имеет полное разбиение на объекты. Таким образом: . Разбиение является непересекающимся, если . В противном случае разбиение произведено на пересекающиеся объекты.

Если задан процесс ZQ в системе, то процесс в объекте Ol может быть определен, как проекция процесса в системе ZQ на подпространство :

.

Пусть имеем объект Ol в системе Q. Тогда генерация процесса  может быть выполнена путем задания оператора  [1]:

,

(1)

где: ;

A - множество аргументов: AQ;

ω- случайное число.

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

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

если, то в объекте Ol развивается локальный процесс;

если, то процесс в Ol частично зависимый от системы;

если , то процесс в Ol полнозависимый от системы.

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

Рассмотрим два объекта Ol и Om в системе Q. Пусть , а процессы в них заданы следующими операторами:

.

В дальнейшем будем пользоваться постановками и результатами, изложенными в [2].

Если  и , то такие процессы и объекты будем называть не сцепленными в момент времени ti.

Если , то объект Om сцеплен с объектом Ol в момент времени ti. То же относится и к их процессам. Это означает, что для определения состояния объекта Om в момент времени ti, необходимо знание состояния объекта Ol в это же время. Обозначим отношение сцепления как Ol→Om. Если , то объект Ol сцеплен с объектом Om в момент времени ti: Om→Ol. Если одновременно  и , то объекты Om и Ol взаимно-сцеплены в момент времени ti: OmOl. При операторном способе описания процессов всегда нежелательна модель, приводящая к появлению взаимно - сцепленных объектов, поскольку возникающую неопределенность приходится раскрывать путем решения в общем случае систем нелинейных уравнений, что может привести к непреодолимым трудностям. В дальнейшем будем стремиться создавать модели, не приводящие к взаимному сцеплению объектов.

Не следует смешивать отношение сцепления и зависимости. Так, если Om→Ol и Ol→Ok, то вовсе не обязательно, чтобы Om→Ok. Таким образом, отношение сцепления не является транзитивным.

Если к отношению сцепления добавить полное транзитивное замыкание, то получим отношение зависимости. Т.е. если Ol зависит от Om, а Ok зависит от Ol, то Ok зависит и от Om. Таким образом, отношение сцепления можно определить как отношение непосредственной зависимости.

Конечно, всегда желательно иметь возможность задания процесса в виде единого оператора (1), однако это, как правило, либо затруднительно, либо невозможно. Ниже предлагается задавать оператор H в виде некоторой алгоритмической структуры.

Рассмотрим дискретный во времени процесс Z. Пространство состояний S может быть как непрерывным, так и дискретным. Поставим в соответствие каждой i-ой точке процесса (момент времени изменения состояния ti) некоторый оператор . Оператор  вычисляет значение состояния  в момент времени ti:

.

Оператор  описывает вычисление только одной i-й точки процесса Z. В силу этого условия будем в дальнейшем называть этот оператор элементарным.

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

.

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

а) независимостью: может существовать самостоятельно без операторов;

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

в) инициативностью: в момент сцепления инициатора с оператором происходит выполнение (инициирование) элементарного оператора, что соответствует вычислению нового состояния процесса.

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

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

а) указание момента времени сцепления инициатора с оператором ;

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

в) комбинированная форма, включающая варианты а) и б).

Таким образом:

,

где: hуi - оператор условия сцепления;

hti - оператор временного условия (соответствует варианту а);

hлi - оператор логического условия (соответствует варианту б);

ht,лi - оператор комбинированного условия (соответствует варианту в).

Расширим понятие элементарного оператора, добавив к нему помимо оператора hci оператор hуi. Таким образом, определим элементарный оператор hi, как двойку:

.

При сцеплении инициатора с элементарным оператором hi происходит мгновенное выполнение его обеих составных частей: выполнение hci позволяет вычислить новое состояние si процесса Z, а выполнение оператора hуi дает возможность определить момент времени, либо логическое условие сцепления инициатора со следующим элементарным оператором hi+1.

Теперь можно определить понятие алгоритмической модели процесса (в дальнейшем АМП), в виде тройки:

АМП = ,

где: - множество элементарных операторов;

β- линейный порядок на ;

I- инициатор.

Следует обратить внимание, что АМП содержит один и только один инициатор, т.е. каждому процессу соответствует один инициатор. В этом смысле инициатор является представителем процесса, при его потери либо отсутствии развитие процесса прекращается. Если в системе развивается одновременно m процессов, то в модели присутствует m инициаторов.

Линейную последовательность элементарных операторов назовем треком TR:

.

Тогда можно АМП определить также как двойку:

АМП=<TR,I>.

Процесс задан, если задан трек элементарных операторов и инициатор.

 

Понятие структуры

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

Структурой назовем свертку трека TR по отношению эквивалентности элементарных операторов.

Пример.

Пусть задан некоторый трек TR (рис. 1).

Рисунок 1. Пример трека

 

Пусть отношение эквивалентности элементарных операторов имеет вид:

.

Тогда структура имеет вид графа (рис. 2).

Рисунок 2. Свертка трека в структуру

 

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

Рисунок 3. Обозначение навигационного оператора

 

Если навигационный оператор обозначить, как показано на рис. 3, то структура из вышеописанного примера будет иметь вид (рис.4):

Рисунок 4. Структура с включением навигационных операторов

 

Здесь операторы h1, h2, h4 являются представителями своего класса эквивалентности. Как видно, после операторов h1 и h2 стоят навигационные операторы hн1 и hн2, в то время как после оператора h4 нет необходимости в использовании навигационного оператора. Навигационный оператор используется также и для организации циклов (оператор hн2, выход 1).

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

Если навигационный оператор включить в состав элементарного оператора, то определение элементарного оператора в составе структуры можно представить в виде:  h=<hc,hу,hн>.

Особый интерес представляет случай, когда структура имеет вид полнодоступного графа (рис. 5).

Рисунок 5. Пример полнодоступной структуры

 

Здесь возможна генерация любого трека на базе эквивалентных классов элементарных операторов h1, h2, h3.

Выполним операцию объединения вершин графа. Для этого объединим все навигационные операторы hн1, hн2, hн3 в один hн . Тогда получим граф, изображенный на рисунке 6.

Рисунок 6. Свертка полнодоступной структуры

 

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

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

 

Литература

1. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. - М.: Сов.Радио, 1973. - 438 с.

2. Черненький В.М. Процессно - ориентированная концепция системного моделирования АСУ: Дис...док. тех. наук.-М.,2000.-350с.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)