Интерпретационные методы в теории алгоритмических алгебр

Одной из определяющих тенденций развития науки является ее математизация, охватывающая, в частности, теорию компьютерных вычислений, в том числе теоретическое программирование. В этой связи особо следует отметить интенсивное проникновение в компьютерную науку идей и методов дискретной математики, алгебры и математической логики, успешное применение теории автоматов, формальных языков и грамматик как для сугубо теоретических, так и для практических целей, в частности, разработки систем программирования, основанных на языках высокого и сверхвысокого уровня, развитие средств логического программирования и т. д.

Особый вклад в развитие данной проблематики вносит алгебраический аппарат, на основе которого создан целый ряд теоретических и практических работ, среди которых особое место занимают работы, связанные с исследованием и применением идей теории алгоритмических алгебр. Основным объектом данной теории является универсальная алгебра алгоритмов той или иной сигнатуры, операции которой моделируют различные программистские конструкции, а цельюисследование математических свойств данной алгебры и связанных с ней объектов, в частности, установление взаимосвязей этих объектов с другими разделами математики и математической кибернетики.

Основы данной теории была заложены В. М. Глушковым в работах [17, 18], в которых впервые было введено и исследовано понятие алгоритмической алгебры (иначе — алгебры алгоритмов или системы алгоритмических алгебр), На основе этого понятия В. М. Глушковым и его учениками и последователями был получен целый ряд результатов как теоретического, так и прикладного характера (см., в частности, работы [19−22, 27, 30- 33, 35, 43−46, 56, 105−110, 112−115]). Отметим лишь некоторые из результатов, которые имеют наиболее тесную связь с данной диссертационной работой.

Одним из основных результатов теории алгоритмических алгебр следует считать теорему В'.М.Глушкова о том, что функционирование конечного дискретного преобразователя (взаимодействующих автоматов, управляющего и операционного) может быть описано регулярной схемой оператора алгоритмической алгебры, однозначно определяемой по данному преобразователю [18]. Этот результат указывает, в частности, на тесную взаимосвязь алгоритмических проблем, формулируемых для алгоритмических алгебр, с проблемами эквивалентности дискретных преобразователей. A.A.Летичевским был получен ряд результатов по алгоритмической разрешимости проблемы эквивалентности автоматов относительно полугрупп [43−45]. Разрешимость алгоритмической проблемы тождества слов и существование полной системы аксиом для специального класса алгебр алгоритмов (алгебр с замкнутыми условиями или S-алгебр) была установлена Г. Е. Цейтлиным в работе [107]. Аналогичный результат для специального класса алгебр недетерминированных алгоритмов (S (Н)-алгебр) был получен Ю. А. Ющенко [115]. А. А. Летичевским была установлена связь алгоритмических алгебр с теорией схем программ [40], что позволило рассматривать проблематику алгебр алгоритмов в общем контексте теории дискретных систем [31]. В работах [12, 4 6, 105] рассмотрены алгебры структур данных и их связь с проблемами проектирования программ.

Важным этапом в развитии теории и приложений алгоритмических алгебр явилось издание монографии В.М. ГЛушкова, Г. Е. Цейтлина,.

E.JI. Ющенко «Алгебра. Языки. Программирование» (Киев: Наук, думка, 1974. — 328 е.- 2-е изд., перераб., 1978. — 320 е.- 3-е изд., перераб. и доп., 1989. — 376 е.- Berlin: Acad.-Verl., 1980, -322 s,), посвященной фундаментальным исследованиям, связанным с применением аппарата общей алгебры в программировании.

Сфера приложений теории алгоритмических алгебр чрезвычайно обширна и охватывает параллельную обработку данных на многопроцессорных машинных комплексах [7, 20, 33], проектирование вычислительных систем [30], проектирование и синтез схем программ'[109−110, 112−113], анализ и оптимизацию схем программ [106], структуры данных [105], специализированные системы автоматизированного проектирования [111, 113], формы представления знаний [108], моделирование технологических процессов [3, 4, 111], а также’ряд других проблем специального характера. Эти приложения опираются и, в свою очередь, стимулируют такие теоретические исследования, которые призваны объяснить процессы, задаваемые регулярными схемами операторов и условий алгоритмических алгебр, а также сделать их исследование эффективным.

