TVPS_posobie_13_06_2013

1.6.Репозиция асинхронного процесса

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

Определение. Репозиция АП Р=<S, F, I, R> – это эффективный асинхронный процесс

Р' = <S', F', I', R'>, где S'=I' R' SД, I' R; R' I; SД S= .

Таким образом, SД – это множество дополнительных ситуаций, отсутствующих в описании исходного АП. Отношение F' задает траектории переходов от ситуаций из I' (т.е. некоторых ситуаций из R) в ситуации из R' (т.е. в некоторые ситуации из I), возможно, через дополнительные ситуации из SД.

Если I'=R, R'=I, то репозиция называется полной. Если I= или R = , то репозиции не существует. В остальных случаях репозицию называют частичной.

Определение. Объединением АП P и его репозиции Р' будем называть АП

(Р Р')=<S SД, F'', I\R', R\I'>,

где F'' определяется следующим образом:

если si F sj, то si F'' sj и если si F' sj, то si F'' sj.

АП и его полная репозиция образуют автономный асинхронный процесс.

Определение. Полная репозиция простого АП называется

тривиальной.

21

Пример 7. На Рис. 8,а представлен АП, I={i1}, R={r1, r2}. На Рис. 8,б представлена его полная репозиция, I'={r1, r2}, R'={i1}, множество ситуаций содержит две дополнительные ситуации S'={r1, r2, s1Д , s2Д , i1}. На

Рис. 8,в представлена его частичная репозиция, I'={r1}, R'={i1}, множество ситуаций содержит одну дополнительную ситуацию

S'={r1, s1Д , i1}. На

Рис. 8,г представлен автономный АП, полученный объединением исходного АП и его полной репозиции.

Рис. 8. Репозиция АП

22

Конвейерный принцип обработки информации

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

Пример 8. На Рис. 9,а представлен непростой эффективный процесс. Пусть I={i1}, R={r1, r2, r3, r4, r5}, тогда получим шесть классов эквивалентности e(1)={i1}, e(2)={s1}, e(3)={s2}, e(4)={r1}, e(5)={r2, r3, r4}, e(6)={r5}. Для возобновления процесса воспользуемся репозицией, пусть она начинается с результанта r1 (дуга изображена с помощью прерывистой линии). Тогда в результате объединения исходного АП и его репозиции получим конвейер, который начинает обработку информации еще до того, как исходный АП завершит свою работу (Рис. 9,б).

i1

s1

s2

r1

r2

r3

r5

а

r4

i1

s1

s2

r1

r2

r3

r5

r4

б

Рис. 9. АП для иллюстрации конвейерного принципа обработки информации

23

1.7.Редукция асинхронного процесса

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

Введем понятие подпроцесса.

Определение. Подпроцессом АП Р=<S, F, I, R> по множеству ситуаций SП S назовем АП РП=<SП, FП, IП, RП>, где

IП=I SП,

RП=R SП,

skFПsp, если skFsp и sk, sp SП.

Пример 9. Рассмотрим граф АП (Рис. 10,а). Подпроцесс по множеству ситуаций SП={i1, s2, s3, s4, r1, r2, r3, r5} представлен на

Рис. 10,б.
i1	s1	s2	r1	r2	r3	r5
s4		s3			r4

а

i1

s2

r1

r2

r3

r5

s3

s4

б

Рис. 10. Пример АП и подпроцесса

24

Определение. Редукция АП Р=<S, F, I, R> по множеству ситуаций S* S – это подпроцесс, все ситуации которого принадлежат максимальным траекториям исходного АП, содержащимся в S* и начинающимся с инициаторов.

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

Пример 10. Рассмотрим граф АП (см. Рис. 10,а). Выполним редукцию данного АП по множеству ситуаций S*={i1, s2, s3, s4, r1, r2, r3, r5} (Рис. 11).

i1

r1

r2

r3

r5

s3

Рис. 11. Пример редукции АП

Свойства редукции АП:

1.Редукция эффективного процесса (если она существует) – всегда эффективный процесс, обратное неверно.

2.Редукция управляемого процесса (если она существует) – всегда управляемый процесс.

Упражнение. Докажите свойства редукции.

25

1.8.Структурирование ситуаций АП

Для АП, моделирующих реальные системы, ситуации часто описываются булевыми векторами фиксированной длины n (si1, si2, … , sin). ik-тая компонента вектора соответствует некоторому условию: если оно выполнено, то sik=1, в противном случае sik=0.

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

Пример 11. Пусть имеется горизонтальный ленточный конвейер (Рис. 12), на который подаются детали двух сортов – тяжелые и легкие. В зоне А конвейера расположены весы, сигнализатор которых срабатывает от тяжелой детали и не чувствителен к прохождению легкой. Легкие детали транспортируются без обработки к концу конвейера, где сваливаются в бункер С. При появлении тяжелой детали в зоне А конвейер останавливается, и рука манипулятора, находящаяся в исходном положении, производит захват детали. Затем привод манипулятора переносит тяжелую деталь в зону В, одновременно включается лента конвейера. В зоне В после срабатывания соответствующего сигнализатора отпускается захват, а затем осуществляется запуск привода манипулятора в направлении начального состояния. Далее выявляется новая тяжелая деталь, и процесс повторяется.

Рис. 12. Ленточный конвейер

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

26

p1=1 – лента конвейера в движении; p2=1 – тяжелая деталь в зоне А; p3=1 – лента конвейера остановлена;

p4=1 – рука манипулятора в исходном положении; p5=1 – рука манипулятора держит тяжелую деталь; p6=1 – работает привод руки в сторону зоны В; p7=1 – рука манипулятора в зоне В;

p8=1 – захват опущен;

p9=1 – работает привод руки в исходное положение.

Ситуации в этом примере представляют собой двоичные векторы (p1, p2, p3, p4, p5, p6, p7, p8, p9). Из 29 возможных векторов ситуациями являются только следующие 7 (не указанные компоненты

равны 0):

s1: p1=p4=p8=1	s5: p3=p6=p7=1
s2: p1=p2=p4=p8=1	s6: p1=p7=p8=1
s3: p2=p3=p4=p5=1	s7: p1=p8=p9=1

s4: p3=p5=p6=1

Описание процесса обнаружения, захвата и переноса тяжелой детали из зоны А в зону В включает ситуации s1, …, s6, инициатором естественно считать ситуацию s1 (I={s1}), а результантом s6 (R={s6}).

Последовательность s6s7s1 можно считать репозицией этого процесса

(I'={s6}, R'={s1}, SД={s7}).

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

В этом случае ситуация sj представима упорядоченной тройкой

sj=(xi(j), уk(j), zl(j)),

где xi(j) – значение входной компоненты, хi(j) Х, |X|=nX, 1≤i≤nX; yk(j) – значение выходной компоненты, yk(j) Y, |Y|=nY, 1≤k≤nY;

zl(j) – значение компоненты, не являющейся ни входной, ни выходной, zl(j) Z, |Z|=nZ, 1≤l≤nZ.

27

1.9.Диаграмма переходов

Определение. Диаграмма переходов (ДП) – это АП, ситуации которого представлены в виде булевых векторов одной и той же размерности n. Так же будем именовать и граф такого АП.

k-я компонента ситуации si называется возбужденной, если si F sj при некотором F и k-е компоненты ситуаций si и sj различны, в противном случае компонента называется устойчивой. Возбужденные компоненты помечаются символом «*».

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

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

1)компонента sik помечена символом «*»;

