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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

8
4) Поиск во входной последовательности начинается после поступления сигнала на-
чать поиск "извне" или наступлении определенного события "внутри" (например, про-
читано определенное количество символов в последовательности и т.п.)
Рассмотрим как можно решить задачи 1-5 и подзадачи 1-4. Будем рассматривать зада-
чи идентификации только на обнаружение, т.к. решение задач локализации полностью
идентично, только с "зеркальным" отражением.
1.3 Разработка алгоритмов задач идентификации
Решение задачи типа "1". Алгоритм решения этой задачи (без учета поступления
символа "bottom") можно непосредственно записать на языке РВАС. Например необхо-
димо определить есть ли во входной последовательности любая из трех следующих цепо-
чек:
1) z
3
z
2
z
1
... z
1
z
3
; 2) z
2
... z
2
z
1
z
3
; 3) z
4
... z
4
z
2
... z
2
z
3
z
1
... z
1,
где z
i
... z
i
повторение символа z
i
любое число раз, но не менее одного. При обнару-
жении любой цепочки должен быть выработан выходной сигнал y.
Тогда на языке РВАС алгоритм поиска запишется:
r(y)=s
0
(z
3
z
2
z
1
{z
1
}z
3
∨
z
2
{z
2
}z
1
z
3
∨
z
4
{z
4
}z
2
{z
2
}z
3
z
1
{z
1
})
Для перехода от РВАС к СКУ и СВФ в соответствие с алгоритмом приведенным в
1.1, преобразуем выражение r в следующую систему из трех уравнений, где s
k1
, s
k2
, s
k3
со-
бытия, появляющиеся при обнаружении цепочек 1, 2, 3 соответственно:
s
k1
(y)=s
0
z
3
z
2
z
1
{z
1
}z
3
s
k2
(y)=s
0
z
2
{z
2
}z
1
z
3
s
k3
(y)=s
0
z
4
{z
4
}z
2
{z
2
}z
3
z
1
{z
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
4
=s
5
&z
1
; s
5
=s
0
&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
0
&z
4
∨
s
8
&z
4
;
s
k3
=s
6
&z
1
∨
s
k3
&z
1
;
СВФ:
y=s
k1
∨
s
k2
∨
s
k3
Для поиска цепочек в любом месте входной последовательности необходимо уста-
навливать маркер начала поиска перед приемом каждого следующего символа. Поэтому в
СКУ нужно добавить уравнение: s
0
=1, а чтобы учесть поступление символа "bottom" не-
обходимо добавить еще одно уравнение в СКУ и одно в СВФ:
СКУ -
s
0
=1
s
b
=s
0
&bottom
∨
s
b
;
СВФ - y
b
=s
b
.
При практической реализации алгоритма необязательно повторять переходы из s
b
в
s
b
. Для программной реализации достаточно будет остановить выполнение программы, а
при аппаратной реализации блокировать прохождение синхросигнала на элементы памя-
ти.
Решение задачи типа "2". Получить алгоритм решения этой задачи возможно сле-
дующим образом: 
  4) Поиск во входной последовательности начинается после поступления сигнала на-
   чать поиск "извне" или наступлении определенного события "внутри" (например, про-
   читано определенное количество символов в последовательности и т.п.)

   Рассмотрим как можно решить задачи 1-5 и подзадачи 1-4. Будем рассматривать зада-
чи идентификации только на обнаружение, т.к. решение задач локализации полностью
идентично, только с "зеркальным" отражением.
                      1.3 Разработка алгоритмов задач идентификации
      Решение задачи типа "1". Алгоритм решения этой задачи (без учета поступления
символа "bottom") можно непосредственно записать на языке РВАС. Например необхо-
димо определить есть ли во входной последовательности любая из трех следующих цепо-
чек:
      1) z3z2z1 ... z1z3; 2) z2 ... z2z1z3; 3) z4 ... z4z2 ... z2z3z1 ... z1,
      где zi ... zi повторение символа zi любое число раз, но не менее одного. При обнару-
жении любой цепочки должен быть выработан выходной сигнал y.
      Тогда на языке РВАС алгоритм поиска запишется:
r(y)=s0(z3z2z1{z1}z3 ∨ z2{z2}z1z3 ∨ z4{z4}z2{z2}z3z1{z1})
      Для перехода от РВАС к СКУ и СВФ в соответствие с алгоритмом приведенным в
1.1, преобразуем выражение r в следующую систему из трех уравнений, где sk1, sk2, sk3 со-
бытия, появляющиеся при обнаружении цепочек 1, 2, 3 соответственно:
      sk1(y)=s0z3z2z1{z1}z3
      sk2(y)=s0z2{z2}z1z3
      sk3(y)=s0z4{z4}z2{z2}z3z1{z1}.
      Дальнейшие преобразования дадут следующие СКУ и СВФ:
      СКУ:
      s1=s2&z1 ∨ s1&z1; s2=s3&z2 ;                    s3=s0&z3 ;              sk1=s1&z3;
      s4=s5&z1;           s5=s0&z2 ∨ s5&z2; sk2=s4&z3;
      s6=s7&z3;           s7=s8&z2 ∨ s7&z2; s8=s0&z4 ∨ s8&z4;
      sk3=s6&z1 ∨ sk3&z1;
      СВФ:
      y=sk1 ∨ sk2 ∨ sk3
      Для поиска цепочек в любом месте входной последовательности необходимо уста-
навливать маркер начала поиска перед приемом каждого следующего символа. Поэтому в
СКУ нужно добавить уравнение: s0=1, а чтобы учесть поступление символа "bottom" не-
обходимо добавить еще одно уравнение в СКУ и одно в СВФ:
      СКУ -
      s0=1
      sb=s0&bottom ∨ sb;
      СВФ - yb=sb.
      При практической реализации алгоритма необязательно повторять переходы из sb в
sb. Для программной реализации достаточно будет остановить выполнение программы, а
при аппаратной реализации блокировать прохождение синхросигнала на элементы памя-
ти.
    Решение задачи типа "2". Получить алгоритм решения этой задачи возможно сле-
дующим образом:



                                            8

Страницы