Следует заметить, что одной из основных задач, с необходимостью решения которых связано возникновение алгоритмических алгебр, являлась задача эквивалентных преобразований микропрограмм (регулярных схем)[17], которая удовлетворительным образом не решена до сих пор. Поэтому весьма актуальным является исследование алгоритмических проблем тождества для тех или иных классов алгебр алгоритмов.

Теорема В. М. Глушкова о представлении дискретных преобразователей регулярными схемами устанавливает возможность (и способ) формального описания вычислений, задаваемых вычислительным устройством (дискретным преобразователем) в алгебраических терминах. Вместе с тем, обратное утверждение для рассмотренного класса преобразователей не имеет места. Поэтому актуальными являются задачи построения таких классов дискретных преобразователей, в котором указанная теорема не только верна, но и допускает обращение. Не менее важными являются задачи теоретического исследования способов организации последовательных и параллельных вычислений, задаваемых регулярными схемами операторов и обладающих теми или иными полезными в практическом отношении свойствами.

Решение этих и целого ряда других задач крайне затруднено сложностью основного объекта — алгоритмической алгебры, сигнатура которой включает в себя до десятка специфических операций и которая далеко не всегда позволяет применить для своего исследования хорошо разработанный аппарат или же непосредственно использовать результаты общетеоретического характера. Поэтому проблема разработки как специальных методов исследования алгоритмических алгебр, так и таких методов, которые позволяли бы эффективно использовать результаты известных математических теорий, представляется весьма актуальной. Именно к их числу относятся интерпретационные методы, т. е. такие, использование которых позволяет заменить (интерпретировать) исходный объект в некотором смысле изоморфным или же эквивалентным ему формальным объектом другого класса со свойствами, позволяющими достаточно эффективно выполнить исследование и перенести полученные результаты на исходный объект.

Объектом исследования в диссертации являются алгебры (детерминированных и недетерминированных) алгоритмов и связанные с ними объекты.

Целью диссертационной работы является разработка и применение интерпретационных методов исследования алгоритмических алгебр.

Для достижения цели исследования в диссертации решены следующие задачи:

— разработан метод редукции алгебр детерминированных и недетерминированных алгоритмов к единому, более простому объекту алгебре П-алгоритмов;

— введено и исследовано понятие О.-языка, обобщающее формальный язык, разработан метод изучения £2-языков путем их сведения к унифицированным объектам, так называемым точным П-языкам;

— введены понятия и разработан метод исследования свободных алгебр й-алгоритмов, детерминированных и недетерминированных алгоритмов, основанный на точных П-языках;

— разработан общий метод исследования специального класса П-языков — формальных языков над алфавитом, интерпретированным в булевой алгебре;

— разработан метод изучения регулярных языков над алфавитом, интерпретированным в булевой алгебре, в том числе алгоритм проверки таких языков на совпадение;

— разработан метод классификации языков над алфавитом, интерпретированным в булевой алгебре;

— разработан аппарат динамических сетевых моделей специального вида (генераторов дискретных процессов, ГДП) и, на его основе, — метод моделирования регулярных схем операторов алгоритмических алгебр в виде ГДП;

— разработан метод многоуровневого представления алгоритмических алгебр;

— разработаны методы формального описания дискретных преобразователей в терминах регулярных схем (с настройкой) операторов алгоритмических алгебр;

— разработан метод исследования случайных вычислительных процессов, задаваемых однородными цепями Маркова с конечным числом состояний, интерпретируемых как элементы марковской алгоритмической алгебры — стохастического аналога алгебры алгоритмов.

