Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 203 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

203
S
2
=S
3
z
2
S
3
=S
0
z
3
S
k1
=S
1
z
3
S
k1
S
4
=S
5
z
1
S
5
=S
0
z
2
S
5
z
2
S
k2
=S
4
z
3
S
k2
S
6
=S
7
z
3
S
7
=S
8
z
2
S
7
z
2
S
8
=S
0
z
4
S
8
z
4
S
k3
=S
6
z
1
S
k3
z
1
S
k3
S
b
=S
0
z
b
S
b
СВФ:
y=S
k1
&S
k2
&S
k3
y
b
=S
b
.
Решение задачи типа "3". При разработке алгоритма решения этой
задачи наряду с замечаниями к задаче "2" нужно еще учесть и то, что заранее
неизвестен порядок, в котором появятся цепочки во входной
последовательности. Используем тот же пример что и в задаче 1, только
теперь необходимо найти хотя бы две цепочки из трех.
При переходе от РВАС к СКУ и СВФ проделаем тоже, что и в задаче 2,
но по иному выполним коррекцию СВФ.
СКУ:
S
0
=1
S
1
=S
2
z
1
S
1
z
1
S
2
=S
3
z
2
S
3
=S
0
z
3
S
k1
=S
1
z
3
S
k1
S
4
=S
5
z
1
S
5
=S
0
z
2
S
5
z
2
S
k2
=S
4
z
3
S
k2
S
6
=S
7
&z
3
S
7
=S
8
z
2
S
7
z
2
S
8
=S
0
z
4
S
8
z
4
S
k3
=S
6
z
1
S
k3
z
1
S
k3
S
b
=S
0
z
b
S
b
СВФ:
y=S
k1
S
k2
S
k1
S
k3
S
k2
S
k3
y
b
=S
b
. 
      S2=S3z2
      S3=S0z3
      Sk1=S1z3  Sk1
      S4=S5z1
      S5=S0z2  S5z2
      Sk2=S4z3  Sk2
      S6=S7z3
      S7=S8z2  S7z2
      S8=S0z4  S8z4
      Sk3=S6z1  Sk3z1  Sk3
      Sb=S0zb  Sb
      СВФ:
      y=Sk1&Sk2 &Sk3
      yb=Sb.
      Решение задачи типа "3". При разработке алгоритма решения этой
задачи наряду с замечаниями к задаче "2" нужно еще учесть и то, что заранее
неизвестен порядок, в котором появятся цепочки во входной
последовательности. Используем тот же пример что и в задаче 1, только
теперь необходимо найти хотя бы две цепочки из трех.
      При переходе от РВАС к СКУ и СВФ проделаем тоже, что и в задаче 2,
но по иному выполним коррекцию СВФ.
      СКУ:
      S0=1
      S1=S2z1  S1z1
      S2=S3z2
      S3=S0z3
      Sk1=S1z3  Sk1
      S4=S5z1
      S5=S0z2  S5z2
      Sk2=S4z3  Sk2
      S6=S7&z3
      S7=S8z2  S7z2
      S8=S0z4  S8z4
      Sk3=S6z1  Sk3z1  Sk3
      Sb=S0zb  Sb
      СВФ:
      y=Sk1Sk2  Sk1Sk3  Sk2Sk3
      yb=Sb.


                                                                         203

Страницы