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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

201
4) Поиск в последовательности начинается после поступления сигнала
начать поиск «извне» или наступлении определенного события "внутри"
(например, прочитано определенное количество символов в
последовательности и т.п.)
Рассмотрим, как можно решить задачи 1-5 и подзадачи 1-4. Будем
рассматривать задачи идентификации только на обнаружение, т.к. решение
задач локализации полностью идентично, только с «зеркальным»
отражением.
7.1.2. Разработка алгоритмов решения задач
распознавания цепочек-образов
Решение задачи типа "1". Алгоритм решения этой задачи (без учета
поступления символа z
t
) можно непосредственно записать на языке РВАС.
Например, необходимо определить есть ли во входной последовательности
любая из трех следующих цепочек:
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
})
При переходе от РВАС к СКУ и СВФ в соответствие с алгоритмом
приведенным ранее, преобразуем выражение 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
      4) Поиск в последовательности начинается после поступления сигнала
начать поиск «извне» или наступлении определенного события "внутри"
(например,    прочитано     определенное    количество     символов    в
последовательности и т.п.)
      Рассмотрим, как можно решить задачи 1-5 и подзадачи 1-4. Будем
рассматривать задачи идентификации только на обнаружение, т.к. решение
задач локализации полностью идентично, только с «зеркальным»
отражением.


    7.1.2.  Разработка     алгоритмов                                   решения   задач
распознавания цепочек-образов

     Решение задачи типа "1". Алгоритм решения этой задачи (без учета
поступления символа zt) можно непосредственно записать на языке РВАС.
Например, необходимо определить есть ли во входной последовательности
любая из трех следующих цепочек:
      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})
       При переходе от РВАС к СКУ и СВФ в соответствие с алгоритмом
приведенным ранее, преобразуем выражение 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=S2z1  S1z1
      S2=S3z2
      S3=S0z3
      Sk1=S1z3
      S4=S5z1

                                                                                     201

Страницы