Метода исследования основаны на применении общей теории универсальных алгебр, теории полугрупп, решеток, булевых алгебр, теории формальных языков и грамматик, абстрактных автоматов, а также теории случайных процессов.

Научная новизна полученных результатов состоит в следующем.

1. Показано, что свойства любой алгебры детерминированных или недетерминированных алгоритмов определяются свойствами существенно более простого объекта — алгебры О-алгоритМов, введенной в работе и однозначно задаваемой по исходной алгоритмической алгебре. Любая алгебра (детерминированных или недетерминированных) алгоритмов может быть построена по некоторой алгебре П-алгоритмов с помощью стандартной конструктивной процедуры.

2. Введены и исследованы понятия П-языка и точного О-языка, обобщающие понятие формального языка и допускающие интерпретацию в классе частичных точечно-множественных (недетерминированных) операторов. На основе этих понятий введены и исследованы свободные алгебры П-алгоритмов, детерминированных и недетерминированных. алгоритмов. Частным случаем свободной алгебры О-алгоритмов является алгебра регулярных выражений (алгебра Клини). Установлены свойства (точных) П-языков, задаваемых регулярными схемами свободных алгебр детерминированных и недетерминированных алгоритмов.

3. Впервые введен и исследован класс формальных языков, построенных над алфавитом, часть символов которого интерпретирована в булевой алгебре. Обычные формальные языки являются частным случаем языков данного класса. Установлена возможность классификации таких языков по аналогии с классификацией Хомского.

4. Установлена связь рациональных (регулярных) языков над алфавитом, интерпретированным в булевой алгебре, с конечными автоматами. Получено обобщение на данный случай теоремы Клини о представлении рациональных языков автоматами. Доказана разрешимость алгоритмической проблемы тождества для регулярных языков над алфавитом, интерпретированным в булевой алгебре.

5. Установлена разрешимость алгоритмической проблемы тождества регулярных схем (операторов и условий) свободных алгебр недетерминированных алгоритмов.

6. Построен аппарат динамических сетевых моделей (ГДП), охватывающий сети Петри и их модификации, а также конечные дискретные преобразователи. Исследованы полугрупповые свойства свободного языка, порождаемого ГДП, установлена связь с частично коммутативными моноидами и теорией следов,.

7. Установлена возможность представления регулярной схемы оператора алгоритмической алгебры в виде динамической сетевой модели (ГДП), вычисляющей тот же оператор. На основе данного представления получена возможность организации вычислений, устойчивых к «сбоям» гипотетической машины.

8. Построен и исследован стохастический аналог алгоритмической алгебры — марковская алгоритмическая алгебра, позволяющая решать ряд задач вероятностного характера.

Практическая ценность и реализация работы. В работе построен метод, позволяющий реализовать алгебры детерминированных и недетерминированных алгоритмов, сигнатура которых включает соответственно семь и восемь операций {без учета нульарных операций) средствами существенно более простой алгебры О-алгоритмов с четырьмя операциями. Такой подход упрощает разработку программных средств, ориентированных на представление алгоритмов и программ в виде регулярных схем алгоритмических алгебр.

Разработанный в диссертации метод моделирования регулярных схем операторов алгоритмических алгебр в виде ГДП позволяет организовать вычислительный процесс, устойчивый к сбоям вычислительного устройства.

Аппарат марковских алгоритмических алгебр позволяет эффективно решать ряд практических задач вероятностного характера, относящихся к программным вычислениям, в частности, вероятностный аналог задачи тестирования программ.

Аппарат генераторов дискретных процессов позволяет осуществить программное моделирование и анализ системы управления промышленным предприятия. Решается также практическая задача декомпозиции информационного фонда промышленного предприятия на базы данных.

