автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Идентификация дискретных систем

На правах рукописи

СКОБЕЛЕВ Владимир Геннадиевич

ИДЕНТИФИКАЦИЯ ДИСКРЕТНЫХ СИСТЕМ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технической отрасли)

Автореферат

диссертации на соискание ученой степени доктора технических наук

Саратов - 2002

Работа выполнена в Институте прикладной математики и механики Национальной Академии Наук Украины (ИПММ НАНУ)

Научный консультант:

- доктор технических наук, профессор Сперанский Дмитрий Васильевич

Официальные оппоненты: - доктор технических наук, профессор

Твердохлебов Владимир Александрович

- доктор технических наук, профессор Сытник Александр Александрович

- доктор технических наук, профессор Матросова Анжела Юрьевна

Ведущая организация: Институт проблем управления РАН, г. Москва

Защита состоится 10 декабря 2002 г. в 14— часов на заседании диссертационного совета Д 212.242.04 в Саратовском государственном техническом университете по адресу: 410054, Саратов, ул. Политехническая, 77, ауд. 319

С диссертацией можно ознакомиться в научно-технической библиотеке СГТУ.

Автореферат разослан «/С » ноября 2002 г.

Ученый секретарь

диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время бурно развивается теория дискретных систем. Это развитие происходит путем возникновения ряда слабо взаимосвязанных недостаточно теоретически проработанных разделов, часто возникающих из прикладных проблем. Как следствие, существует многообразие различных моделей, как правило, нечисловой природы (т.е: таблицы, размеченные графы, теоретико-множественные и лингвистические конструкции и т.д.), основным методом исследования которых является более или менее разумно организованный перебор вариантов, т.е. поиск. Отмеченные особенности в полной мере проявили себя в возникших в последнее время системах дискретных событий (discrete event systems) и размеченных системах переходов (labelled transition systems). Этим разделам ежегодно посвящается значительное число конференций, симпозиумов и публикаций, основной итог которых - результаты дескриптивного плана.

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

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

Теория систем существует уже более полувека. Ее становление как самостоятельной науки тесно связано с именами М. Арбиба, JI. Берталан-фи, Р. Калмана, В.М. Матросова, М. Месаровича, П. Фалба. Однако до сих пор отсутствует общепринятый аксиоматический подход к теории систем, позволяющий с единых позиций эффективно исследовать весь комплекс возникающих проблем. Более того, зачастую происходит независимое развитие теорий непрерывных и дискретных систем, вспоминающих друг о друге только при исследовании гибридных моделей.

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

з

вателей была создана теория идентификации непрерывных систем. Предмет ее исследования — идентификация методами математического анализа и алгебры отображений и параметров для систем, представленных функциональными или дифференциальными уравнениями. Достаточная проработанность этой теории позволила Л. Льюнгу оформить эффективную теорию, предназначенную для пользователя. Эта теория, однако, вообще не применима в процессе решения проблем идентификации дискретных систем, из-за отсутствия возможности использовать в дискретном случае такое фундаментальное понятие, как предельный переход. В то же время для узких классов дискретных систем были с успехом использованы методы теории конечных полей. Яркими примерами являются исследования линейных систем А. Гиллом и А. Заде, теории кодирования Р. Блейху-том и многочисленные потенциальные приложения, указанные Р. Лиддлом и Г. Нидеррайтером.

Независимо от теории систем и немного ранее | во времени применение, по сути дела, системного подхода с успехом было продемонстрировано в современной алгебре, что, в конечном счете, привело к разработке теории алгебраических систем А.И. Мальцевым и А. Тарским.

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

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

Указанная цель достигается решением следующих задач:

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

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

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

4. Разработка более простых, чем известные аналитические, комбинаторных методов поиска одной и всех простых импликант, покрывающих заданную точку, а также ДНФ, состоящих из простых импликант.

5. Решение возникших из прикладных задач анализа контроллепри-годности комбинационных схем проблем анализа управляемости/наблюдаемости для булевых функций.

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

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

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

Новые научные результаты. В процессе решения задач диссертации получены новые научные, принадлежащие лично автору результаты, которые выносятся на защиту:

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

2. Определены и исследованы оригинальные базовые математические модели для поиска безусловных и адаптивных решений, соответственно М -источник и АМ -источник. Впервые исследованы общие соотношения между моделями, предназначенными для поиска адаптивных и безусловных решений. Получено полное решение задач поиска основных тапов решений (т.е. всех минимальных, всех неприводимых, одного минимального, одного кооперативного и одного адаптивного решений). Разработана общая схема двустороннего поиска минимальных решений для М -источников за счет параллельных действий с прямыми и обратными М -источниками.

3. Впервые получено полное решение задачи поиска всех неприводимых множеств представителей заданного семейства множеств.

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

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

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

7. Разработаны основанные на последовательном вычеркивании литералов комбинаторные алгоритмы поиска одной и всех простых импли-кант, покрывающих заданную точку. Показано, что последовательное применение этих алгоритмов дает возможность строить не очень сложную ДНФ, состоящую из простых импликант, а также сокращенную ДНФ.

8. Впервые построена математическая теория исследования управляемости/наблюдаемости булевых функций и их композиций, основанная на теории минимизации ДНФ.

9. Впервые получено полное решение задачи идентификации булевых вектор-функций методами теории линейных пространств над конечными полями.

10. Впервые разработан новый фрагмент математической теории систем - теория ДДФ-систем, предназначенный для анализа систем, подверженных дестабилизирующим воздействиям внешней среды.

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

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

Мотивация исследований и реализация результатов. Проведенные в работе исследования выполнены в рамках следующих госбюджетных НИР, проводимых в отделе теории управляющих систем Института прикладной математики и механики HAH Украины:

- «Разработать методы построения тестов для систем базовых ТЭЗов и модификации структуры ТЭЗов с целью улучшения их диагностируемо-сти и выдать рекомендации организациям Минавиапрома по их использованию» (1979-1981, ГР № 79033304);

- «Анализ непрерывных и дискретных систем с применением в задачах управления и оптимизации» (1982-1985, ГР № 01820073577);

- «Разработать математические методы оптимизации управления с приложением в технической диагностике, транспортных и технологических процессах» (1986-1989, ГР № 01.860.042947);

- «Исследование математических вопросов теории цифровых устройств и создание программных систем их контроля и диагностирования» (1990-1993, ГР№ 01.9.00.018.556);

- «Исследование обратных задач теории автоматов, идентификации и распознавания дискретных систем» (1994-1998, ГР№ 0399U003565);

- «Исследование актуальных проблем моделирования, управления и идентификации дискретных систем» (1999-2003, ГР № 0199U001612).

Кроме этого, разработка и внедрение результатов осуществлялись в процессе выполнения следующих хоздоговорных работ:

- «Внедрение алгоритмов и системы математического обеспечения для моделирования и диагностики цифровых устройств» (1984-1987, ГР № 01840084752) и «Разработка моделей, алгоритмов и математического обеспечения диагностирования цифровых устройств» (1987-1989, ГР № 01.870.055.678), заключенных между Саратовским производственным объединением им. С. Орджоникидзе и Специальным конструкторско-технологическим бюро систем управления ИПММ HAH Украины;

- «Исследование методов, алгоритмов и разработка программного обеспечения контроля и автоматизированного поиска неисправностей МСВТ» (1989-1990, ГР № 5540107.00045), заключенной- между Московским НИИ «Научный центр» и Специальным конструкторско-технологическим бюро систем управления ИПММ HAH Украины.

Разработанные автором алгоритмы поиска, идентификации автоматов и булевых функций использовались им при чтении курса «Дискретная математика и математическая логика» для студентов математического факультета Донецкого государственного университета (специальность 0106 Прикладная математика) в 1986-1991гг., а методы исследования поведения систем в условиях нестабильной внешней среды - при чтении с 1999г. курса «Математические методы в маркетинге» для бакалавров и магистров Донецкой государственной академии управления, а также для системы последипломного образования ОАО «Концерн «Стирол»» (г. Горловка).

Апробация работы. Основные результаты работы были представлены на Международной конференции по прикладной и промышленной математике ICIAM/GAMM'95 (г. Гамбург, Германия), ежегодных конференциях Общества по прикладной и промышленной математике . (Gesellschaft für angewandte mathematik und mechanic - GAMM): GAMM'98 (г. Бремен, Германия) и GAMM'2001 (г. Цюрих, Швейцария), Международной конференции «Fault tolerant systems and diagnostics» (г. Брно, Чехословакия, 1981), Всесоюзной конференции «Проблемы теоретической кибернетики» (г. Волгоград, 1990), Всесоюзных совещаниях по технической диагностике ( г. Черкассы, 1979 и Ростов-на-Дону, 1980), а также доложены на семинарах в Московском, Киевском, Саратовском и Донецком государственных университетах, Институте кибернетики HAH Украины (г. Киев), Институте проблем моделирования в энергетике HAH Украины (г. Киев), Институте прикладной математики и механики HAH Украины (г. Донецк), университете г. Сандерленд (Великобритания), Институте математики университета г. Мишкольц (Венгрия).

Публикации. По теме диссертации опубликовано 39 работ, в том числе 2 монографии. Список основных публикаций, наиболее полно отражающих содержание работы, приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, пяти разделов, заключения, списка литературы из 138 наименований и приложения. Общий объем работы составляет 257 страниц текста, в том числе 236 страниц основного текста, 11 страниц списка литературы и 10 страниц приложения.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

1. Для заданной системы 5 и заданного множества систем и = {8< | г е /} требуется проверить, выполнено ли условие: ¿' е (У ? В случае положительного ответа необходимо найти такую систему Б что истинно равенство 5 •

