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

некоторые допущения. В действительности эффективность будет ниже
величины полученной при помощи этой формулы. Из формулы также видно,
что если Тобраб намного меньше Тсчит, то эффективность системы равна 1, т.е.
такой алгоритм работы многопроцессорной системы будет неэффективен.
      В заключение сделаем замечания по практической аппаратной
реализации алгоритма. Аппаратная реализация отлаженного алгоритма в
этом случае чрезвычайно проста, если в качестве элементарного автомата
памяти использовать D триггер. При этом количество триггеров в схеме
соответствует числу уравнений НД СКУ плюс количество начальных
состояний в алгоритме. Каждое уравнение будет представлять собой
функцию возбуждения соответствующего ему триггера. Таким образом будет
получено описание схемы цифрового устройства на входном языке, которое
может быть использовано в системах автоматизированного проектирования
(CAD/CAM).

                  Контрольные вопросы к главе 7.
     1.    Каковы алгоритмы поиска цепочек символов во входной
последовательности при решении следующих задач:
     а) поиск наличия любой из нескольких заданных цепочек символов в
произвольной входной последовательности символов?
     б) поиск наличия всех заданных цепочек символов в произвольной
входной последовательности символов?
     в) поиск наличия заданного количества любых из нескольких заданных
цепочек символов в произвольной входной последовательности символов?
     г) поиск наличия нескольких заданных цепочек символов, у которых
префикс и суффикс одинаковы, а корни различны в произвольной входной
последовательности символов?
     д) поиск наличия заданной цепочки с использованием маскирования
некоторых её символов в произвольной входной последовательности
символов?
     е) поиск наличия заданной цепочки символов в произвольной входной
последовательности символов, когда этот поиск должен быть начат по
сигналу извне?
     2.    Как можно динамически управлять алгоритмом поиска с
использованием маркера начала поиска?
     3.    Какие этапы содержит предложенная методика проектирования
параллельных алгоритмов?
     4.    Почему локализация коммуникаций позволяет сократить время
выполнения алгоритма?
     5.    Какие стратегии используются при распределении задач по
процессорам?



                                                                         229