На основе полученных результатов при непосредственном участии автора были разработаны программные средства моделирования и анализа интегрированной системы управления дискретным производством ПАРИС и АВАНС, а также пакет прикладных программ «Декомпозиция информационной базы» (Отраслевой фонд алгоритмов и программ АСУ Минприбора СССР, инв.№ 1030, Калинин, Центрпрограммсистем, 1983), реализующий описанный в диссертации метод декомпозиции информационного фонда на базы данных.

Системы ПАРИС и АВАНС были апробированы на реальных данных, относящихся к трем подсистемам интегрированной АСУ НПО «Электрон» (системы автоматизированного проектирования изделий, системы оперативно-производственного планирования, автоматизированной системы оперативно-диспетчерского управления). Результаты моделирования были обработаны, и на их основе разработаны конкретные рекомендации для повышения эффективности системы управления Львовского научно-производственного объединения «Электрон» .

Разработка и апробация указанных программных средств проводилась в рамках следующих опытно-конструкторских и научно-исследовательских работ: ОКР «Разработка общесистемных и функциональных средств автоматизации управления производственным объединением» (шифр «Меркурий 2.2», номер государственной регистрации У45 449 от 04.05.87 г.), проведенной на основании приказов Министерства промышленности средств связи СССР № 547 дсп от 16.12.85 г. и № 96 дсп от 21.03.86 г.- НИР «Разработка принципов построения типовых инструментальных и функциональных средствинтегрированных АСУ предприятием (объединением) «(шифр «Старт», номер государственной регистрации У48 996 от 06.05.88 г.), проведенной на основании Постановления Государственной Комиссии.

Совета Министров СССР № 47 от 11.02.88 г. и приказа Министерства промышленности средств связи СССР № 61 от 19.02.88 г.- НИР «Проведение научных исследований по направлению развития работ в области АСУ предприятия, объединения, создание научно-технического задела по разработке технико-экономических решений для повышения уровня интеграции и эффективности указанных систем в ХШ-й пятилетке» (шифр «Развитие», номер государственной регистрации У56 580 от 15.03.89 г.), проведенной по решению Государственной Комиссии Совета Министров СССР № 47 от 11.02.88 г. и приказу Министерства промышленности средств связи СССР № 61 от 19.02.88 г.- при выполнении технического задания по научно-технической программе ГКНТ СССР 0.80.02, задание 35.01.06Д «Разработать методологические и инструментальные средства для автоматизированного проектирования сложных многоуровневых и крупномасштабных систем». Система ПАРИС (версия 1.1) отмечена серебряной медалью ВДНХ СССР.

Основные положения диссертации отражены в публикациях [52−55, 61−66, 71−100, 114].

Основной текст диссертационной работы состоит из четырех глав, охватывающих двадцать четыре раздела.

В первой главе диссертации алгебры детерминированных и недетерминированных алгоритмов рассматриваются с точки зрения более «простого» объекта — вводимой в данной главе универсальной алгебры О-алгоритмов. Сигнатура алгебры ¿-^-алгоритмов содержит лишь четыре операции, три из которых (сложение, умножение и итерация) представляют собой хорошо известные операции алгебры Клини.

Показано, что изучение алгебраических свойств алгоритмических. алгебр (детерминированных и недетерминированных алгоритмов) может быть сведено к изучению алгебры О-алгоритмов. Именно, показывается, что упомянутые алгебры алгоритмов являются редуктами алгебры £)-алгоритмов, конечная система порождающих которой однозначно определяется порождающими алгоритмической алгебры. При этом информационные множества алгебры алгоритмов и соответствующей алгебры^{-алгоритмов} совпадают. Прямая и обратная процедуры сопоставления алгоритмической алгебре соответствующего редукта алгебры П-алго-ритмов, описанные в данной главе, составляют сущность метода редукции алгоритмических алгебр. Вводятся и исследуются свободные алгебры П-алгоритмов, которые можно рассматривать как фактор-алгебры алгебры термов заданной сигнатуры. Этими термами однозначно определяются специального рода объекты — так называемые.