2. Заданы система 50 и конечное множество систем и (Ь\ & и). Для заданной системы 5 е {5 0} и [/ необходимо проверить, выполнено ли равенство: 5 =5 0?

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

3. Выделить такое достаточно малое по мощности подмножество U' множества U , что решение проблемы идентификации системы для множества U' однозначно определяет решение проблемы идентификации системы для множества U .

Для решения проблемы 3 достаточно разработать эффективный механизм представления реакции любой системы S <bU в виде композиции реакций систем, принадлежащих множеству U'. Однако при решении прикладных задач (в том числе при построении тестов для дискретных устройств) часто используется следующий инверсный подход. Определяется ядро, т.е. достаточно малое по мощности подмножество UVa множества U . Решается задача идентификации для множества C/ker. После этого решается задача поиска как можно более широкого класса [t/ker] - замыкания ядра U ксг - систем, совместимых с найденным решением.

В отдельную группу выделен ретроспективный анализ проблем поиска. В качестве базовой модели для поиска безусловных решений выбран источник S = (S,F,sllt,Sfi„) (S - конечное множество ситуаций, F - конечное множество возможно частичных отображений множества S в себя, sm е$ - начальная ситуация, а Sß„ (0^Sß„ сS\{sir}) - множество финальных ситуаций). Операторы определяются как элементы множества F+, а множество L(S) выигрышных операторов состоит из тех, которые переводят ситуацию sjn в множество S/a. Решения определяются как выигрышные операторы, удовлетворяющие заданному комплексу условий. Среди решений выделены минимальные (по длине) и неприводимые (т.е. которые теряют свойство «быть выигрышным оператором» в результате удаления (или, иными словами, вычеркивания) хотя бы одного элементарного оператора). Следующее распространение свойства «быть решением» на множества операторов приводит к понятию кооперативного решения. Пусть зафиксированы симметрические операции а>,:Sx...xS.->S

/раз

(/ =1,...,г). /-кооперативным решением назовем такое множество операторов {F,,...,F,},4to: 1) coj(xlnFl,...,,slnFj)eSflr]-2) (»M„Fh,...,sirlFk)iSß„ (1 < А, <... < А, (i = 2,...j-1)); 3) если L(S)*0, то d(F,) < min d(F) (d(F) -

FeL(S)

длина оператора F). В качестве базовой модели для поиска адаптивных решений выбран источник S = (S,H,sm,Sj-m) (Не F х G), для которого элементарный оператор (f,g)eH интерпретируется следующим образом: / - элементарный оператор в обычном смысле этого слова, а g - имя случая, идентифицированного в результате дополнительного анализа ситуации, к которой применяется /. Адаптивным решением назовем частичное отображение B:G" —>F, удовлетворяющее следующим четырем условиям:

1) AeDomB-,

2) gi---gr g DomBтогда и только тогда, когда g,.■.gr_, е ОотВ, sineDomH (Я = (В(Л), g, )(£(g,), g2).. ... gr_,), gf) ) и

3) если gj...greDomB и g,. ..g,g<£ DomB для всех geG, то ^te..*)"0 (Gs,/={geG|(/,g)eH,56JDom(/,g)}) и ■^(gi—&-)»£') для всех g'eGl B(a ...gr);

4) существует такое число ls, что d(G)<ls для всех GeDomB.

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

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

5. Для заданного источника S построить один, безразлично какой именно, элемент множества Lmm (S).

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

7. Для заданного источника 5 построить один, безразлично какой именно, элемент множества Lcprn,(S) кооперативных решений.

8. Для заданного источника S построить один, безразлично какой именно, элемент множества Udp,v{S) адаптивных решений.

Эти задачи решены в разделе 2.

В отдельную группу выделен ретроспективный анализ задач теории экспериментов со слабоинициачьным автоматом (М,О0), где М = (Q,X,Y,S,1) е АЫп - заданный автомат, а О0 - множество допустимых начальных состояний. Анализ подходов, предложенных А. Гиллом и П. Штарке, показывает актуальность исследования структуры множеств идентифицирующих слов с целью разработки математических основ для унифицированной генерации методов поиска минимальных и неприводимых идентифицирующих слов. Имеется также много невыясненных моментов, связанных с оценками длин минимальных диагностических и синхронизирующих слов. Нижние оценки функций Шеннона L?bm(r) и L'tmn(г) длин минимальных, соответственно, диагностических и синхронизирующих слов для слабоинициального автомата с г допустимыми начальными состояниями, а также нижние оценки функций Шеннона Ldhtm = шах Li (г)

и ПЫп - шах Ь'Ып(г), установленные И.К. Рысцовым и М.Н. Соколовским, объединяет то, что используемые автоматы имеют входной алфавит, мощ-

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

9. Детализировать общие решения задач 4-8 для идентификации внутренних состояний слабоинициальных автоматов.

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

Эти задачи решены в разделе 3.

Проведенный анализ известных аналитических методов построения ДНФ показал, что ни один из них не дает возможность строить простые импликанты, покрывающие заданную точку со сложностью, существенно меньшей, чем сложность построения сокращенной ДНФ. Таким образом, показана актуальность решения следующей задачи.

11. Детализировать общие решения задач 4-7 для построения простых импликант и состоящих из них ДНФ.

Эта задача решена в разделе 4.

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

12. Разработать унифицированные методы анализа и управления для систем в условиях действия нестабильной внешней среды.

Решению этой проблемы посвящен раздел 5.

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

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

Анализ задач 4-7 показывает, что актуальной является разработка метатеории, т.е. средств, позволяющих единым образом представить все многообразие проблем и методов поиска безусловных решений для источника 5 = (8,Г,я1п,8Гт) и выделить факторы, определяющие внутреннюю

сложность решения конкретных задач. Предполагается, что множество решений Г2 = (5) с; ¡-(З) - регулярное и задано характеристической функцией Ха ■ Для его построения в дереве поиска выделяется три типа вершин, а именно: финальные, бесперспективные и порождающие. Таким образом, разработка любой конкретной схемы поиска с необходимостью содержит

доказательство утверждений о том, что вершина г -го уровня является порождающей (соответственно, финальной или бесперспективной) тогда и только тогда, когда выполнен соответствующий комплекс условий. На этой основе разработаны общие схемы (и доказана их корректность) поиска в ширину, поиска с возвращением и метода ветвей и границ, детализации которых и используются в дальнейшем. Эти три схемы имеют экспоненциальную временную сложность. Что же касается емкостной сложности, то она является экспоненциальной только для поиска в ширину и для метода ветвей и границ. Для поиска с возвращением емкостная сложность (при равномерном весе) равна V = 0(Ь0) {Ь0 —>°о), где Ь0 - длина специального конечного дерева, которое может быть свернуто в настроенный автомат, представляющий множество 1~х(5). Показано, что эту оценку можно следующим образом улучшить для важного специального случая.

Теорема 1. Если Р - порождающее множество коммутативной полугруппы, то емкостная сложность построенной схемы поиска с возвращением равна К = 0(|Р|)(£о ->°о).

Базовая модель для поиска безусловных решений определена в работе следующим образом.

Определение 1. Источник 5 = назовем М -источником,

если на множестве 5 задано отношение частичного порядка <!;, удовлетворяющее следующим условиям: 1) если .v, е Б^ и <Л. 5,, то з2 е ; 2) если е Вот/ (/ е Р) и <2 ^, то е Вот/; 3) если 52 <,. .v,, то <,. я,/ для любого такого / е Р, что 5, е йот/.

Обоснование выбора такой модели в качестве базовой состоит в следующем. Наделение структурой частичного порядка - одной из наиболее общих теоретико-множественных структур не накладывает больших ограничений на множество ситуаций. Этот частичный порядок дает возможность сравнивать между собой расстояния от двух ситуаций до множества финальных ситуаций, даже если эти расстояния не известны (т.е. частичный порядок согласован с множествами равноотстоящих ситуаций). Требование монотонноста элементарных операторов становится естественным, если их действия на ситуации интерпретировать как снятие неопределенности. Показано, что ограничения на отношение <5, сформулированные в терминах элементарных операторов, следующим образом распространяются на множество Р*: если то и < , (Р е Р*), где Р* = {Т7 е Р*! .у е ОотР}. Строение минимальных решений для М -источника характеризуется следующим образом.

Теорема 2. Если и с/(Р^) < <1(Рг), то

РгР й 1тт (5) для всех Р е Р*Л .

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

Решение задачи 5 сведено к построению ядра L™" (S) множества rin(S), определяемого условиями: I) L™ (S) с Г" (S); 2) построение Lnk"" (5) осуществляется наименее сложным образом; 3) L™" (S) * 0 тогда и только тогда, когда Lm,n (S) * 0. С этой целью в дереве поиска выделено i -характеристическое множество вершин (г = 0,1,...), являющееся минимальным по мощности подмножеством вершин г -то уровня, отметки которых -все минимальные элементы множества отметок вершин /-го уровня. Показано, что каждое /-е характеристическое множество порождает некоторое (/' + 1)-е характеристическое множество. На этой основе определены множества порождающих, бесперспективных и финальных вершин, детализирована общая схема поиска в ширину для построения множества L™" (S).

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

Строение неприводимых решений для М -источника характеризуется следующим образом.

Теорема 3. Если для оператора F е Ft* существует представление

F = FtF2 (F„F2 е F+), где sf„F} <s smF, то FF3 t L!r(S) для всех F3 e .

На основании этой теоремы определены множества порождающих, бесперспективных и финальных вершин, детализирована общая схема поиска в ширину для построения множества L э L'r (S), из которого множество L'r(S) выделяется методом решета.

Для решения задачи 7 предполагается, что (S,<s) - нижняя полуструктура, т.е. в качестве операций а>. выступает операция gib, что дает возможность легко модифицировать алгоритм построения множества Ц!'" (S) для построения кооперативного решения.

Базовая модель для поиска адаптивных решений определена в работе следующим образом.

Определение 2. Источник S ={S,H,sjn,Sfm) (HcFxG) назовем AM -источником, если на множестве S задано отношение частичного порядка <s, удовлетворяющее следующим условиям: 1) если 5, е Sfill и sz <s st, то

e Sfi„; 2) если 5, e Dom(f,g) ((/,g) eH) и s2 <s s„ то 0 * G,2/с G,b/; 3) если s2 <s , то í2(/,g)<s ^(/.g) для любого такого ,v, eDom(f,g), что geGía/.

Определим на множестве

I = {сг е B(S) | (Vs,,s2 е ct)(j, ф í, => О, s2) л (s, д,))} отношение частичного порядка <2 следующим образом;

с, <s сг2 о (VÍ, е а, )(Э.?2 е ег2)(л-, <s. ,v2). Элементы множества F будем рассматривать как такие, возможно частичные, отображения /:L~>Z (/еF), что значения qf (exеZ,/eF) вычисляются в соответствии со следующим алгоритмом:

1. Если существует такое sea, что Gt = 0, то qf не определено.

2. ^UW.gNgeG*,}-

sea

3. Вычислить множество сг2, состоящее из всех максимальных по отношению <s элементов множества ст,.

4. qf:=cr2\ S/lrl и конец.

Сопоставим с АМ -источником S источник C(S) = (Z,F,{í,„},{0)) . Доказаны следующие важные свойства источника C(S).

Теорема 4. C(S) является М -источником.

Теорема 5. Существует конструктивный способ построения по каждому неприводимому решению F б L'r (C(S)) некоторого адаптивного решения BfgL"Jp"(S).

