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

Представлен основной математический аппарат, связанный с формальным представлением параллельных управляющих алгоритмов в виде модели недетерминированных автоматов (НДА) и эквивалентные преобразования этой модели. В качестве основной модели НДА принята система рекуррентных канонических уравнений, описывающих все реализуемые в системе управления частные события и язык граф-схем алгоритмов с параллельными ветвями. Эквивалентные преобразования модели НДА базируются на использовании операций детерминизации, минимизации, кодирования и композиции НДА. Рассмотрены методы формального описания алгоритмов взаимодействия параллельных процессов, связанных с их синхронизацией и обменом информацией. Формальные представления алгоритмов взаимодействия процессами иллюстрируются на базе решения "классических" задач управления процессами: обращение к общему ресурсу для n процессов, производители-потребители, читатели-писатели, обедающие философы, а также задач идентификации языков. Рассмотрены также методы структурной реализации параллельных алгоритмов.Пособие подготовлено на кафедре "Вычислительная техника" ПГУ, предназначено для студентов специальности 220100 при изучении ими дисциплин "Теория автоматов" и "Недетерминированные автоматы в системах логического управления", а также может быть использовано студентами всех специальностей направления "Информатика и вычислительная техника" при изучении ими родственных дисциплин.