0-языки. При этом П-языки, определяемые регулярными выражениями алгебры Клини, совпадают с обычными рациональными языками. Поэтому рассматриваемая алгебра является некоторым обобщением алгебры.

Клини. Показывается, что каждый элемент свободной алгебры П-алго-ритмов задает единственный^-язык специального вида, так называемый точный П-язык. На основе понятия свободной алгебры П-алгорит-мов вводятся и исследуются понятия свободных алгебр детерминированных и недетерминированных алгоритмов. Соответствующие определения «свободны» от операторной терминологии, т. е. не используют понятий информационного множества, оператора и условия, и свойства свободных алгоритмических алгебр определяются свойствами точных языков. Вместе с тем любая алгебра (детерминированных или недетерминированных) алгоритмов является гомоморфным образом некоторой свободной алгебры.

Из результатов, полученных в первой главе диссертации, следует, что свойства свободных алгоритмических алгебр определяются свойствами точных И-языков, связанных с этими алгебрами.

Примером точного П-языка является формальный язык, рассматриваемый над таким алфавитом, части символов которого взаимнооднозначным образом сопоставлены элементы некоторой конечной булевой алгебры, и называемый языком с интерпретацией алфавита в булевой алгебре. Подобные языки возникали и рассматривались ранее в связи с изучением алгебр детерминированных и недетерминированных алгоритмов (конфигурации в [107]), схем программ (цепочки стандартной схемы в [40]) а также в ряде других случаев. Формальное понятие языка над алфавитом с интерпретацией в булевой алгебре вводится и изучается во второй главе диссертационной работы. Показывается, что свойства языков с интерпретированным в булевой алгебре алфавитом определяются свойствами некоторой однозначно определяемой по исходному алфавиту и булевой алгебре алгебраической системе и. Сигнатура операций алгебраической системы и включает сложение, умножение и итерацию, а сигнатура отношений этой системы состоит из единственного отношениясогласованного с операциями частичного порядка, относительно которого и является верхней полурешеткой. Исследуются свойства алгебраической системы и, определяемые языками специального вида, построенными над алфавитом, часть символов которого соответствует элементам конечного разбиения единицы булевой алгебры. Устанавливается связь этих языков с абстрактными автоматами, что приводит к некоторому обобщению теоремы Клини о совпадении классов рациональных и регулярных (задаваемых конечными автоматами) языков. Основное внимание в данной главе уделяется регулярным языкам с интерпретацией алфавита. Исследуются их свойства и доказывается разрешимость проблемы тождества для таких регулярных языков, заданных конечными автоматами или же регулярными выражениями алгебры Клини. На основе полученных результатов доказана разрешимость проблемы тождества для свободной алгебры недетерминированных алгоритмов. Изучается возможность классификации языков с интерпретацией алфавита по аналогии с классификацией Хомского формальных языков. Доказана возможность подхода, основанного на данной классификации.

В третьей главе диссертации разрабатывается и применяется к исследованию регулярных схем операторов алгоритмических алгебр аппарат динамических сетевых моделей — генераторов дискретных процессов (ГДП). Статическая структура ГДП может рассматриваться как вычислительная модель Тыугу, а правила функционирования носят весьма общий характер и задают недетерминированное поведение системы. Исследуются выразительные возможности введенной модели, показывается, что в терминах ГДП могут быть описаны автоматы и сети Петри. Вводятся и изучаются специальные классы ГДП (свободные ГДП, ГДП с настройкой). Установлена связь ГДП с частично коммутативными моноидами и теорией следов, исследуются формальные языки, порождаемые ГДП, изучаются полугрупповые свойства этих языков. Рассматривается многоуровневое представление ГДП. Вводится понятие многоуровневой алгоритмической системы. Показывается, что регулярная схема оператора алгоритмической алгебры допускает разложение по некоторой многоуровневой алгоритмической системе (т.е. регулярную схему можно представить в виде некоторой совокупности взаимосвязанных регулярных схем более простого вида). Показано, что регулярные схемы операторов алгоритмйческих алгебр могут быть заданы в терминах ГДП специального вида, вычисляющих те же операторы, что и исходные регулярные схемы. Данная интерпретация регулярных схем операторов в виде ГДП позволяет выделить и изучить специальные способы организации вычислений, основанные на данном представлении. Показывается, в частности, что вычисления можно организовать на основе единого циклического способа управления, при котором вычисление значений элементарных операторов происходит в цикле, состоящем в последовательном (в любом заранее заданом порядке) вычислении этих операторов с проверкой единственного элементарного условия. При этом такой способ вычислений устойчив к «сбоям» гипотетической машины, т. е. при прерывании вычислений их можно возобновить на основе последнего вычисленного значения, а порядок выполнения элементарных операторов может быть изменен произвольным образом (но сохранен до окончания вычислений или же до следующего «сбоя»).

