Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

  • Просмотров 4093
  • Скачиваний 387
  • Размер файла 52
    Кб

Антик М.И. 11_03_91 МИРЭА АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА Алгоритмы этого типа являются следующим этапом обобщения описаний вычислительных процессов. Теперь, по сравнению с ал- горитмами автоматного типа, на каждом шаге, помимо модифика- ции памяти, идентифицирующей шаг алгоритма, разрешается изме- нять любую другую память устройства локально (по частям) или глобально (всю сразу). Устройство-исполнитель

алгоритма этого типа будем назы- вать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации шага алгоритма, остальная па- мять используется для запоминания промежуточных данных, вы- числяемых в процессе последовательного, по шагам, выполнения алгоритма. Такая модель вычислителя особенно удобна для рас-

чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп- ность взаимодействующих синхронных автоматов, один из которых называется управляющим автоматом (УА), а объединение всех ос- тальных автоматов называется операционным автоматом (ОА). УА является исполнителем алгоритма автоматного типа, ко- торый входит составной частью в любой алгоритм процедурного типа. Кроме того, УА

инициирует действия отдельных шагов ал- горитма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритма под управлением УА; кроме того, к ОА удобно отнести все вы- числения предикатных функций, оставив УА только анализ вычис- ленных предикатных значений. Прежде чем переходить к точным терминам, рассмотрим сле- дующиe примеры алгоритмов процедурного типа. Например, каноническое описание синхронного

конечного автомата может быть интерпретировано (истолковано) как одно- шаговый алгоритм процедурного типа. █ ┌──────┐ │ │ ┌──V──V─────┐ │ │ B=FO(S,A) │ │ │ │ │ │ S:=FS(S,A)│ │ └─────┬─────┘ └─────────┘ Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма