Механизм распознавания сходства и различия автоматов и алгоритмов

АННОТАЦИЯ

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

- получения критерия сходства и различия автоматов и разработки механизма распознавании сходства пригодных для инженерной практики метода синтеза сложных автоматов.

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

ABSTRACT

The article is devoted to the research and development of the tolerance apparatus for algorithms and automata designed to solve one of the main problems of computer system design automation (SC) - determining the optimal composition of functional modules (FM) of the developed SC, which differ in the minimum number of types of FM, but in the aggregate best (in a sense) way implementing any algorithm from a given set of problems. Thus, in the problem to be solved, the following questions are highlighted, which are also the stages of the specified method.

- obtaining the criterion of similarity and difference of automata and developing a mechanism for recognizing the similarity of the method of synthesis of complex automata suitable for engineering practice.

- research of possible methods for constructing tolerance classes on a set of algorithms and automata and development of such a procedure that would lead to a single construction of classes of similar automata.

Ключевые слова: функционально неэквивалентные автоматы, несимметричные отношения, отношения вложения, абстрактный автомат, система базисных маршрутов.

Keywords: functionally non-equivalent automata, asymmetric relationships, containment relationships, abstract machine, the system of the base routes.

Введение. Суть установления соответствия между ФМ и алгоритмами состоит в замене одного или нескольких из алгоритмов или блоков одним или несколькими модулями Б_ξ. Заменить фрагмент алгоритма модулем можно, если Б_ξ эквивалентен этому фрагменту, т.е. если модуль Б_ξ при его функционировании дает на выходе результат, находящейся в отношении изоморфизма с результатом функционирования фрагмента  при изоморфизме поданных входных сигналов.

Уточним понятие заменимости автоматов.

1. Будем различать «заменимость» в одну сторону, когда один абстрактный автомат-алгоритм G с «богатой» совокупностью признаков описания А заменяет другой абстрактный автомат –алгоритм c «бедной» совокупностью признаков , ( при этом A), или при одинаковом числе признаков, признаки из  более «емкие» и они «поглощают» некоторые или все признаки из . Такую заменимость будем определять отображением вложения е :  → А и обозначим:   А, чтобы подчеркнуть, что  является подмножеством А, а е - отношением вложения или просто вложением. Данное отношение рефлексивно, транзитивно и антисимметрично. Оно представляет собой один из видов нестрогих порядков.

2. Если автоматы G₁ и G₂ полностью взаимозаменяемы в рассматриваемой ситуации, т.е. А₁⇔А₂, то отношение вложения автомата G самого себя назовем его тождественным отображением автомата G и обозначим символом е_G (е_G: Данное отношение транзитивно, рефлексивно и симметрично.

Оно является отношением эквивалентности.

Отдельные структурные автоматы - функциональные модули способны замещать несколько других абстрактных автоматов - фрагментов алгоритмов , т.е. целую совокупность {} как взаимосвязанных, так и независимых фрагментов алгоритма. Если I = {} некоторое множество индексов, а {}- семейство множеств алгоритмов, заномерованных из I, и если  то для суммы множеств    из семейства {  } существует отображение

где В_ξ - совокупность характеристик модуля Б_ξ ,  -дизъюнктивное объединение, обозначаемое также символом  Но отмечается также вложение:

Постановка задачи. В основе установления приведенного соответствия между автоматами (и алгоритмами) лежит их сходства и различие с точки зрения получения одинакового результата при поступлении на их входы одинаковых данных. В [2,15,16] введены понятия областей определений и значений алгоритма, а также отношения функциональной эквивалентности алгоритмов [8], которое является экспликацией понятия взаимозаменяемости и одинаковости алгоритмов.

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

Критерий сложности автоматов (абстрактных и физических), пригодный для распознавания их сходства и различия, должен прежде всего отвечать на вопрос, получим ли мы одинаковые результаты на разных автоматах, если подать на их входы одинаковые сигналы. Кроме того он должен быть прост в практическом использовании и давать опережающий однозначный ответ (до реализации алгоритма). Данный критерий должен оценивать структурно-функциональное разнообразие сравниваемых объектов (алгоритмов и ФМ), т.е. множество входов выходов и поведение автоматов. При этом, если руководствоваться фундаментальным принципом управления, названным У.Р. Эшби законом необходимого разнообразия, то его, применительно к поставленной задаче, следует понимать так: разнообразие заменяющего объекта (одного автомата) должно быть не меньше разнообразия заменяемого объекта (другого автомата).

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

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

Мы использовали иной, более простой метод установления соответствия между алгоритмами и автоматами, который обоснован Ю.И. Яновым [1] и развит А.П. Ершовым [2]. Суть его состоит в переходе от системы с отношениями не ее элементах к некоторому множеству других элементов, описывающих существенные свойства системы, но уже без отношений на них. В результате распознавание сходства (различия) систем выполняется путем проверки на совпадение (несовпадение) элементов из разных множеств. Операцией сравнения уже служит не отношение изоморфизма соответствия, а отношение вложения элементов одного множества в другое, которое несравненно менее трудоемко, чем распознавание изоморфизма.

С учетом этой идеи существования изоморфизма между структурами - в работах [3] детально рассмотрен наиболее приемлемый критерий сходства и различия алгоритмов и автоматов – система базисных маршрутов

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

Конфигурация и маршруты на схемах алгоритмов. В области теоретического программирования в классической работе Ю.И. Янова [1], впервые была математически строго рассмотрена кардинальная ее проблема – теория формальных преобразований программ, создавшая определенный подход к задачам теории преобразования программ последовательных [8], [9,10] , параллельных автоматов [11] и схем автоматов [1]. Основной результат работ [12]- это алгоритм распознавания эквивалентности (равносильности) логических схем Янова, где критерием служило множество конфигураций на канонических схемах алгоритмов (доказан Ю.И. Яновым, А.П. Ершовым и др.) и автоматов (А.А. Летичевским и др.), а отношением сравнения – отношение эквивалентности конфигураций. Алгоритм распознавания двух логических схем Янова обычно сводится к построению их канонических схем и последующей проверки их на равенство.

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

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

Далее, маршруты на модели алгоритма G состоят только из счетных арифметических и логических операторов. В силу предложенного [7] метода построения модели алгоритма G = (W, R; ), содержательных маршрутов находящийся между ее начальными и конечными вершинами являются с точностью до счетных операторов и порядка на них ничем иным как точными конфигурациями схемы G, заключающимися символом конечного оператора [9]. Тогда две эквивалентные схемы в любой конкретной интерпретации будут иметь одинаковые последовательности выполнения счетных операторов, т.е. маршруты.

Следовательно, при таком подходе проверки эквивалентности не надо приводить логическую схему к канонической форме. Требуется лишь вычислить множества маршрутов W₁ = {}  и  W₂ = {w_2j } на двух операторных схемах алгоритмов G₁ и G₂ или более, а затем сравнить все маршруты из их множеств.

С связи со сказанным вытекает следующее утверждение.

Утверждение 2.1. Если множества W₁ и W₂ маршрутов конечны и равны | W₁ | = |W₂| по числу маршрутов, и для каждого маршрута из W₁ найдется w_2j из W₂, изоморфный первому, то схемы G₁ и G₂  алгоритмов будут эквивалентны G₁  ~ G₂.

Таким образом, для распознавания сильной эквивалентности можно использовать не конфигурации, а маршруты на граф схемах алгоритмов. При этом значительно упрощается процедура распознавания эквивалентности. Однако и в данном случае остаются без ответа некоторые вопросы.  Так если некоторое подмножество  маршрутов из W₁ автомата А₁ не  имеет изоморфных маршрутов W₂ автомата А₂ или наоборот, то необходимо выяснить:

1) существует ли другой вид отношения, кроме эквивалентности, характеризующий их функциональные свойства;