В четвертой главе диссертационной работы рассмотрены специальные классы алгоритмических алгебр и некоторые приложения введенного в предшествующих разделах аппарата к объектам, выходящим за рамки теории алгоритмических алгебр. Изучаются регулярные схемы над памятью, определение которых дается по аналогии со схемами над памятью, рассматриваемыми в [30]. Показано, что оператор, заданный конечным дискретным преобразователем, можно задать регулярной схемой с настройкой в такой алгоритмической алгебре, сигнатура которой содержит лишь две операции — а-итерацию и композицию операторов, а множество элементарных условий состоит из единственного условия. Доказывается, что оператор, задаваемый ГДП с настройкой, может быть представлен регулярной схемой (с настройкой) оператора алгоритмической алгебры, сигнатура которой содержит три операции — композицию, а-дизъюнкцию и недетерминированную дизъюнкцию операторов. Установлено, что для любой регулярной схемы оператора алгебры недетерминированных алгоритмов существует такая регулярная схема (с настройкой) алгебры алгоритмов с двумя операциями (недетерминированной дизъюнкцией и а-итерацией), элементарные операторы которой определяются по исходной схеме, вычисляющая тот же оператор. Из сформулированных результатов, в частности, следует, что класс ГДП представляет собой такой класс дискретных преобразователей, в котором теорема Глушкова (о представлении оператора, заданного конечным дискретным преобразователем, регулярной схемой) допускает обращение. Вводится и исследуется понятие марковской алгоритмической системы, которая дает возможность описания однородных Цепей Маркова с конечным числом состояний в терминах, аналогичных алгебро-алгоритмическим. Доказано, что марковская алгоритмическая система является гомоморфным образом алгоритмической алгебры. С помощью введенного понятия решаются задачи вероятностного характера применительно к моделям, заданным в виде регулярных схем операторов. К числу таких задач относятся: определение вероятности того, что значение оператора, представленного регулярной схемой и вычисляемого в случайно выбираемой точке, удовлетворяет заданному условию (вероятностный аналог задачи тестирования) — определение вероятности прерывания вычислений до их завершения (переход системы в заданное поглощающее состояние) — определение математического ожидания времени, проведенного в некотором состоянии до поглощения и т. п. В заключение четвертой главы описаны две прикладные задачи, решение которых основано на полученных в данной работе результатах: задача моделирования информационно-функциональной структуры промышленного предприятия и задача декомпозиции информационного фонда на базы данных. На основе решения этих задач были разработаны прикладные программы, внедренные в производство.

В заключении перечислены выносимые на защиту результаты диссертационной работы.

— го.

ЗАКЛЮЧЕНИЕ

.

В диссертации предлагается для решения актуальной научной проблемы исследования алгебр детерминированных и недетерминированных алгоритмов использовать интерпретационные методы, основанные на сведении данных алгебр и связанных с ними формальных объектов к другим объектам, исследование которых может быть выполнено достаточно эффективным образом. К числу указанных объектов, введенных и рассмотренных в диссертации, относятся универсальные алгебры П-алгоритмов, формальные языки над интерпретированным в булевой алгебре алфавитом, генераторы дискретных процессов, марковские алгоритмические алгебры.