Таким образом, установлено общее соотношение между АМ -источником и М -источником.

На основе исследования структуры адаптивных решений АМ -источника S получено решение задачи 8. Сворачивание дерева, представляющего адаптивное решение, в автомат Мура, дает унифицированный метод построения автоматов-экспериментаторов.

Дальнейшим развитием полученных результатов является решение проблемы поиска множества VA всех неприводимых множеств представителей семейства множеств А = {а1}1е[. Элементами множества VA являются все такие множества V с \Ja,, что: I) V п а: ф 0 для всех е /; 2) для лк>-

/е/

бого VjdV существует такое i el, что V¡ nal = 0. Эта проблема естественно возникает в процессе решения как фундаментальных, так и прикладных проблем дискретной математики. В работе показано, что к ней, в частности, сводятся поиск базисов для булевых функций и поиск всех неприводимых диагностических тестов для одноуровневых комбинационных схем.

Исследуем структуру множества УА. В работе показано, что без ограничения общности можно считать, что семейство А состоит из непустых попарно не сравнимых по отношению включения с множеств. Отношение эквивалентности рс:АхА, определяемое соотношением: сс1ра) тогда и только тогда, когда существует такая конечная последовательность а1 = а,ь ,..= а} элементов семейства А, что а^ п,аКл ф 0 для всех г = 0,1,...,и-1, определяет разбиение пр-{А) семейства А,

значение которого состоит в следующем.

Теорема 6. Если VJ е УА. ( / е /), то и е УА. Обратно, любое не' 1<л

приводимое множество представителей V еУА единственным образом может быть представлено в виде V =1) У], где V) е УА (_/ е 3).

Таким образом, найдены конструктивный метод распараллеливания вычислений при построении множества УЛ и способ компактного хранения элементов множества УА. Определим отображение : и а -> В(А.)

равенством (р)(у) = {а е А;, | Vеа}. Показано, что УА]/кар, = УА. /кег ру, что позволяет произвести дальнейшее упрощение построения множества УА и сократить затраты памяти, необходимой для хранения элементов множества УА. Определим отображение Ф,:( и а)/кепр. —>В(А /кег® .) равенством Ф; ([у]ксг^. ) = {aeAJ /кег^ | Мксг^ е а}. Строение множества определяется следующим образом.

Теорема 7. Если IV - множество представителей семейства множеств А]/Ыг<р], то IV е тогда и только тогда, когда ни один элемент

Мкяр е И7 не удовлетворяет включению

Это означает, что УА./ксгф. является множеством всех максимальных по включению элементов множества В'(( и а)/кет<р.), полученного из

множества В(( и а)/кст<р ) в результате удаления множеств в соответствии со следующими двумя правилами:

1) множество IV е В(( и а) / кег ср ) удаляется, если существует такое WiclW,чтoФj(Wt) = ФJ(Ж);

2) если удаляется множество Ж, то удаляются и все такие множества е В(( II а)/кегрДчто Ш2 эГ.

Отсюда вытекает, что если А] I кет <р] - конечное семейство конечных множеств, то множество может быть построено последовательным, поуровневым восстановлением полуструктуры В'(( и а)/кег?>у).

Таким образом, в разделе 2 впервые разработана завершенная общая теория поиска, включающая в себя в качестве специальных случаев классические теоретико-множественный подход и подход, основанный на оценивании, на основе которой получено полное решение задач 4-8. Исследования в двух следующих разделах во многом основаны на развитии и детализации моделей и методов настоящего раздела.

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

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

Для решения задачи 10 разработан общий метод построения экспоненциальных нижних оценок для функции Шеннона. Суть этого метода состоит в следующем. Известно, что если / = 0 .../) е8(п), где /3. -

цикл длины А, то |/| = #СЩг,,...,/}). Используя подстановку

1

f = Dr+l...D2reS(n), где г =

■(V24/I + 1-1

6

удалось получить следую-

щую асимптотическую оценку для функции Шеннона L(n) = max I f \

/<!.Ч'(")

Теорема 8. L(n) > е0(Л) (и -н> ад).

Теорема 9. При п =

+1 справедлива следующая

Как следствие, получен ряд экспоненциальных нижних оценок, характеризующих выразительную мощность симметрической группы S(n): порядок циклической подгруппы, порядок нормальной подгруппы, мощность централизатора подгруппы в S(n).

Используя найденную подстановку, удалось построить автоматы, на основе которых доказаны следующие теоремы.

—(л/24£- 23 +1 6

оценка функции Шеннона для длин минимальных диагностических слов для слабоинициального автомата с двухбуквенным входным алфавитом

Ы2„>е'** (*_>«,).

Теорема 10. Справедлива следующая оценка функции Шеннона для длин минимальных синхронизирующих слов для слабоинициального автомата с двухбуквенным входным алфавитом

Пк2„>е0^ (*->«).

L"

Рассмотрим функцию Шеннона L"omH(k,m,n) = (и е {d,s}). Из

кт

теорем 9 и 10 вытекает, что C'omtl(k,2,n)>e0(-^">nk) (к—» оо)для ue{d,s}. Этот факт является принципиально новым моментом, так как из известных результатов И.К. Рысцова и М.Н. Соколовского вытекало только, что П'отн(к,т,п)> 0(1) (£-> °о). Фундаментальное значение теорем 9 и 10 состоит в том, что любой алгоритм построения диагностических или синхронизирующих слов для слабоинициального автомата, основанный на восстановлении отрезков, длина которых ограничена площадью автоматной таблицы, заведомо имеет экспоненциальную сложность (как временную, так и емкостную).

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

При исследовании автомата, как абстрактной системы, состоящей из трех абстрактных множеств (множество состояний, входной и выходной

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

Зафиксируем класс автоматов АЫп. Пусть заданы группы = (О,,°) и = (&,,•). Обозначим через РЫл(С,,С2) множество всех упорядоченных наборов отображений Ф = (р,,...,р6), где <р[ :Ок->С1, <р2: X т —>01, <Ръ •' бс > <Ръ -> с2, : У„. Каждому набору

отображений Ф = (^,,...,(г>6)еГАгт/,(С1,С2) поставим в соответствие такой автомат Аф — (Ок, X т, Уп, ¿'ф, Лф), что 8Ф

Лф(д,х)=--(р6(ср^(д)*<р5(х)) для всех деОк и х е Хт. Положим Л-™(С1,С2)={Л|Ф6РЫ„(С1,С2)}.

Определение 3. Представлением автомата М е АЫп группами Э, и Э2 назовем такой набор отображений Фм е (О,, С2), что М = АФм .

Следующая теорема указывает конструктивный способ расширения множества представлений автоматов М е АЬпп.

Теорема 11. Если (С,''1! / е 14} и {С^' | / е N1 - такие последовательности групп,что 0'1} <С'" <...<<... (у = 1,2),то

Установлены следующие достаточные условия;при которых верхняя граница А^ достижима.

Теорема 12. Если в, и Э2 - такие группы, что Ъ, < 0>{ (/=1,2), где тт{/„/2} , то = Л™■

Рассмотренные представления автоматов М е АЫп группами О, и (Э2 на каждом такте осуществляют вычисления по схеме:

кодирование —»групповая операция —»декодирование. Такая схема не удобна при работе с расширениями функций переходов и выходов на множество 0,. х X*. Поэтому естественно потребовать, чтобы для функции переходов кодирование осуществлялось только в начале

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

Определение 4. Представление Фи авто-

мата М е Актп группами Э, и Э2 назовем согласованным с функцией переходов, если (д, р) = <р" {<р" (д) о (р)) для всех д е ^ и р е Х'т.

Установлен следующий критерий принадлежности представления ФеРЬм(0„С2) множеству Р*т„(С1,С2) согласованных с функцией переходов представлений

Теорема 13. Для любых групп = (С^0) и Э2 представление Ф = (г/),,... ) е Ркп:п (С,, (32) согласовано с функцией переходов тогда и только тогда, когда существует такое расширение ¡р2 отображения (р7:Хт ->О, на множество А'*, что для всех деОк, ре Х'т истинными являются равенства (^1 ° (Р^)) = ^э (^з 0 <Р») ° и

Из этого критерия вытекает, что если Ф = {(ри...,<р(1)е Р^,„(С,,С2), то: 1) :Ок -»(?, - инъективное отображение; 2) <ръ:С, ()к - сюръек-тивное отображение; 3) (ръ - инъективное отображение.

Найдена следующая важная алгебраическая характеристика для представлений, согласованных с функцией переходов.

Теорема 14. Если Ф = (р1,...,р6)еР4ст„(01,С2), причем ^2(Л) = 1с.и (Уа!гр^о (Уа1 <р7) = Уа1(р1, то расширение 'ф2 отображения <р2: Хт на множество Х*т является гомоморфизмом свободной полугруппы {Х*т,-) в группу .

Из инъективности отображения <рх вытекает, что = 0

для любой группы порядка меньшего, чем к. Следующая теорема показывает, что это - точная оценка.

Теорема 15. Для всех к> 2 и т > 1 существуют такие группы С, порядка к, что Р^„(О„С2)*0.

Множество представлений ^((З^С^) естественно приводит к множеству автоматов А1тп(С1,в2) = {Аф е А^^О^ФеР^С^С,,)}. Доказано, что в случае, когда С, - группа порядка к, структура этих автоматов описывается следующим образом.

Теорема 16. Если Ф = (^1,...,^6)еР;°л„(01,С2), где Э, - группа по/ л к рядка к, то автомат Аф состоит из - компонент сильнои связанно-

I Уа1рг I

сти, каждая из которых содержит | Уа1 <р21 состояний.

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

Таким образом, в разделе 3 впервые разработан завершенный фрагмент комбинаторно-алгебраической теории, предназначенной для анализа конечных автоматов, на основе которой получено полное решение задач 9 и 10.

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

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

мы (и исследована их сложность) для поиска одной (безразлично, какой именно) и всех простых импликант, покрывающей заданную точку я е , поиска состоящей из простых импликант ДНФ длины, не превосходящей 1^1 и поиска сокращенной ДНФ. Эти алгоритмы и являются вычислительной основой для разработанной в работе теории управляемости/наблюдаемости булевых функций.

Пусть /¿¡^ ~ булева функция, полученная из булевой функции /еР2(п) заменой переменных х, ...7х,г, соответственно, значениями о-„...,егге{0,1}.

Определение 5. Для булевой функции / е Р7 (п) назовем множество я = = 1,...,г} <...<(г <п;а],...,аг е{ОД}): 1) множеством

а-управляемости, если = а; 2) множеством (/, а) -наблюдаемости

(ге{1,...,л}\.....¡,},ае{ОД}), если

Обозначим через (а,/) и БстЫ(а,/), соответственно,

множество всех, всех неприводимых (т.е. минимальных по включению) и всех минимальных (по мощности) множеств а -управляемости для булевой функции / еВД, а через (/',«,/), 5° (',«,/) и - множество

всех, всех неприводимых и всех минимальных множеств (/,#)-наблюдаемости для булевой функции / е Р2 (и). Положим с («,/)=( л-1, где ^ е ^¡„(а,/) и °(',«,/) =1 ^ где (/,«,/) и будем считать, что

°(а,/) = оо (соответственно, °(/,а,/) = °о), если Бс(а,/) = 0 (соответственно, 5,°(7,а,/) = 0).

Определение 6. а-управляемостью, (/,а)-наблюдаемостью и г-наблюдаемостью булевой функции / еР2(п) назовем , соответственно, параметры с («,/), Ч'>,/)и °(/,/) = тш{V"(/,0,/),V ° (/',1, /)}.

Пусть 5 = {(^,о-у)|у=1,...,г} (1</, <...<гг<«;ст1,...,о-гб{0,1}). Положим /Г(л') = л • Доказано, что неприводимые множества управляемом '

сти/наблюдаемости для булевой функции / б Р2(п) имеют следующую структуру.

Теорема 17. Для всех булевых функций /еР2(п): 1) деб^а,/) тогда и только тогда, когда К (я) е ; 2) 5 е 5° (/,«,/) тогда и только тогда, когда хс'К(8) е где /1а - такая булева функция, что множество Ыг состоит из всех таких наборов (Д,...,Д_|,а,Д+1,...,/5п)еЯ/, что (Д,...,Д_„а,Д+1,...,Д)^.

Следовательно, сложность построения множеств ^¡п(а,/) и ('>«>/)> а также вычисления параметров "(а,/), 0(/,«,/) и "(/',/) определяется сложностью построения соответствующих сокращенных ДНФ. При этом справедливы следующие оценки

Теорема 18. Для почти всех булевых функций / б Р2 (и) при всех /е {1,...,«} и ае {ОД}, если и —о, то:

1) для почти всех 5е5°(а,/)и5°(/',а,/);

2) л-^и + 2£у<и-1ов1ояи + 1 (ке{/(а,/),/((',й,/)});

3) 1^>,/)|=о(|5;(а,/)|) и |51(/,а,/)|=о(|^0',а,/)|).

Это означает, что осуществляя поиск одного, безразлично какого именно, множества .V е (а,/) (или множества .V е Б°(1,а,/)) и выбирая значение в качестве приближенного значения с(а,/) (соответствен-

но, ° (/,«,/)), мы почти всегда будем допускать погрешность вычисле-

У1

ний, не превосходящую величины А = -)) (п -> со).

1о %п

Развитые средства следующим образом распространяются на композицию /^Х булевых функций /"(*,,...,*„) и g^0>я,...,^^,/)

0=1,...,£).

Если композиция - бесповторная, то построение одного, безразлично какого именно, множества: 1) ) осуществляется заменой в

множестве 65°(а,/) каждой пары {¡},ст}) (у=1 ,...,к) множеством sJeS°r(orJ,gJ)■, 2) 5 6(/,«,/;;;■ осуществляется при (у = 1,...,/с) заменой в множестве sleS°(i,a,f) каждой пары (у = 1,...,&) мно-

жеством е S°r(o^J,gf), а при г = А/А - заменой в множестве „V, е 5°(/,«,/) (соответственно в множестве ^ е 5°(;,а,/)) каждой пары (Г,сг;) (7 = 1,...,А) множеством е(ст,,gJ.) и добавлением к полученному множеству множества, б5,°(А/А,1,/) (соответственно, множества, е^ДА/^О,/)). Построение множеств и )