2)  можно ли правила преобразования схем [11,] с сохранением этих отношений применить к соответствующим локальным частям W`<sub>1</sub> (или W`₂ );

3) существует ли соответствие между разнородными автоматами (абстрактными и физическими).

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

Итак, сформулирована первая посылка, лежащая в основе решения поставленных вопросов, а именно- использование в качестве операции сравнения структур абстрактных моделей алгоритмов более «слабых» отношений, чем эквивалентность. Далее, так как на модели алгоритма G =(W,R;F,U`), среди множества W маршрутов, базисных и содержательных, могут быть одинаковые или исходные по составу элементарных логических и арифметических операций и их упорядоченности , возникает вопрос нельзя ли для описания алгоритма G вместо исходного множества W маршрутов, среди которых имеются сравнимые между собой маршруты, использовать множество W` с меньшим числом маршрутов, которые уже не находится в отношении сравнения друг с другом. Так была сформулирована другая посылка-реализация гомоморфизмов первоначальных множеств абстрактных моделей алгоритмов в их фактор модели, множество носителей которых имеют меньшее число элементов, чем исходные аналогичные множества.

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

Список литературы:
1. Янов.Ю.И. О логических схемах алгоритмов // Проблемы кибернетики, 1958. -Вып.1. –с 75-127.
2. Ершов.А.П. Операторные алгоритмы III //Проблемы кибернетики,- Вып.20. -1968. - 288 с.
3. Янов.Ю.И. О локальных преобразованиях схем алгоритмов// Проблемы кибернетики, 1967. - вып.20. -201-216.
4. Каляев А.В. Многопроцессорные вычислительные системы с программируемой архитектурой. -М: Радио и связь, 1984. - 240 с.
5. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. Физ - мат,-1973. -256с.
6. Дурандин К.П., Ефремов В.Д., Колосников Д.Н. Методы анализа эффективности функционирования сложных систем. Л.: ЛПИ. - 1978.-77.
7. Мусаев М.У. Средства формализованного описания и преобразования автоматов и алгоритмов, ориентированных на проектирования ВС / Таш.политех.ин-т.-Ташкент.1988. -29 с. Деп в УЗНИИТИ 27.12.88. -29 с. № 911 Уз 88.
8. Кринецкий Н.А., Миронов Г.А.Фролов Г.Д. Программирование и алгоритмические языки. М.: Наука, 1975. -496 с.
9. Жаров В.Т., Тютин А.А. ОБ одном методе покрытия логических схем в заданной системе элементов // УсиМ. - 1983. -№ 4 –с 45-58.
10. Тузов В.А. Эквивалентность логических схем с перестановочными операторами// Кибернетика, - 1971. -№ 5. - с 23-32.
11. Грин Д., Кнут Д. Математические методы анализа алгоритмов пер. с англ. Из-во ’’Мир” 1987 г. 120 с.
12. Иловайский И. В. Формальный синтез схем свойств по алгоритмам и функционирования ВС/ / Выпуск. 47.-1981. – с.56-72.
13. Горель Э.Л. Об операторных схемах Янова с обеспечением конечной эквивалентности //Кибернетика, - 1971. -№ 5. - с 63-64.
14. Вальковский В.А. Некоторые результаты относительно свойств конфигураций схем Янова// Кибернетика,-1972. -№ 4.с 14-22.
15. Кринецский Н.А. Равносильное преобразования алгоритмов и программирование. -М.: Сов. Радио,-1980. - 303с.
16. Жаров В.Т., Тютин А.А. ОБ одном методе покрытия логических схем в заданной системе элементов // УсиМ. - 1983. -№ 4 –с 45-58.