╥хъёЄ ЁхЇхЁрЄр: ёЄЁрэшЎр 1
Антик М.И. 11_03_91 МИРЭА АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА Алгоритмы этого типа являются следующим этапом обобщенияописаний вычислительных процессов. Теперь, по сравнению с ал-горитмами автоматного типа, на каждом шаге, помимо модифика-ции памяти, идентифицирующей шаг алгоритма, разрешается изме-нять любую другую память устройства локально (по частям) илиглобально (всю сразу). Устройство-исполнитель алгоритма этого типа будем назы-вать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат сосложно структурированной памятью - состоянием: часть памятииспользуется для идентификации шага алгоритма, остальная па-мять используется для запоминания промежуточных данных, вы-числяемых в процессе последовательного, по шагам, выполненияалгоритма. Такая модель вычислителя особенно удобна для рас-чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп-ность взаимодействующих синхронных автоматов, один из которыхназывается управляющим автоматом (УА), а объединение всех ос-тальных автоматов называется операционным автоматом (ОА). УА является исполнителем алгоритма автоматного типа, ко-торый входит составной частью в любой алгоритм процедурноготипа. Кроме того, УА инициирует действия отдельных шагов ал-горитма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритмапод управлением УА; кроме того, к ОА удобно отнести все вы-числения предикатных функций, оставив УА только анализ вычис-ленных предикатных значений. Прежде чем переходить к точным терминам, рассмотрим сле-дующиe примеры алгоритмов процедурного типа. Например, каноническое описание синхронного конечногоавтомата может быть интерпретировано (истолковано) как одно-шаговый алгоритм процедурного типа. █ ┌──────┐ │ │ ┌──V──V─────┐ │ │ B=FO(S,A) │ │ │ │ │ │ S:=FS(S,A)│ │ └─────┬─────┘ └─────────┘ Исполнитель этого алгоритма состоит только из ОА. Накаждом шаге этого алгоритма изменяется вся память устройства,поэтому управление памятью не требуется, идентифицировать ша-ги этого алгоритма не надо. Например, инкрементор с одноразрядным входом и однораз-рядным выходом может быть реализацией следующих преобразова-ний: █ █ p:=1 █ █ ┌────────┐ │ │ ┌─────V─V───────┐ │ │ (p:, b) = a+p │ │ └───────┬───────┘ └──────────┘ ОА, реализующий инкрементор в целом, будет следующим: ┌──┬─┐ a ──────────────────┤HS│S├────b ┌─┬─┐p │ │ │начальное значен.─┤S│T├──┤ │P├──┐ ├─┤ │ └──┴─┘ │ SYN ─────────/C│ │ │ ┌┤D│ │ │ │└─┴─┘ │ └───────────────┘Конечно, эта реализация совпадает с реализацией алгоритма ав-томатного типа, если состояние р1 кодируется 1, а состояниер0 - 0. Этот пример показывает,что до начала вычислений можетпотребоваться начальная установка памяти. На самом деле этонеобходимо было уже в алгоритмах автоматного типа, так каккод начального состояния требует предварительной установ-ки. Ограничимся здесь обозначением этой проблемы, а решениеее, связанное прежде всего с корректной синхронизацией ус-тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк-вивалентного автомату Мили , не обсуждалась простая возмож-ность ее реализации и на структурном уровне. Например, толькочто рассмотренный автомат Мили может быть преобразован в эк-вивалентный автомат Мура по одному из следующих вариантов: ┌┬─┬┐t┌──┬─┐ ┌──┬─┐ ┌┬─┬┐a ──┤│T│├┤HS│S├─b a ─────┤HS│S├─┤│T│├─b ─/┴┴─┴┘ │ │ │ │ │ │─/┴┴─┴┘ C │ │ │ C │ │ │ C ─/┬┬─┬┐p│ │ │ ─/┬┬─┬┐p│ │ │ ┌┤│T│├┤ │P├┐ ┌┤│T│├┤ │P├┐ │ └┴─┴┘ └──┴─┘│ │ └┴─┴┘ └──┴─┘│ └─────────────┘ └─────────────┘ При таких структурных преобразованиях проще истолковы-вать алгоритмы как процедурные. █ █ █ p:=1; t:=0 █ █ p:=1 █ █ █ ┌────────┐ │ ┌────────┐ │ │ ┌─────V─V───────┐ │ ┌─────V─V───────┐ │ │t:=a;(p:,b)=t+p│ │ │ (p , b):= a+p │ │ └───────┬───────┘ │ └───────┬───────┘ └──────────┘ └──────────┘ БЛОК-ТЕКСТ. Способ описания автоматного алгоритма посленекоторых дополнений может быть использован и для описанияалгоритмов в процедурной форме: Блок-текст состоит из трех частей: 1)- Описание переменных и начальных значений памяти. 2)- Описания функций и связей. Записываются любые функции ифункциональные связи (в том числе предикатные), не использу-ющие запоминания. Переменные из левой части операции присва-ивания таких функциональных описаний используются в блокахпроцедуры. 3)- Процедура, состоящая из блоков (микроблоков) операторныхи блоков переходов:- операторные - в скобках вида .....