2)si F sj, причем sik =sjk;

3)компонента sjk символом «*» не помечена.

Пример 12. На Рис. 13,а представлена конфликтная ситуация si: si3=sj3=1, компонента si3 символом «*» помечена, а sj3 – нет. Аналогично и для Рис. 13,б, где ситуация si является конфликтной: si3=sj3=0, компонента si3 символом «*» помечена, а sj3 – нет.

Рис. 13. Пример конфликтной ситуации

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

Пример 13. Диаграмма переходов, соответствующая некоторому автономному АП, представлена на Рис. 14. Проверьте, является ли она полумодулярной.

28

Рис. 14. Пример диаграммы переходов

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

Упражнение. Выделите возбужденные компоненты в ситуациях ДП (Рис. 15). Проверьте, является ли ДП полумодулярной.

Рис. 15. ДП для выделения возбужденных компонент

1.10.Редукция диаграммы переходов

Редукцию ДП можно осуществить по множеству ситуаций, порожденному теми или иными компонентами ситуаций.

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

Пример 14. Пусть ДП имеет вид (Рис. 16), I={0100, 0010, 1011}, R={0011, 1010}.

29

Рис. 16. Пример ДП для выполнения редукции

Первые два элемента вектора полного состояния выберем в качестве входных компонент, последние два – в качестве выходных компонент. Определим редукцию ДП по множеству Х*={00, 10} входных компонент.

Сначала запишем множества S={0100, 0000, 0011, 0010, 0001, 1011, 1010}. На основе множества S получим множество S*, те состояния, которые не соответствуют множеству Х*={00, 10} в S* не попадут (в данном случае это состояние 0100):

S*={0000, 0011, 0010, 0001, 0001, 1011, 1010}.

Теперь выполним	редукцию	данного АП	по множеству S*
(Рис. 17).
0010	0011	1011	1010

Рис. 17. Результат редукции АП по множеству Х* значений входной компоненты

Аналогично определим редукцию данного АП по множеству Y*={00, 11} значений выходной компоненты.

На основе множества S получим множество S*, те состояния, которые не соответствуют множеству Y*={00, 11} в S* не попадут (в данном случае это состояния 0010, 0001, 1010):

S*={0100, 0000, 0011, 1011}

Редукция процесса Р по множеству Y*={00, 11} значений выходной компоненты представлена на Рис. 18.

Рис. 18. Результат редукции АП по множеству Y* значений выходной компоненты

30