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

      3) Поиск заданного количества искомых цепочек т.е. например,
ищутся 5 цепочек, а результат поиска может быть положительным, если
будет найдены хотя бы 3 из них. Здесь дополнительная трудность при поиске
состоит в том, что заранее невозможно определить порядок, в котором они
будут находиться в последовательности. Если же искать их многократным
просмотром последовательности, то будут существенные потери времени.
      4) Поиск нескольких цепочек, у которых префикс и суффикс
одинаковы, а корни различны. Если префикс обозначить через А, суффикс
через С, а корни через В1,В2,В3, то на языке РВАС алгоритм поиска запишется
как: r(у)=А&(В1  В2  В3)&С. Можно, конечно, выполнить преобразование,
раскрыв скобки, но тогда суффиксы и префиксы уйдут в каждую из трех
цепочек, что увеличит размерность алгоритма.
      5) Поиск цепочек, когда в последовательности некоторые символы
являются «прозрачными» (т.е. их как бы нет). Например, игнорирование
знаков препинания в тексте или определенных байтовых комбинаций в
двоичных файлах.
      6) Когда поиск в последовательности начинается по сигналу
«извне», а до того времени на каждом шаге осуществляется просто просмотр
очередного символа последовательности. Например, когда поиском
управляет внешняя среда или когда нужно найти цепочку после пропуска
определенного количества символов входной последовательности.
      Отметим, что начальное состояние S0 НДА, которое назовем маркером
начала поиска, имеет очень существенное значение. Маркер позволяет
динамически управлять процессом поиска без изменения самого алгоритма
поиска (программная или аппаратная реализация не меняется), что
обеспечивает гибкость при реализации алгоритма. Например, не меняя
алгоритма, а управляя только маркером можно получить решение
следующих подзадач, которые могут являться составной частью задач 1-6.
      1) Не начинается ли последовательность с искомой цепочки, т е. самый
первый символ последовательности совпадает с первым символом цепочки.
Такая задача решается установкой маркера начала поиска (S0=1) перед
приемом первого символа последовательности и сбросом его (S0=0 ) после
приема первого символа.
      2) Классическая задача поиска, когда последовательность может
содержать цепочки в любом месте между "top" и "bottom". Эта задача
решается установкой маркера (S0=1) перед приемом первого символа
последовательности, без последующего сброса (поиск искомых цепочек
начинается с каждого очередного символа).
      3) Поиск в последовательности начинается после обнаружения в ней
определенного символа или символов (точки, отмечающей конец
предложения и т.п.). Эта задача решается установкой маркера после
поступления этого символа, без последующего сброса.


                                                                        200