осуществляется посредством всевозможных таких замен. Вычисления параметров с(а,/'!) и следующим образом сводятся к

6] 1 "»оЛГ о1'"'»о*

арифметическим действиям над значениями с(а,/), c{<J|,g,), °(/,а,/) и °(А/Л,а,/). Пусть

[1, если /е {1,...,л} \

Г

Для элементарной конъюнкции К = /\х"' положим ¿и(К) = ), счи-

ы ' м "

тая, что а + оо = оо + я = оо + оо = со. Тогда '(а,/''.....) = min ß(K(s)) и

s'.....' ',(«./)

Imin /i(K(s)), если г е {1,..., л} \ {/',,..., L}

mm{Fj,v2}, если/ = hl {h = ¡¿,1 =\,...,т}} где ,= min n(K{s)) + v°(hl,\,gh) и 2= min /i(tf(j)) + ve(A/,0,gJ.

Если же композиция не является бесповторной, то посредством замены в сокращенной ДНФ DJ'4' каждого литерала сокращенной ДНФ

DcoJp строится ДНФ D, раскрываются скобки, осуществляется переход к

сокращенной ДНФ Dc°*p , а затем осуществляется анализ последней методом, изложенным выше.

Развитые средства являются основой для конструирования совместимой с системой моделирования электронных схем подсистемы, предназначенной для вычисления параметров управляемости и наблюдаемости узлов комбинационных схем, а также для построения входных наборов, обеспечивающих требуемые значения в заданных узлах, что, в конечном итоге,приводит к автоматизации процесса построения тестов для комбинационных схем . Такая подсистема состоит из пяти блоков. Блок 1 формирует описание исходной схемы в терминах элементов, выбранных в качестве стандартных. Для каждого такого элемента БИБЛИОТЕКА, организованная в блоке 2, содержит описание неприводимых множеств и параметров управляемости и наблюдаемости. БИБЛИОТЕКА допускает пополнение, осуществляемое с помощью блоков 3 и 4. Блок 3, взаимодействуя с системой моделирования, формирует исходные данные для блока 4, основу которого составляют разработанные в работе алгоритмы построения простых импликант и состоящих из них ДНФ. Блок 5 вычисляет множества и параметры управляемости и наблюдаемости для композиций. В случае получения неудовлетворительных результатов, вызванных наличием сходящихся разветвлений, соответствующий фрагмент схемы объявляется стандартным элементом, его характеристики вычисляются и заносятся в БИБЛИОТЕКУ. Описание схемы переделывается соответствующим образом и производится анализ преобразованной схемы.

Идентификация булевых вектор-функций является актуальной проблемой дискретной математики и имеет многочисленные приложения. Традиционный подход к ее решению основан на методе полного перебора и имеет экспоненциальную сложность (как временную, так и емкостную). Один из способов понижения сложности состоит в замене (там, где это возможно) перебора алгебраическими операциями. Именно такой подход к решению проблемы идентификации булевых вектор-функций, основанный на теории векторных пространств над конечными полями, разработан в работе. График graph / = {(al,...,ani+„)\f((a„...,aj = (a!ti+1,...,am+lt)} булевой функции /^ОД}'" -»{ОД}" является подмножеством линейного пространства GFm+"(2). Доказана следующая особенность структуры множества graph f (/e Ртп = (Рг{т))п).

Теорема 19. Для любой функции / е (Т0(т))" истинным является равенство graph / = U V, где Lin graph f - множество всех макси-

VcLifi graph f

мальных по включению подпространств линейного пространства GF'"+"(2), содержащихся во множестве graph f.

Так как gQ = /(•) +ДО)6 (Та(т)У для любой булевой функции / е РЯ1Л, то можно ограничиться исследованием только булевых функций, принадлежащих множеству (Т0(т))п. При этом, теорема 19 обосновывает определение следующей конструкции.

Определение 7. Линейной характеристической функцией множества graph f назовем такое множество Xf = | ' = 1,...,/} матриц над полем

GF(2), что для любого вектора ае{0,1}т+" равенство лМ. = 0 - истинное хотя бы для одного значения ге{!,...,/} тогда и только тогда, когда а е graph f.

Доказано, что построение линейной характеристической функции осуществляется следующим образом.

Теорема 20. Для булевой функции / g (Та(т))" линейная характеристическая функция имеет вид Z/ - {Ev \ V е Lin graph /}, где Ev - матрица порядка (т + п)х (т + п-DimV), столбцами которой являются векторы ej,...,em+„_DimK, образующие базис ортогонального дополнения Vх.

Получены следующие характеристики сложности «расщепления» множества graph f (/ е (Т0(т))п) на подпространства, принадлежащие множеству Lin graph /•

Теорема 21. Для любого от е N при всех п е N существует такая функция / е (Т0 (m))", что | Lin graph f |= 2m -1.

Теорема 22. Для любых т,пе N и / = + 0,25 - существует такая функция f е(Т0(т))", что множество Lin graph f содержит последовательность подпространств К,,..., К,, удовлетворяющую следующим условиям: 1) DimVk = к (к = 1,...,/): 2) пГ = {0} для всех таких /,У = 1,...,/, что

Развитые средства дают возможность для заданных булевой функции / еРт„ и множества Пс{0,1}™4" осуществлять проверку истинности включения Q ç graph f с помощью следующего алгоритма:

1. Если/*(Г0(м))", то /(•)•-/О +/(°)> f2:=Q + /(0).

2. xf := iEv IУ 6 Lin graph /}.

3. Вычислить Xf (а) = {яЕу \V е Lin graph/} для всех а б il.

4. Если 0eXf(a) Д™ всех то включение Q с graph f - истинное, иначе включение ложное.

Программная или аппаратная реализация этого алгоритма может быть использована для конструирования унифицированных средств как on-line, так и off-line контроля комбинационных схем.

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

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

Пятый раздел посвящен разработке основ теории, предназначенной для исследования систем, подверженных дестабилизирующим воздействиям внешней среды (ДДФ-систем). Построение аксиоматики такой теории является актуальным,т.к. она дает возможность «вложить» ДДФ-системы в математическую теорию систем и, следовательно, использовать весь арсенал ее методов и средств. В качестве основного понятия выбран дестаби-лизатор Б, представляющий собой множество наборов отображений и операторов, действующих на объекты идеальной модели (т.е. эталона). С помощью этого понятия ДДФ-система может быть определена либо как упорядоченная пара (5,0), где 5 - идеальная модель, либо (что, по сути, то же самое) как семейство обычных систем А = {5Л | «1 е Б}. Обеспечение условия 5 е А дает возможность исследовать идеальную модель в терминах ДДФ-систем. В работе построена иерархия ДДФ-систем в соответствии с иерархией математических моделей систем, разработанной М. Меса-ровичем и Я. Такахарой. Кроме того, на ДДФ-системы распространены операции замыкания обратной связи, параллельного и каскадного соединений. Таким образом, в работе разработаны основы как абстрактной, так и структурной теорий ДДФ-систем.

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

ний внешней среды. Стандартными методами вычисляются коэффициенты влияния (относительная релевантность) ггти (х}) и значимость

5(лг,) = гт,я(х])Н(х]) (Я - энтропия) каждой независимой переменной х] (у = 1,...,/) на исследуемую ДДФ-систсму. Принципиально новым моментом является использование порога а > О для разбиения множества {*!,...,*,} на классы Ссущ = {х е {*,,..| ¡п^/•„„,„*(<))> а} существенных

и Скаущ ={хе{х1,...,х,}\М готнх^У)<а} несущественных переменных.

Последние, на данном этапе, вообще могут быть исключены из рассмотрения. Таким образом, в модель заложен некоторый вариант нестационарного решета, позволяющий динамически изменять размерность механизма адаптивного управления за счет добавления или удаления независимых переменных, характеризующих состояние внешней среды (что автоматически влечет за собой изменение функции полезности). Вторым принципиально новым моментом является использование порога @ > 0 для разбиения множества ,..., х1} на классы Узт = {х е {х,,..., х,} | ¡п^ .у(х(г)) > /?}

значимых и ¥нат = {х е (х,,.. < /?}. Дополнительное иссле-

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

множества независимых переменных. Использование этой меры в системе имитационного моделирования дает возможность выявлять ситуации, требующие наиболее тщательного отслеживания. Развитые средства являются основой для построения следующего механизма контроля и адаптации ДДФ-системы к условиям нестационарной внешней среды (через £],$ и

Е^,Д - обозначены, соответственно, нижние и верхние границы изменения

переменных х} и г):

1. Если е] < х] < EJ для всех у = 1,...,/ и 3 < г < А, то никаких изменений в стратегии управления ДДФ-системой не производится и конец, иначе переход к шагу 2.

2. Если е} <х]<И] для всех у =1,...,/ и г <8, то переход к шагу 3, иначе переход к шагу 4.

3. Стратегия управления ДДФ-системой на оставшемся промежутке времени должна быть переработана, так как проявились ошибки, допущенные при ее разработке и конец.

4. Если е]<,х]< Е; для всех / = 1,...,/ и г > Д, то переход к шагу 5, иначе переход к шагу 6.

5. Стратегия управления ДДФ-системой на оставшемся промежутке времени должна быть переработана, так как либо было выбрано не наилучшее решение, либо не полностью учтены благоприятствующие факторы внешней среды и конец.

6. Стратегия управления ДДФ-системой на оставшемся промежутке времени должна быть переработана, так как исходные предпосылки, лежащие в основе применяемой стратегии, перестали быть истинными и конец.

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

Таким образом, в разделе 5 впервые разработан новый фрагмент математической теории систем - теория ДДФ-систем, предназначенный для анализа систем, подверженных дестабилизирующим воздействиям внешней среды. Получено решение задачи 12.

В заключении сформулированы основные результаты работы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Итоги проведенных в диссертационной работе исследований могут быть кратко сформулированы в следующем виде:

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

2. Впервые получено полное решение задачи поиска множества всех неприводимых множеств представителей заданного семейства множеств.

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

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

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

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

6. Впервые исследовано представление функций переходов и выходов конечных автоматов конечными группами. Тем самым создан эффективный математический аппарат для исследования автоматных моделей методами теории групп.

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

8. Впервые разработаны более простые, чем известные аналитические, общие комбинаторные методы поиска всех и одной простых импли-кант, покрывающих заданную точку, а также ДНФ, состоящих из простых импликант.

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

10. Впервые разработан метод идентификации булевых вектор-функций на основе теории линейных пространств над конечными полями. Тем самым создан эффективный математический аппарат для решения задач контроля правильности функционирования комбинационных схем.

11. Разработан метод идентификации неисправностей для схем с памятью методом выделения ядра, основанный на использовании булевых матриц.

12. Построен фрагмент математической теории систем, предназначенный для исследования систем, находящихся под действием дестабилизирующих факторов внешней среды. Решена задача адаптивного управления ДДФ-системой методами теории информации.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Скобелев В.Г. Построение автоматов-экспериментаторов // Методы диагноза и контроля сложных дискретных систем и автоматов. - Киев: Ж АН УССР, 1973. - С. 32-44.

2. Богомолов A.M., Скобелев В.Г. Об одном алгоритме решения диагностической и установочной задач с автоматом // Кибернетика. - 1975.

- № 6. - С. 1-6.

3. Скобелев В.Г. Построение меры для оценки диагностических свойств класса автоматов // Методы диагноза и контроля сложных систем и автоматов (Препринт 76-18). - Киев: ИК АН УССР, 1976. - С. 31 -37.

4. Скобелев В.Г. Неприводимые множества представителей семейства множеств // Дискретные системы, формальные языки и сложность алгоритмов. - Киев: ИК АН УССР, 1977. - С. 54-65.

5. Скобелев В.Г. Построение минимальных диагностических слов восстановлением их финальных отрезков // Дискретные системы, формальные языки и сложность алгоритмов. - Киев: ИК АН УССР, 1978.

- С. 75-83.

6. Скобелев В.Г. Некоторые оценки для автономных автоматов // Методы проектирования схемного и программного оборудования ЭВМ. -Киев: ИК АН УССР, 1979. - С. 42-55.

7. Скобелев В.Г. Локализация кратных неисправностей магнитной большой интегральной схемы (МБИС) «Ассоциативное ОЗУ // Вопросы технической диагностики. - Ростов-на-Дону: РИСИ, 1980. -С. 38-42.

8. Скобелев В.Г. Метод поиска минимальных выигрышных решений в классе W-задач и его применение к построению минимальных диаг-

ностических слов // Методы и системы технической диагностики. Вып. 1. - Саратов: Изд-во Сарат. ун-та, 1980. - С. 27-39.

9. Скобелев В.Г. О некоторых задачах перечисления конечных автоматов // Докл. АН УССР. - 1980. - № 12. - С. 64-66.

10.Скобелев В.Г. Методы построения минимальных диагностических слов для автомата и сложность их реализации // Автоматика и телемеханика. - 1981. -№ 6. - С. 162-169.

11.Скобелев В.Г. Алгоритмы и сложность распознавания внутренних состояний конечного автомата // Докл. АН УССР. - 1981. - № 7. -С. 71-74.

M.Skobelev V.G. On finding of minimal distinguishing sequences for finite automaton // Diagnostika a zabezpeceni cislovych system. - Brno, ZARI, 1981.-P. 145-151.

13.Скобелев В.Г. О перечислении возвратных автоматов // Кибернетика.

- 1984.-№ 5.-С. 120-122.

14.Скобелев В.Г. О сложности поиска диагностических и установочных слов для конечного автомата // Кибернетика. - 1985. - № 4. - С. 116118.

15.Скобелев В.Г. Об оценках длин диагностических и возвратных слов для автоматов // Кибернетика. - 1987. - № 4. - С. 114-116.

16.Скобелев В.Г. Управляемость и наблюдаемость для булевых функций и их композиций // Докл. АН УССР. - 1987. - № 7. - С. 65-67.

17.Скобелев В.Г. Об исследовании управляемости комбинационных схем // Автоматика и телемеханика. - 1988. - № 1. - С. 136-141.

18.Скобелев ВТ. Анализ управляемости и наблюдаемости комбинационных схем // Электронное моделирование. - 1989. - № 1. - С.63-67.

19. Скобелев В.Г. Комбинаторные алгоритмы построения дизъюнктивной нормальной формы (ДНФ) // Докл. АН УССР. - 1989. - № 2. -С. 72-75.

Ю.Скобелев В.Г. Об одном методе минимизации булевых функций автоматов // Кибернетика. - 1989. - № 5. - С. 44-48.

21. Скобелев ВТ. О реализациях булевых функций на мультиплексорах. // Теория и моделирование управляющих систем. - Киев: Наукова думка, 1989.-С. 52-56.

22.Скобелев ВТ. Поиск на частично упорядоченных структурах // Украинский математический журнал. - 1992. - № 2. - С. 253-260.

23.Скобелев ВТ. Представление автоматов группами // Украинский математический журнал. - 1992. -№ 10. - С. 1412-1416.

24.Скобелев ВТ., Сперанский Д.В. Идентификация булевых функций методами линейной алгебры // Украинский математический журнал.

- 1995. -№2. -С. 260-268.

25.Скобелем В.Г. Общерекурсивная модель секретного замка // Докл. НАН Украины. - 1995. - № 6. - С. 73-75.

26.Skobelev V.G. Problem-solving: combinatorial-algebraic appioach // ZAMM. - 1996. - P. 583-584.

21 .Скобелев В.Г. Построение нижних экспоненциальных оценок // Докл. НАН Украины. - 1997. - № 3. - С. 115-117.

28.Скобелев В.Г. Некоторые метрические соотношения в симметрической группе подстановок // Идентификация и моделирование управляющих систем. - Киев: Наукова думка, 1997. - С.5-9.

29.Скобелев В.Г., Христиановский В.В. Исследование систем в условиях дестабилизации. - Донецк: ДонГУ, 1997. - 106 с.

30.Скобелев В.Г., Христиановский В.В. Системы под действием дестабилизирующих факторов: аксиоматический подход // Докл. НАН Украины. - 1998. - № 5. - С. 99-104.

31. Скобелев В.Г. Поиск адаптивных решений на частично упорядоченных структурах // Искусственный интеллект. - 1999. № 1. - С. 6-11.

32.Skobelev V.G. Design of irreducible sets of representatives for a family of sets//ZAMM. - 1999. -P. 915-916.

ЪЪ.Скобелев В.Г. Композиции ДДФ-систем // Докл. НАН Украины. -2000.-№ 1.-С. 82-85.

34.Скобелев В.Г. Представление автоматов группами // Украинский математический журнал. - 2000. -№ 10. - С. 1397-1404.

3 5. Скобелев В.Г. Общие схемы поиска решений на частично упорядоченных структурах // Труды ИПММ НАН Украины. - 2000. - № 5. -С. 132-140.

36.Пилюшежо B.J1., Скобелев В.Г. Адаптивное управление ДДФ-системами // Докл. НАН Украины. - 2000. - № 11. - С. 135-138.

ЪП.Скобелев В.Г. Общие схемы поиска безусловных решений систем // Докл. НАН Украины. - 2000. - № 12. - С. 82-86.

38.Skobelev V.G. Algebraic models for discrete systems' analysis // Mathematical Notes, Miskolc. - 2001.-N 1. - P. 61-68.

39.Скобелев В.Г. Анализ дискретных систем. - Донецк: ИПММ НАНУ, 2002.-172 с.

Лицензия ИД №06268 ог 14.II.01

Подписано в печать 30.10.02 Формат 60x84 1/16

Бум. тип. Усл. печ.л. 1,86 (2,0) Уч.-изд.л. 2,0

Тираж 100 экз. Заказ НЪЧ Бесплатно

Саратовский государственный технический университет 410054 г. Саратов, ул.Политехническая, 77 Копинришер СГТУ, 410054, г. Саратов, ул. Политехническая, 77

ВВЕДЕНИЕ.

1. МОДЕЛИ И МЕТОДЫ ТЕОРИИ СИСТЕМ.

1.1. Основы математической теории систем.

1.2. Проблемы идентификации систем.

1.3. Конечные автоматы.

1.4. Булевы функции.

1.5. Поиск.

1.6. Выводы.

2. ПОИСК НА ЧАСТИЧНО УПОРЯДОЧЕННЫХ СТРУКТУРАХ.

2.1. Общие схемы поиска безусловных решений.

2.2. Л^-источник.

2.3. Поиск безусловных решений для .М-источников.

2.4. АМ-источник.

2.5. Поиск адаптивных решений для AM-источников.

2.6. Неприводимые множества представителей семейства множеств.

2.7. Выводы.

3. АНАЛИЗ КОНЕЧНЫХ АВТОМАТОВ.

3.1. Поиск идентифицирующих слов.

3.2. Построение нижних экспоненциальных оценок.

3.3. Сложность поиска минимальных идентифицирующих слов.

3.4. Оценка диагностических свойств класса автоматов.

3.5. Построение автоматов-экспериментаторов.

3.6. Представление автоматов группами.

3.7. Рекурсивная модель секретного замка.

3.8. Выводы.

4. АНАЛИЗ БУЛЕВЫХ ФУНКЦИЙ.

4.1. Комбинаторные алгоритмы построения ДНФ.

4.2. Управляемость.наблюдаемость булевых функций.

4.3. Идентификация булевых вектор-функций.

4.4. Идентификация неисправностей выделением ядра.

4.5. Выводы.

5. ДДФ-СИСТЕМЫ.

5.1. Основные понятия и определения.

5.2. Композиции ДДФ-систем.

5.3. Адаптивное управление ДДФ-системами.

5.4. Выводы.

Актуальность. В настоящее время бурно развивается теория дис-' кретных систем. Это развитие происходит путем возникновения ряда слабо взаимосвязанных недостаточно теоретически проработанных разделов, часто возникающих из прикладных проблем. Как следствие, многообразие различных моделей, как правило, нечисловой природы (т.е. таблицы, размеченные графы, теоретико-множественные и лингвистические конструкции и т.д.), основным методом исследования которых является более или менее разумно организованный перебор вариантов, т.е. поиск. Отмеченные особенности в полной мере проявили себя в возникших в последнее время системах дискретных событий (discrete event systems) и отмеченных системах переходов (labelled transition systems). Этим разделам ежегодно посвящается значительное число конференций, симпозиумов и публикаций, основной итог которых - результаты ^ дескриптивного плана.

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

Ретроспективный анализ дает возможность выявить следующие существенные моменты. • Теория систем существует уже более полувека. Ее становление, как самостоятельной науки, тесно связано с именами М. Арбиба, JI. Берта-ланфи, Р. Калмана, В.М. Матросова, М. Месаровича, П. Фалба. Однако, до сих пор отсутствует общепринятый аксиоматический подход к теории систем, позволяющий с единых позиций эффективно исследовать весь комплекс возникающих проблем. Более того, зачастую происходило независимое развитие теорий непрерывных и дискретных систем, вспоминающих друг о друге только при исследовании гибридных моделей.

Проблеме идентификации уделялось большое внимание с самого начала становления теории систем, как математической науки. Первый крупный успех связан с разработкой Р. Калманом алгебраической теории идентификации для достаточно узкого, но, в то же время, достаточно важного класса линейных систем. Безусловным достоинством этой теории является то, что она дает унифицированный метод исследования как непрерывных, так и дискретных линейных систем. Совершенно иная картина имеет место при выходе за класс линейных систем. Трудами многочисленных исследователей была создана теория идентификации непрерывных систем. Предмет ее исследования - идентификация методами математического анализа и алгебры отображений и параметров для систем, представленных функциональными или дифференциальными уравнениями. Достаточная проработанность этой теории позволила JI. Льюнгу оформить эффективную теорию, предназначенную для пользователя. Эта теория, однако, вообще не применима при решении проблем идентификации дискретных систем из-за отсутствия возможности использовать в дискретном случае такое фундаментальное понятие, как предельный переход. В то же время, для узких классов дискретных систем были с успехом использованы методы теории конечных полей. Яркими такими примерами являются исследования линейных систем А. Гиллом и А. Заде, теории кодирования Р. Блейхутом и многочисленные потенциальные приложения, указанные Р. Лиддлом и Г. Нидеррайтером.

Независимо от теории систем и немного ранее во времени применение, по сути дела, системного подхода с успехом было продемонстрировано в современной алгебре, что, в конечном счете, привело к разработке теории алгебраических систем А.И. Мальцевым и А. Тарским.

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

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

Основные направления выполненных исследований следующие:

- разработка общей теории поиска на частично упорядоченных структурах, специальными случаями которой являются классические теоретико-множественный подход и подход, основанный на оценивании;

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

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

- разработка более простых, чем известные аналитические, комбинаторных методов поиска всех и одной простых импликант, покрывающих заданную точку, а также ДНФ, состоящих из простых импликант;

- решение возникших из прикладных задач анализа контрол-лепригодности комбинационных схем проблем анализа управляемости/наблюдаемости для булевых функций;

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

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

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

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

На основе разработанной завершенной общей теории поиска исследованы два фундаментальных класса дисцсретных^систем: конечные автоматы и булевы^функции. )

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

Результаты, связанные с исследованием булевых функций, состоят в следующем. Впервые разработаны комбинаторные алгоритмы решения фундаментальных проблем поиска одной и всех простых импликант, покрывающих заданную точку. Предложенные алгоритмы являются детализацией вышеупомянутых разработанных в работе общих алгоритмов поиска и основаны на последовательном вычеркивании литералов. На основе последовательного применения этих алгоритмов решены фундаментальные проблемы поиска не очень сложной ДНФ, состоящей только из простых импликант, а также сокращенной ДНФ. Предложенные в работе формальные определения множеств управляемости и наблюдаемости для булевых функций дали возможность установить связь между проблемой анализа управляемости/наблюдаемости булевых функций и теорией минимизации ДНФ. На этой основе впервые построена математическая теория анализа управляемости/наблюдаемости булевых функций и их композиций. Алгоритмические и метрические аспекты этого анализа основаны на разработанных комбинаторных алгоритах поиска простых импликант и состоящих из них ДНФ. Прикладной аспект этих результатов состоит в том, что развитые средства являются основой для конструирования совместимой с системой моделирования электронных схем подсистемы, предназначенной для анализа параметров управляемости и наблюдаемости узлов комбинационных схем, а также для построения входных наборов, обеспечивающих требуемые значения в заданных узлах. Впервые решена проблема идентификации булевых вектор-функций методами теории линейных пространств над конечными полями. Прикладной аспект этих результатов состоит в том, что, г фактически, разработаны унифицированные средства как on-line, так и off-line контроля комбинационных схем. Показана возможность эффективного использования булевых матриц при идентификации неисправностей для схем с памятью методом выделения ядра.

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

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

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

Реализация результатов. Проведенные в работе исследования выполнены в рамках следующих госбюджетных НИР Института прикладной математики и механики НАН Украины:

Разработать методы построения тестов для систем базовых ТЭЗов и модификации структуры ТЭЗов с целью улучшения их диагности-руемости и выдать рекомендации организациям Минавиапома по их использованию" (1979-1981, ГР N 79033304);

Анализ непрерывных и дискретных систем с применением в задачах управления и оптимизации " (1982-1985, ГР N 01820073577);

Разработать математические методы оптимизации управления с приложением в технической диагностике, транспортных и технологических процессах" (1986-1989, ГР N 01.860.042947); Исследование математических вопросов теории цифровых устройств и создание программных систем их контроля и диагностирования" (19901993, ГР N 01.9.00.018.556); г

Исследование обратных задач теории автоматов, идентификации и распознавания дискретных систем" (1994-1998, ГР N 0399U003565);

Исследование актуальных проблем моделирования, управления и идентификации дискретных систем" (1999-2003, ГР N 0199U001612).

Кроме этого, разработка и внедрение результатов осуществлялись при выполнении следующих хоздоговорнывх работ:

Внедрение алгоритмов и системы математического обеспечения для моделирования и диагностики цифровых устройств" (1984-1987, ГР N 01840084752)

Разработка моделей, алгоритмов и математического обеспечения диагностирования цифровых устройств" (1987-1989, ГР N 01.870.055.678), заключенных между Саратовским производственным объединением им. С. Орджоникидзе и Специальным конструкторско-технологическим бюро систем управления ИПММ НАН Украины;

Исследование методов, алгоритмов и разработка программного обеспечения контроля и автоматизированного поиска неисправностей МСВТ" (1989-1990, N Госсрегистрации 5540107.00045), заключенных между Московским НИИ Научный центр и Специальным конструкторско-технологическим бюро систем управления ИПММ НАН Украины. (

Разработанные алгоритмы поиска, идентификации автоматов и булевых функций использовались автором при чтении курса "Дискретная математика и математическая логика" для студентов математического факультета Донецкого государственного университета в 1986-1991 гг., а методы исследования поведения систем в условиях нестабильной внешней среды - при чтении с 1989г. курса "Математические методы в маркетинге" для бакалавров и магистров Донецкой государственной академии управления и для системы последипломного образования ОАО "Концерн "Стирол"" (г. Горловка).

Соответствующие документы о внедрении прило^гсбны к диссертационной работе.

Апробация работы. Основные положения и результаты диссертационной работы были представлены на международной конференции по прикладной и промышленной математике ICIAM/GAMM'95 (г. Гамбург, Германия, 1995), на двух ежегодных конференциях Общества по прикладной математике и механике (Gesellschaft fur angewandte mathematik und mechanik - GAMM): GAMM'98 (г. Бремен, Германия, 1998) и GAMM'2001 (г. Цюрих, Швейцария, 2001), на международной конференции "Fault tolersant systems and diagnostics" (г. Брно, Чехословакия), на Всесоюзной конференции "Проблемы теоретической кибернетики" (г. Волгоград, 1990), на Всесоюзных совещаниях по технической диагностике (гг. Черкасы, 1979, и Ростов на Дону, 1980), на семинарах в Московском, Киевском, Саратовском и Донецком государственных университетах, в Институте кибернетики НАН Украины (г. Киев), Институте проблем моделирования в энергетики НАН Украины (г. Киев), Институте прикладной математики и механики НАН Украины (г. Донецк), в университете г. Сандерленд (Великобритания), в Институте математики университета г. Мишкольц (Венгрия).

Публикации. Основные результаты опубликованы в 39 печатных работах [8, 40, 50-70, 72-76, 78-83, 85-87, 131-133], из которых 4 выполнены в соавторстве. В работе [1] автору принадлежат алгоритмы двухстороннего поиска диагностических и установочных слов. В работе [40] автором разработан механизм адаптивного контроля систем, подверженных дестабилизирующим воздействиям внешней среды. В работе [74] автору принадлежат результаты, связанные с алгоритмическими и метрическими аспектами построения линейных характеристических функций. В работе [80, 81] автору принадлежат результаты, связанные с построением иерархии ДДФ-систем.

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

Основные результаты раздела опубликованы в [40,78,80,81.83].

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

6. Впервые исследовано представление функций переходов и выходов конечных автоматов конечными группами. Тем самым создан эффективный математический аппарат для исследования автоматных моделей методами теории групп.

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

8. Впервые разработаны более простые, чем известные аналитические, общие комбинаторные методы поиска всех и одной простых им-пликант, покрывающих заданную точку, а также ДНФ, состоящих из простых импликант.

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

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

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

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

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

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536с.

2. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.- 366с.

3. Беллман Р. Применение динамического программирования к задаче о коммивояжере. В кн.: Кибернетический сборник. Вып. 9 (Старая серия). - М.: Мир, 1964. - С.219-222.

4. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 457с.

5. Бенерджи Р. Теория решения задач. М.: Мир, 1972. - 224с.

6. Берж С. Теория графов и ее применение. М.: ИЛ, 1962. - 319с.

7. Богомолов A.M., Барашко А.С., Грунекий И.С. Эксперименты с автоматами. Киев, Наукова Думка, 1973. - 144с.

8. Богомолов A.M., Скобелев В.Г. Об одном алгоритме решения диагностической и установочной задач с автоматом // Кибернетика. 1975.- N 6. С.1-6.

9. Блейхут Р. Теория и практика кодов, контролирующих ошибки.- М.: Мир, 1986. 576с.

10. Васильев Ю.Л. О "суперпозиции" сокращенных дизъюнктивных нормальных форм. В кн.: Проблемы кибернетики. Вып. 12. - М.: Наука, 1964. - С.239-242.

11. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. - 272с.

12. Гилл А. Линейные последовательностные машины. М.: Наука, 1974. - 287с.

13. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476с.

14. Горяшко А.П. Проектирование легко тестируемых дискретных устройств: идеи, методы, реализация // Автоматика и телемеханика. -1984. N 7. - С.5-35.

15. Гэри М., Джонсон Д. Вычислительные машины и труднореша-емые задачи. М.: Мир, 1982. - 416с.

16. Де Брейн Н.Г. Асимптотические методы в анализе. М.: ИЛ, 1961. - 247с.

17. Де Брейн Н.Г. Теория перечисления Пойа. В кн.: Прикладная комбинаторная математика. - М.: Мир, 1968. - С.1-106.

18. Дискретная математика и математические вопросы кибернетики. Т.1 / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974.- 312с.

19. Журавлев Ю.И. Локальные алгоритмы вычисления информа-ции.1 И Кибернетика. 1965. - N 1. - С.12-19.

20. Журавлев Ю.И. Локальные алгоритмы вычисления информа-ции.Н // Кибернетика. 1966. - N 2. - С.1-11.

21. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. М.: Мир, 1971. - 400с.

22. Киркленд Т., Флорес В. Программные средства анализа тестируемости и автоматическая генерация тестов для СБИС // Электроника. 1983. - 56. - N 5. - С.41-48.

23. Клини Ф.К. Представление событий в нервных сетях и конечных автоматах. В кн.: Автоматы / Под ред. К.Э. Шеннона, Дж. Маккарти.- М.: ИЛ, 1956. С.15-67.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960с.

25. Коршунов А.Д. О перечислении конечных автоматов. В кн.: Проблемы кибернетики. Вып. 34. - М.: Наука, 1978. - С.5-82.

26. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. М.: Мир, 1988.- 428с.

27. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 2. М.: Мир, 1988.- 394с.

28. Льюнг Л. Идентификация систем. Теория для пользователя. -М.: Наука, 1991. 432с.

29. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. - 329с.

30. Матросов В.М., Анапольский Л.Ю., Васильев С.Н. Метод сравнения в математической теории систем. Новосибирск: Наука, 1980. -480с.

31. Месарович М., Такахара Я. Общая теория систем: математические основы. М.: Мир, 1978. - 311с.

32. Мур Э.Ф. Умозрительные эксперименты с последовательност-ными машинами. В кн.: Автоматы / Под ред. К.Э. Шеннона, Дж. Маккарти. - М.: ИЛ, 1956. - С.179-210.

33. Нигматтулин Р.Г. Проблема нижних оценок сложности и теория NP-полноты (обзор) // Известия ВУЗов. Математика. 1981. - N 5. -С.17-25.

34. Нильсон Н. Искусственный интеллект. М.: Мир, 1973. - 270с.

35. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985. - 376с.

36. Основы технической диагностики. Кн. 1 / Под ред. П.П. Пархоменко. М.: Энергия, 1976. - 464с.

37. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложгость. М.: Мир, 1985. - 510с.

38. Перфильева И.Г. Приложения теории нечетких множеств. В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 29. - М.: ВИНИТИ, 1990. - С.83-151.

39. Пилюшенко В.Л., Скобелев В.Г. Адаптивное управление ДДФ-системами // Докл. НАН Украины. 2000. - N 11. - С.135-138.

40. Прахар К. Распределение простых чисел. М.: Мир, 1967. - 511с.

41. Рабин М.О., Скотт Д. Конечные автоматы и задачи их разрешения. В кн.: Кибернетический сборник. Вып. 4 (Старая серия). - М.: Мир, 1962. - С.58-91.

42. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476с.

43. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. - 624с.

44. Рысцов И.К. Оценка длины кратчайшего диагностического слова для конечного автомата // Кибернетика. 1978. - N 6. - С.40-45.

45. Рысцов И.К. Асимптотическая оценка длины диагностического слова для конечного автомата // Докл. АН СССР. 1978. - 241. - N 2.- С.294-296.

46. Сапоженко А.А., Чухров И.П. Минимизация булевых функций в классе дизъюнктивных нормальных форм. В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 25. - М.: ВИНИТИ, 1987. - С.68-116.

47. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. - 348с.

48. Сачков В.Н. Комбинаторные методы дискретной математики. -М.: Наука, 1977. 320с.

49. Скобелев В.Г. Построение автоматов-экспериментаторов. В кн.: Методы диагноза и контроля сложных дискретных систем и автоматов. - Киев: ИК АН УССР, 1973. - С. 32-44.

50. Скобелев В.Г. Построение меры для оценки диагностических свойств класса автоматов. В кн.: Методы диагноза и контроля сложных систем и автоматов (Препринт 76-18). - Киев: ИК АН УССР, 1976.- С.31-37.

51. Скобелев В.Г. Неприводимые множества представителей семейства множеств. В кн.: Дискретные системы, формальные языки и сложность алгоритмов. - Киев: ИК АН УССР, 1977. - С.54-65.

52. Скобелев В.Г. Построение минимальных диагностических слов восстановлением их финальных отрезков. В кн.: Дискретные системы,формальные языки и сложность алгоритмов. Киев: ИК АН УССР, 1978. - С.75-83.

53. Скобелев В.Г. Некоторые оценки для автономных автоматов. -В кн.: Методы проектирования схемного и программного оборудования ЭВМ. Киев: ИК АН УССР, 1979. - С.42-55.

54. Скобелев В.Г. Локализация кратных неисправностей магнитной большой интегральной схемы (МБИС) "Ассоциативное ОЗУ". В кн.: Вопросы технической диагностики. Ростов-на-Дону: РИСИ, 1980. - С.38-42.

55. Скобелев В.Г. Метод поиска минимальных выигрышных решений в классе W-задач и его применение к построению минимальных диагностических слов. В кн.: Методы и системы технической диагностики. Вып. 1. - Саратов: СГУ, 1980. - С.27-39.

56. Скобелев В.Г. О некоторых задачах перечисления конечных автоматов // Докл. АН УССР. 1980. - N 12. - С.64-66.

57. Скобелев В.Г. О количестве графов переходов с заданным числом граничных вершин // Кибернетика. 1981. - N 2. - С.132-133.

58. Скобелев В.Г. О количестве графов переходов с заданным числом близнецов // Кибернетика. 1981. - N 2. - С.140-141.

59. Скобелев В.Г. Методы построения минимальных диагностических слов для автомата и сложность их реализации // Автоматика и телемеханика. 1981. - N 6. - С.162-169.

60. Скобелев В.Г. Алгоритмы и сложность распознавания внутренних состояний конечного автомата // Докл. АН УССР. 1981. - N 7. -С.71-74.

61. Скобелев В.Г. О перечислении возвратных автоматов // Кибернетика. 1984. - N 5. - С.120-122.

62. Скобелев В.Г. О сложности поиска диагностических и установочных слов для конечного автомата // Кибернетика. 1985. - N 4. -С.116-118.

63. Скобелев В.Г. Об оценках длин диагностических и возвратныхслов для автоматов // Кибернетика. 1987. - N 4. - С.114-116.

64. Скобелев В.Г. Управляемость и наблюдаемость для булевых функций и их композиций // Докл. АН УССР. 1987. - N 7. - С.65-67.

65. Скобелев В.Г. Об исследовании управляемости комбинационных схем // Автоматика и телемеханика. 1988. - N 1. - С.136-141.

66. Скобелев В.Г. Анализ управляемости и наблюдаемости комбинационных схем // Электронное моделирование. 1989. - 11. - N 1. -С.63-67.

67. Скобелев В.Г. Комбинаторные алгоритмы построения дизъюнктивной нормальной формы (ДНФ) // Докл. АН УССР. 1989. - N 2. -С.72-75.

68. Скобелев В.Г. Об одном методе минимизации булевых функций // Кибернетика. 1989. - N 5. - С.44-48.

69. Скобелев В.Г. О реализациях булевых функций на мультиплексорах. В кн.: Теория и моделирование управляющих систем. - Киев: Наукова думка, 1989. - С.52-56.

70. Скобелев В.Г., Кашеро М. В. Автоматизация конструирования заданий и текстов программ моделирования распределенных схем. В кн.: Моделирование и диагностика управляющих систем. - Киев: Наукова думка, 1991. - С.94-96.

71. Скобелев В.Г. Поиск на частично упорядоченных структурах // Украинский математический журнал. 1992. - 44. - N 2. - С.253-260.

72. Скобелев В.Г. Представление автоматов группами // Украинский математический журнал. 1992. - 44. - N 10. - С.1412-1416.

73. Скобелев В.Г., Сперанский Д.В. Идентификация булевых функций методами линейной алгебры // Украинский математический журнал. 1995. - 47. - N 2. - С.260-268.

74. Скобелев В.Г. Общерекурсивная модель секретного замка // Докл. НАН Украины. 1995. - N 6. - С.73-75.

75. Скобелев В.Г. Построение нижних экспоненциальных оценок // Докл. НАН Украины. 1997. - N 3. - С.115-117.

76. Скобелев В.Г. Принятие решений: комбинаторный подход. Донецк: ДонГУ, 1997. - 54с.

77. Скобелев В.Г. Анализ дискретных систем. Донецк, ИПММ НА-НУ, 2002. - 172с.

78. Скобелев В.Г. Некоторые метрические соотношения в симметрической группе подстановок. В кн.: Идентификация и моделирование управляющих систем. - Киев: Наукова думка, 1997. - С.5-9.

79. Скобелев В.Г., Христиановский В.В. Исследования систем в условиях дестабилизации. Донецк: ДонГУ, 1997. - 106с.

80. Скобелев В.Г., Христиановский В.В. Системы под действием дестабилизирующих факторов: аксиоматический подход // Докл. НАН Украины. 1998. - N 5. - С.99-104.

81. Скобелев В.Г. Поиск адаптивных решений на частично упорядоченных структурах // Искусственный интеллект. 1999. - N 1. - С.6-11.

82. Скобелев В.Г. Композиции ДДФ-систем // Докл. НАН Украины.- 2000. N 1. - С.82-85.

83. Скобелев В.Г. Механизм стимулирования в активной системе: общая модель. В кн.: Труды ИПММ НАН Украины. - 1999. - N 4. -С.166-170.

84. Скобелев В.Г. Представление автоматов группами.П // Украинский математический журнал. 2000. - 52. - N 10. - С.1397-1404.

85. Скобелев В.Г. Общие схемы поиска решений на частично упорядоченных структурах. В кн.: Труды ИПММ НАН Украины. - 2000.- N 5. С.132-140.

86. Скобелев В.Г. Общие схемы поиска безусловных решений // Докл. НАН Украины. 2000. - N 12. - С.82-86.

87. Современные методы идентификации систем / Под ред. П. Эйк-хофа М.: Мир, 1983. - 400с.

88. Соколовский М.Н. Сложность порождения подстановок и эксперименты с автоматами. В кн.: Методы дискретного анализа в теории кодов и схем. Вып. 29. - Новосибирск: НГУ, 1976. - С.68-86.

89. Соколовский М.Н. Оценка длины диагностического слова для конечного автомата // Кибернетика. 1976. - N 2. - С.16-21.

90. Трахтенброт Б. А., Барздинь Я.М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. - 400с.

91. Хант Е.Б. Искусственный интеллект. М.: Мир, 1978. - 558с.

92. Харари Ф. Теория графов. М.: Мир, 1973. - 300с.

93. Харари Ф., Палмер Е.М. Перечисление графов. М.: Мир, 1977. - 324с.

94. Хелд М., Карп P.M. Применения динамического программирования к задачам упорядочения. В кн.: Кибернетический сборник. Вып. 9 (Старая серия). - М.: Мир, 1964. - С.202-218.

95. Adamek J. Realization theory for automata in categoriez // J. Pure and Appl. Alg. 1977. - 9. - N 3. - P.281-296.

96. Adamer J., Koubek V. Functional algebras and automata // Kybernetika (Prague). 1977. - 13. - N 4. - P.245-260.

97. Arbib M.A., Manes E.G. Machines in a category // SIAM Rev. -1974. 16. - N 2. - P.163.

98. Bellman R. Combinatorial processes and dynamic programming in combinatorial analysis. In: Proceedings of Symposia in Applied Mathematics. Vol. X. American Mathematical Society. - Providence: RI, 1960. - P.293-326.

99. Bellmore M., Nemhauser G.L. The travelling salesman problem: a survey // Operat. Res. 1968. - N 16. - P.538-568.

100. Bollobas B. Modern graph theory. Springer-Verlag, 1998. - 394p.

101. Dantzig G.B., Fulkerson D.R., Jonson S. Solution of large-scale travelling salesmam problem // Operat. Res. 1954. - N 2. - P.393-410.

102. Dantzig G.B. Discrete-variable extremum problems // Operat. Res. 1957. - N 5. - P.266-277.

103. Dantzig G.B., Blattner W.O., Rao M.R. All shortest routes from a fixed origin in a graph. In: Theory of Graphs. International Symposia. Rome, July 1966. - Gordon and Breach: NY. - 1967. - P.85-90.

104. Dijkstra E.W. A note on two problems in connection with graphs // Numerical Mathematics. 1959. - N 1. - P.269-271.

105. Eilenberg S. Automata, languages and machines. Vol A. Academic Press: NY. - 1974. - 451p.

106. Eilenberg S. Automata, languages and machines. Vol B. Academic Press: NY. - 1976. - 387p.

107. Eilenberg S., Wright J.B. Automata in general algebras // Inf. and Control. 1967. N 11. - P.452-470.

108. Floyd R.W. Algorithm 97: shortest path // Communications ACM. 1962. - 5. - N 6. - P.345.

109. Fulkerson D.R. Expected critical path length in PERT networks // Operat. Res. 1962. - N 10. - P.808-817.

110. Hennie F.C. Finite-state models for logical machines. John Wiley&Sons INC.: NY, 1962. - 466p.

111. Hibbard T.N. Least upper bounds on minimal terminal state experiments for two classes of sequential machines // J. Assoc. Comput. Math. 1961. - N 8. - P.601-612.

112. Johnson. D.B. Algorithms for shorted paths. Ph. D. Thesis. -Dept. Comput. Sci. Cornell Univ., Itaka: NY, 1973.

113. Kim M., Kang S., Hong K. Developments in testing transition systems // Testing of Communication Systems. Vol. 10. - 1997. - P. 143166.

114. Kohavi Z. Switching and finite automata theory. McGrow-Hill Book Company: NY, 1970. - 592p.

115. Kruskal J.B.Jr. On the shortest spanning subtree of a graph and the travelling salesman problem // Proc. of AMS. 1956. - 7. - N 1. -P.48-50.

116. Land A.H., Doig A.G. An automatic method for solving discrete programming problems // Econometrica. 1960. - 28. - N 3 - P.497-520.

117. Lawler E.L., Wood D.E. Branch-and-bound methods: a survey // Operat. Res. 1966. - N 14. - P.699-719.

118. Lee D., Yannakakis M. Principles and methods of testing finite state machines. A survey // Proc. of IEEE. - 1996. - Vol. 84. ■ N 8. -P.1090-1123.

119. Lehmer D.H. The sieve problem for all-purpose computers // Math. Tables Aids Comput. 1953. - N 7. - P.6-14.

120. Lehmer D.H. Combinatorial problems with digital computers. In: Proc. Fourth Canadian Math. Congress, 1957. - Univ. of Toronto Press. -1960. - P.160-173.

121. Little J.D.C., Murty K.G., Sweeny D.W., Karel C. An algorithm for the travelling-salesman problem // Operat. Res. 1963. - N 11. - P.972-989.

122. McNauton R., Yamada H. Regular expressions and state graphs for automata // Trans. Electron. Comput. 1960. - 9. - N 1. - P.39-47.

123. Moore E.F. The shortest path through a maze. In: Proceedings of International Symposium on The Theory of Switching. Part II. Cambrige Mass. - Harvard Univ. Press. - 1959. - P.285-292.

124. Obruca A.K. Spanning tree manipulations and the travelling salesman problems // Computer J. 1968. - N 10. - P.374-377.

125. Paun G., Rosenberg G., Salomaa A. DNA computing. New computing paradigms. Springer-Verlag, 1998. - 402p.

126. Pierce A.R. Bibliography on algorithms for shorted path, shorted spanning trees and relative circuit routing problems (1956-1976) // Networks. 1975. - N 5. - P.129-149.

127. Pollak M., Wiebenson W. Solution of the shorted-route problem -A review // Operat. Res. 1960. - N 8. - P.224-230.

128. Shapiro J.F. Shortest route methods for finite state deterministic dynamic programming // SIAM J. Appl. Math. 1968. - N 16. - P.1232-1250.

129. Skobelev V.G. On finding of minimal distinguishing sequences for finite automaton. In: Diagnostika a zabezpeceni cislovych system. - Brno, ZARI, 1981. - P.145-151.

130. Skobelev V.G. Problem-solving: combinatorial-algebraic approach 11 ZAMM. 1996. - 76., S3. - P.583-584.

131. Skobelev V.G. Design of irreducible sets of representatives for a family of sets // ZAMM. 1999. - 79, S3. - P.915-916.

132. Skobelev V.G. Algebraic models for discrete systems' analysis. -Mathematical Notes, Miskolc. 2001. - 2. - N 1. - P.61-68.

133. Spira P.M. A new algorithm for finding all shorted paths in graph of positive arcs in averege time 0(n2logn) J J SIAM J. Comput. 1973. -2. - N 1. - P.28-32.

134. Spira P.M., Pan A. On finding and updating shortest paths and spanning trees. In: IEEE 14th Annual Symposium on Switching and Automata Theory. - 1973. - P.82-84.

135. Stairs. Bibliography of the shorted route probblem. Report LSE-TNT-6: Transport Network Thery Unit. - London School of Economics, 1966. - P.32-47.

136. Starke P. Uber experimente an automaten // Zetschr. f. Math. Logic und Grundl. d. Math. 1967. - 13. - P.67-80.

137. Ukraine, 340055, Donetsk-55, Universitetskaya str., 24 Tel.:+38 (0622) 933028 Fax: +38 (0622) 927112 E-mail: postmaster@univ.donetsk.ua

138. Jlf. Ol.cLCQJL № ///?/Q/'JU £/а/. О Ha№Г