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

                       ПРЕДИСЛОВИЕ

     Повышение производительности вычислительных машин и систем
автоматики на их основе во многом определяется эффективностью
организации логического управления в системах, учитывающих реализацию
параллелизма на всех уровнях управления. Особенно это относится к
мультипроцессорным системам, в том числе к системам реального времени,
предназначенным для управления в робототехнических системах, когда
возникают задачи управления параллельными взаимодействующими
процессами и ресурсами. При создании таких систем одной из актуальных
задач является разработка формальных методов описания алгоритмов
управления    параллельными     взаимодействующими     процессами,   их
эквивалентных преобразований и методов их структурной реализации на
разных уровнях.
     Настоящее учебное пособие посвящено вопросам синтеза таких систем
логического управления, который базируется на использовании моделей
недетерминированных конечных автоматов (НДА) и их стандартной
аналитической форме представления в виде системы рекуррентных
канонических уравнений, описывающих все реализуемые в системе
управления частные события.
     В такой математической модели НДА в отличие от модели
детерминированного автомата (ДА) предложено использовать представления
функций переходов в автомате не в терминах состояний, а в терминах
частных событий, реализуемых в автомате. При этом каждому НДА может
быть поставлен в соответствие эквивалентный ему детерминированный
автомат, в котором состояния в общем случае будут представлены
совокупностью событий, имеющих место в один и тот же момент времени в
НДА. Т.е. ДА является частным случаем НДА, в котором не соблюдаются
условия однозначности переходов, проявляющейся в том, что под действием
одного и того же входного сигнала возможен переход от некоторого
исходного события к нескольким событиям, совокупность которых и будет
представлять собой одно из состояний ДА.
     Таким образом, «недетерминированность» автомата нельзя смешивать
со «случайностью», характеризующую вероятностный автомат, в котором
автомат может перейти в одно из следующих состояний с фиксированными
вероятностями [6].Указанная особенность модели НДА и определяет
«скрытый» в ней параллелизм.
     Такой подход к формализации сложных параллельных алгоритмов
управления с взаимодействующими ветвями позволяет создать набор
методов и средств для компактного формального описания алгоритмов
управления и их эквивалентных преобразований для построения возможных
реализаций с учетом требований повышения производительности,
надежности и уменьшения аппаратурных затрат.

                                                                      3