1. Понятие дискретной динамической системы

• Название: 1. Понятие дискретной динамической системы
• Дата: 23.11.2018
• Размер: 0.51 Mb.
• Имя файла: tmp_4118-Otvety_k_ekzamenu_po_predmetu_Teoria_vychislitelnykh_pr.docx
• Тип: Документы; #57412
• страница: 3 из 15

6.Эффективный асинхронный процесс.

Эффективным называется АП <S, F, I, R>, удовлетворяющий следующим условиям:

1) I≠ , R≠;

2) каждая ситуация принадлежит некоторой максимальной траектории;

3) множества ситуаций I и S\(I R) не содержат циклов.

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

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

7.Управляемый асинхронный процесс.

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

8.Простой асинхронный процесс. Протокол простого АП.

Простой АП – ЭАП, удовлетворяющий условию: если s_iFs_j, то s_j∉I и s_i∉R (каждая максимальная траектория ПАП начинается единственным инициатором и заканчивается единственным результантом).

Протокол ПАП <S,F,I,R> - ПАП вида , R, F^П, I, R>, где s_iF^Пs_j, если s_iMs_j. Протокол простого АП удобно использовать для «входного-выходного» описания процесса.

Протокол можно рассматривать как ПАП, в котором за каждым инициатором непосредственно следует результант.

9.Репозиция АП. Автономный асинхронный процесс.

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

Репозиция АП Р= – это ЭАП: Р'=<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'' определяется следующим образом: (если s_iFs_j, то s_iF''s_j) и (если s_iF's_j, то s_iF''s_j).

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

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

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

Пример. На рис (а) представлен непростой эффективный процесс. Пусть 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 (дуга изображена с помощью прерывистой линии). Тогда в результате объединения исходного АП и его репозиции получим конвейер, который начинает обработку информации еще до того, как исходный АП завершит свою работу.