Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 10 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

10
s
к2
=s
p
(z
2
{z
2
}z
1
z
3
) - для корня 2
s
к3
=s
p
(z
4
{z
4
}z
2
{z
2
}z
3
z
1
{z
1
}) - для корня 3
r(y)=s
r
z
2
{z
1
}z
3
- для суффикса.
Для каждого уравнения перейдем от РВАС к СКУ и объединим их. Получим:
СКУ:
s
0
=1
Для префикса ( маркер начала поиска s
0
):
s
p
=s
9
&z
3
; s
9
=s
10
&z
2
; s
10
=s
11
&z
1
; s
11
=s
0
&z
1
;
Для корней ( маркер начала поиска s
p
):
s
1
=s
2
&z
1
∨
s
1
&z
1
; s
2
=s
3
&z
2
; s
3
=s
p
&z
3
; s
k1
=s
1
&z
3
;
s
4
=s
5
&z
1
; s
5
=s
p
&z
2
∨
s
5
&z
2
; s
k2
=s
4
&z
3
;
s
6
=s
7
&z
3
; s
7
=s
8
&z
2
∨
s
7
&z
2
; s
8
=s
p
&z
4
∨
s
8
&z
4
;
s
k3
=s
6
&z
1
∨
s
k3
&z
1
;
Для суффикса ( маркеры начала поиска s
k1
, s
k2
, s
k3
):
r=s
12
&z
3
; s
12
=(s
k1
∨
s
k2
∨
s
k3
)&z
2
∨
s
12
&z
1
;
Для входного символа "bottom":
s
b
=s
0
&bottom
∨
s
b
;
СВФ:
y=r; 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
&bottom
∨
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
&bottom
∨
s
b
.
Решение задачи типа "6". При решение этой задачи алгоритм разрабатывается в том
же порядке как и в задачах 1-5.
Но в СКУ добавляется s
0
=0. Поэтому все символы во входной последовательности игно-
рируются до тех пока по сигналу "извне" не установится маркер начала поиска (s
0
=1). 
  sк2=sp(z2{z2}z1z3) - для корня 2
  sк3=sp(z4{z4}z2{z2}z3z1{z1}) - для корня 3
  r(y)=srz2{z1}z3 - для суффикса.
  Для каждого уравнения перейдем от РВАС к СКУ и объединим их. Получим:
  СКУ:
  s0=1
  Для префикса ( маркер начала поиска s0):
  sp=s9&z3;      s9=s10&z2; s10=s11&z1; s11=s0&z1;
  Для корней ( маркер начала поиска sp):
  s1=s2&z1 ∨ s1&z1;           s2=s3&z2;                 s3=sp&z3; sk1=s1&z3;
  s4=s5&z1;                   s5=sp&z2 ∨ s5&z2;         sk2=s4&z3;
  s6=s7&z3;                               ∨
                              s7=s8&z2 s7&z2;           s8=sp&z4 ∨ s8&z4;
  sk3=s6&z1 ∨ sk3&z1;
  Для суффикса ( маркеры начала поиска sk1, sk2, sk3):
  r=s12&z3;             s12=(sk1 ∨ sk2 ∨ sk3)&z2 ∨ s12&z1;
  Для входного символа "bottom":
  sb=s0&bottom ∨ sb;
  СВФ:
  y=r;           yb=sb.
  Решение задачи типа "5" Рассмотрим решение такой задачи на примере, когда иско-
мая цепочка будет z1z1z2z3, в алфавите Z={z1,z2,z3,z4,z5,z6,z7,z8,z9,z10}, а игнорируемый
символ при поиске z10. Тогда цепочка во входной последовательности z1z10z10z1z2z10z3
должна быть обнаружена.
  Получить алгоритм решения этой задачи возможно следующим образом:
  - на языке РВАС записывается алгоритм поиска цепочки

  - по РВАС строится СКУ и СВФ;

  - СКУ изменяется (корректируется) так, что алгоритма не меняет своего состояния при
        поступлении на вход z10 (символ игнорируется и как бы "прозрачен" для цепоч-
        ки).

  Алгоритм поиска на языке РВАС запишется:
  r(y)=s0z1z1z2z3.
  Перейдем от РВАС к СКУ и СВФ и получим:
  СКУ:
  s0=1; r=s1&z3;           s1=s2&z2; s2=s3&z1; s3=s0&z1;
  sb=s0&bottom sb∨
  СВФ:
  y=r;           yb=sb.
  Корректируем СКУ и получаем:
  s0=1; r=s1&z3 ∨ r&z10; s1=s2&z2 ∨ s1&z10;          s2=s3&z1 ∨ s2&z10;
  s3=s0&z1 ∨ s3&z10;       sb=s0&bottom ∨ sb.
  Решение задачи типа "6". При решение этой задачи алгоритм разрабатывается в том
же порядке как и в задачах 1-5.
Но в СКУ добавляется s0=0. Поэтому все символы во входной последовательности игно-
рируются до тех пока по сигналу "извне" не установится маркер начала поиска (s0=1).


                                           10

Страницы