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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

205
y
b
=S
b
.
Решение задачи типа "5" Рассмотрим решение такой задачи на
примере, когда искомая цепочка будет z
1
z
1
z
2
z
3
, в алфавите
Z={z
1
,z
2
,z
3
,z
4
,z
5
,z
6
,z
7
,z
8
,z
9
,z
10
}, а игнорируемый символ при поиске z
10
. Тогда
цепочка в последовательности z
1
z
10
z
10
z
1
z
2
z
10
z
3
должна быть обнаружена.
Получить алгоритм решения этой задачи возможно следующим
образом:
- на языке РВАС записывается алгоритм поиска цепочки;
- по РВАС строится СКУ и СВФ;
- СКУ изменяется (корректируется) так, что алгоритм не меняет своего
состояния при поступлении на вход z
10
(символ игнорируется и как бы
«прозрачен» для цепочки).
Алгоритм поиска на языке РВАС запишется:
r(y)=S
0
z
1
z
1
z
2
z
3
.
Перейдем от РВАС к СКУ и СВФ и получим:
СКУ:
S
0
=1
r=S
1
z
3
S
1
=S
2
z
2
S
2
=S
3
z
1
S
3
=S
0
z
1
S
b
= S
0
z
b
S
b
СВФ:
y=r
y
b
=S
b
.
Корректируем СКУ и получаем:
S
0
=1
r=S
1
z
3
r&z
10
S
1
=S
2
z
2
s
1
&z
10
S
2
=S
3
z
1
S
2
&z
10
S
3
=S
0
z
1
S
3
z
10
S
b
=S
0
z
b
S
b
.
Решение задачи типа "6". При решении этой задачи алгоритм
разрабатывается в том же порядке как и в задачах 1-5. Но в СКУ добавляется
S
0
=0. Поэтому все символы в последовательности игнорируются до тех пока
по сигналу «извне» не установится маркер начала поиска (S
0
=1).
В заключение следует отметить, что хотя разработка алгоритмов
решения задач поиска велась для однопроцессорной системы
(последовательная реализация алгоритма), по своей сути полученные
алгоритмы уже являются параллельными. Но если задача поиска имеет 
      yb=Sb.
      Решение задачи типа "5" Рассмотрим решение такой задачи на
примере, когда искомая цепочка будет z1z1z2z3, в алфавите
Z={z1,z2,z3,z4,z5,z6,z7,z8,z9,z10}, а игнорируемый символ при поиске z10. Тогда
цепочка в последовательности z1z10z10z1z2z10z3 должна быть обнаружена.
      Получить алгоритм решения этой задачи возможно следующим
образом:
      - на языке РВАС записывается алгоритм поиска цепочки;
      - по РВАС строится СКУ и СВФ;
      - СКУ изменяется (корректируется) так, что алгоритм не меняет своего
состояния при поступлении на вход z10 (символ игнорируется и как бы
«прозрачен» для цепочки).
      Алгоритм поиска на языке РВАС запишется:
      r(y)=S0z1z1z2z3.
      Перейдем от РВАС к СКУ и СВФ и получим:
      СКУ:
      S0=1
      r=S1z3
      S1=S2z2
      S2=S3z1
      S3=S0z1
      S b= S 0zb  Sb
      СВФ:
      y=r
      yb=Sb.
      Корректируем СКУ и получаем:
      S0=1
      r=S1z3  r&z10
      S1=S2z2  s1&z10
      S2=S3z1  S 2&z10
      S3=S0z1  S3z10
      Sb=S0zb  Sb.
      Решение задачи типа "6". При решении этой задачи алгоритм
разрабатывается в том же порядке как и в задачах 1-5. Но в СКУ добавляется
S0=0. Поэтому все символы в последовательности игнорируются до тех пока
по сигналу «извне» не установится маркер начала поиска (S0=1).
      В заключение следует отметить, что хотя разработка алгоритмов
решения задач поиска велась для однопроцессорной системы
(последовательная реализация алгоритма), по своей сути полученные
алгоритмы уже являются параллельными. Но если задача поиска имеет
                                                                            205

Страницы