Разработка и применение для анализа алгоритмических алгебр интерпретационных методов показали, что с их помощью может быть решен ряд теоретических задач, не допускавших решения традиционными методами, а также выявили возможность применения разработанного аппарата для эффективного решения практических задач на промышленном уровне.

В работе получены следующие результаты, обладающие новизной и выносимые на защиту:

1. Разработан интерпретационный ме, тод, позволяющий свести алгебры детерминированных и недетерминированных алгоритмов к единому, существенно более простому объекту — введенной и исследованной в работе алгебре П-алгоритмов. Показано, что свойства любой алгебры детерминированных или недетерминированных алгоритмов определяются свойствами алгебры П-алгоритмов, однозначно задаваемой по исходной алгоритмической алгебре. Любая алгебра (детерминированных или недетерминированных) алгоритмов может быть построена по некоторой алгебре П-алгоритмов с помощью стандартной конструктивной процедуры.

2. Введены и исследованы понятия П-языка и точного П-языка, а на основе этих понятий — свободные алгебры П-алгоритмов, детерминированных и недетерминированных алгоритмов. Установлена связь свободной алгебры П-алгоритмов и свободной алгебры недетерминированных алгоритмов с алгеброй Клини. Разработан метод исследования свободных алгебр П-алгоритмов, детерминированных и недетерминированных алгоритмов, основанный на свойствах точных П-языков, задаваемых схемами соответствующих алгебр.

3. Введено понятие и разработан общий метод исследования специального класса П-языков — формальных языков над алфавитом, интерпретированным в булевой алгебре. Установлена возможность классификации таких языков по аналогии с классификацией Хомского.

4. Разработан метод исследования регулярных языков над алфавитом, интерпретированным в булевой алгебре. Установлена связь рациональных (регулярных) языков над алфавитом, интерпретированным в булевой алгебре, с конечными автоматами. Получено обобщение на данный случай теоремы Клини о представлении рациональных языков автоматами. Описан общий алгоритм, позволяющий проверить эквивалентность таких языков.

5. Доказана разрешимость алгоритмической проблемы тождества для регулярных языков над алфавитом, интерпретированным в булевой алгебре.

6. Установлена разрешимость алгоритмической проблемы тождества регулярных схем (операторов и условий) свободных алгебр недетерминированных алгоритмов.

7. Построен аппарат генераторов дискретных процессов, охватывающий автоматы, сети Петри и их модификации, а также конечные дискретные преобразователй. Исследованы свойства языков, порождаемых ГДП, установлена связь с частично коммутативными моноидами и теорией следов.

8. Разработан метод исследования регулярных схем операторов алгоритмических алгебр на основе их представления в виде генераторов дискретных процессов. На основе данного представления исследованы способы организации вычислений, задаваемых регулярными схемами, в том числе устойчивых к сбоям вычислительного устройства. Показано, что в классе ГДП верна и допускает обращение теорема В. М. Глушкова о представлении оператора, заданного конечным дискретным преобразователем, регулярной схемой алгоритмической алгебры.

9. Разработаны методы формального описания дискретных преобразователей в терминах регулярных схем (с настройкой) операторов алгоритмических алгебр.

10. Разработан метод исследования случайных вычислительных процессов, соответствующих однородным цепям Маркова с конечным числом состояний и интерпретируемых как элементы введенной в рвботе марковской алгоритмической алгебры — стохастического аналога алгебры алгоритмов.

11. На основе разработанных теоретических положений предложено использование введенного в работе аппарата для программного моделирования и анализа системы управления промышленным предприятием, а также для решения задачи декомпозиции информационного фонда предприятия на базы данных.

Подходы и методы, предложенные в’диссертации, носят общий характер и могут быть использованы для решения ряда других теоретических и практических задач.