Содержание к диссертации
Введение
1. Модели и методы теории систем 16
1.1. Основы математической теории систем 16
1.2. Проблемы идентификации систем 27
1.3. Конечные автоматы 32
1.4. Булевы функции 38
1.5. Поиск 44
1.6. Выводы 60
2. Поиск на частично упорядоченных структурах 63
2.1. Общие схемы поиска безусловных решений 63
2.2. А4-источник 77
2.3. Поиск безусловных решений для М.-источников 80
2.4. АМ-источник 96
2.5. Поиск адаптивных решений для ЛЛ4-источников 103
2.6. Неприводимые множества представителей семейства множеств 108
2.7. Выводы 118
3. Анализ конечных автоматов 120
3.1. Поиск идентифицирующих слов 120
3.2. Построение нижних экспоненциальных оценок 138
3.3. Сложность поиска минимальных идентифицирующих слов 145
3.4. Оценка диагностических свойств класса автоматов 151
3.5- Построение автоматов-экспериментаторов 157
3.6. Представление автоматов группами 162
3.7. Рекурсивная модель секретного замка 177
3.8. Выводы 179
4. Анализ булевых функций .182
4.1. Комбинаторные алгоритмы построения ДНФ 182
4.2. Управляемость.наблюдаемость булевых функций 193
4.3. Идентификация булевых вектор-функций 199
4.4. Идентификация неисправностей выделением ядра .212
4.5. Выводы 217
5. ДДФ-системы 219
5.1. Основные понятия и определения 219
5.2. Композиции ДДФ-систем 224
5.3. Адаптивное управление ДДФ-системами 226
5.4. Выводы 231
Заключение 233
Список литературы 237
Приложение 248
- Основы математической теории систем
- Общие схемы поиска безусловных решений
- Поиск идентифицирующих слов
- Комбинаторные алгоритмы построения ДНФ
Введение к работе
Актуальность. В настоящее время бурно развивается теория дис- ' кретных систем. Это развитие происходит путем возникновения ряда слабо взаимосвязанных недостаточно теоретически проработанных разделов, часто возникающих из прикладных проблем. Как следствие, многообразие различных моделей, как правило, нечисловой природы (т.е. таблицы, размеченные графы, теоретико-множественные и лингвистические конструкции и т.д.), основным методом исследования которых является более или менее разумно организованный перебор вариантов, т.е. поиск. Отмеченные особенности в полной мере проявили себя в возникших в последнее время системах дискретных событий (discrete event systems) и отмеченных системах переходов (labelled transition systems). Этим разделам ежегодно посвящается значительное число конференций, симпозиумов и публикаций, основной итог которых - результаты дескриптивного плана.
Именно недостаточная теоретическая проработка и, как следствие, отсутствие единой методологии исследования приводят к тому, что основным методом исследования дискретных систем становится поиск, чье становление, как аксиоматической теории, тесно связано с именами Р.Бенерджи и Н. Нильсона. В результате, алгоритмический и метрический аспекты многих как фундаментальных, так и прикладных проблем исследования дискретных систем часто остаются в тени. В конечном итоге отсутствует теория эффективного анализа дискретных систем и, как таковая, теория идентификации дискретных систем.
Ретроспективный анализ дает возможность выявить следующие существенные моменты.
Теория систем существует уже более полувека. Ее становление, как самостоятельной науки, тесно связано с именами М. Арбиба, Л. Берта-ланфи, Р. Калмана, В.М. Матросова, М. Месаровича, П. Фалба. Однако, до сих пор отсутствует общепринятый аксиоматический подход к теории систем, позволяющий с единых позиций эффективно исследовать весь комплекс возникающих проблем. Более того, зачастую происходило независимое развитие теорий непрерывных и дискретных систем, вспоминающих друг о друге только при исследовании гибридных моделей.
Проблеме идентификации уделялось большое внимание с самого начала становления теории систем, как математической науки. Первый крупный успех связан с разработкой Р. Калманом алгебраической теории идентификации для достаточно узкого, но, в то же время, достаточно важного класса линейных систем. Безусловным достоинством этой теории является то, что она дает унифицированный метод исследования как непрерывных, так и дискретных линейных систем. Совершенно иная картина имеет место при выходе за класс линейных систем. Трудами многочисленных исследователей была создана теория идентификации непрерывных систем. Предмет ее исследования - идентификация методами математического анализа и алгебры отображений и параметров для систем, представленных функциональными или дифференциальными уравнениями. Достаточная проработанность этой теории позволила Л. Льюнгу оформить эффективную теорию, предназначенную для пользователя. Эта теория, однако, вообще не применима при решении проблем идентификации дискретных систем из-за отсутствия возможности использовать в дискретном случае такое фундаментальное понятие, как предельный переход. В то же время, для узких классов дискретных систем были с успехом использованы методы теории конечных полей. Яркими такими примерами являются исследования линейных систем А. Биллом и А. Заде, теории кодирования Р. Блейхутом и многочисленные потенциальные приложения, указанные Р. Лиддлом и Г. Нидеррайтером.
Независимо от теории систем и немного ранее во времени применение, по сути дела, системного подхода с успехом было продемонстрировано в современной алгебре, что, в конечном счете, привело к разработке теории алгебраических систем А.И. Мальцевым и А. Тарским.
Был сделан ряд попыток объединения комбинаторного подхода с алгеброй. Однако, до сих пор создание общей теории идентификации дискретных систем находится в зачаточном состоянии. Поэтому, создание общих математических методов исследования дискретных систем, основанных на взаимопроникновении теории поиска решений и теории алгебраических систем выглядит весьма актуальным, плодотворным и перспективным.
Целью диссертационной работы является разработка основ комбинаторно-алгебраической теории, предназначенной для решения проблем идентификации дискретных систем. Это исследование проводится в диссертационной работе в двух аспектах. Первый аспект - это разработка общей теории, охватывающей как можно больше частных задач и систем. Второй аспект - это глубокая проработка важных модельных задач, продвижение в которых не раз являлось мощным стимулом для развития общей теории.
Основные направления выполненных исследований следующие: - разработка общей теории поиска на частично упорядоченных структурах, специальными случаями которой являются классические теоретико-множественный подход и подход, основанный на оценивании; исследование проблемы идентификации внутренних состояний слабоинициальных конечных автоматов на основе разработанных методов поиска, с целью создания унифицированных методов построения минимальных и неприводимых диагностических, установочных и синхронизирующих слов для простых экспериментов, унифицированных методов построения кратных и условных экспериментов; исследование представлений функций переходов и выходов конечных автоматов конечными группами, с целью создания эффективного математического аппарата для исследования автоматных моделей методами теории групп; разработка более простых, чем известные аналитические, комбина- торных методов поиска всех и одной простых импликант, покрывающих заданную точку, а также ДНФ, состоящих из простых импликант; решение возникших из прикладных задач анализа контрол-лепригодности комбинационных схем проблем анализа управляемости/наблюдаемости для булевых функций; разработка более простого, чем исчерпывающий поиск, метода идентификации булевых вектор-функций на основе теории линейных пространств над конечными полями, с целью создания эффективного математического аппарата для решения прикладных проблем контроля правильности функционирования комбинационных схем; - построение фрагмента математической теории систем, предназна ченного для исследования систем, находящихся под действием дестаби лизирующих факторов внешней среды с целью создания унифицирован ных эффективных методов контроля и управления реальными система ми.
Методы исследования. Теоретическую основу выполненных исследований составляют математическая теория систем, теория поиска, современная алгебра, теория множеств, теория автоматов, теория булевых функций, а также методы дискретной математики, используемые в технической диагностики дискретных устройств.
Научная новизна и основные положения, выносимые на защиту. С целью создания общей теории поиска впервые разработана метатеория поиска безусловных решений, определяемых характеристической функцией. Созданы три общие схемы поиска безусловных решений на основе выделения в дереве поиска множеств бесперспективных, финальных и порождающих вершин. Определены и исследованы оригинальные базовые математические модели для поиска безусловных и адаптивных решений, соответственно, Л^-источник и АУИ-источник. Впервые исследованы общие соотношения между моделями, предназначенными для поиска адаптивных и безусловных решений. Получено полное решение проблем поиска основных типов решений (т.е. всех ми- нимальных, всех неприводимых, одного минимального, одного кооперативного и одного адаптивного решений). Разработана общая схема двустороннего поиска минимальных решений для Л4 -источников за счет параллельных действий с прямым и обратным Л4-источниками. Получено полное решение модельной прикладной проблемы - поиска диагностических тестов для одноуровневых комбинационных схем. Впервые получено полное решение фундаментальной проблемы дискретной математики - поиска всех неприводимых множеств представителей заданного семейства множеств.
На основе разработанной завершенной общей теории поиска исследованы два фундаментальных класса дщжретных сис/гем: конечные автоматы и булевы функции. .яйм,*-о. C^U^fa- і
Результаты, связанные с исследованием конечных автоматов, состоят в следующем. Построены и исследованы прямые и обратные Л4-источники, предназначенные для решения проблем идентификации внутренних состояний слабоинициального конечного автомата. Таким образом, непосредственное применение разработанных общих алгоритмов поиска дает возможность решить целый спектр проблем теории экспериментов с автоматами, а именно: поиск (всех или одного, безразлично, какого именно) минимальных идентифицирующих (т.е. диагностических, установочных или синхронизирующих) слов восстановлением либо их начальных, либо их финальных отрезков, а также двухсторонним восстановлением; поиск всех неприводимых идентифицирующих слов восстановлением либо их начальных, либо их финальных отрезков; поиск кратных идентифицирующих экспериментов. Разработан общий метод построения нижних экспоненциальных оценок на основе использования подстановок, имеющих специальную структуру. Эффективность и мощь этого метода проиллюстрирована исследованием метрических характеристик симметрической группы - классического объекта алгебры, а также построением нижних экспоненциальных оценок длин минимальных диагностических и синхронизирующих слов для слабоинициального автомата с двухбуквенным входным алфавитом. Фундаментальное значение последнего результата состоит в том, что любой алгоритм построения диагностических или синхронизирующих слов для слабоинициального автомата, основанный на восстановлении отрезков фиксированной длины, заведомо имеет экспоненциальную сложность (как временную, так и емкостную). Разработана мера оценки диагностических свойств класса параллельно функционирующих слабоинициальных автоматов. Таким образом, созданы основы для унифицированной организации направленного поиска при построении всех основных типов как простых, так и кратных безусловных экспериментов по идентификации как внутренних состояний слабоинициального автомата, так и слабоинициального автомата, принадлежащего данному классу. Прикладной аспект этих результатов состоит в том, что, фактически, построена концептуальная модель для унифицированной разработки методов последовательного построения тестов для дискретных устройств с памятью. Введенное и исследованное в работе понятие ЛЛІ -источника дало возможность произвести его детализацию для решения проблем идентификации внутренних состояний слабоинициального конечного автомата и контроля правильности функционирования автомата при наличии сбоев. Таким образом, непосредственное применение разработанных общих алгоритмов поиска дает возможность строить условные эксперименты с автоматами, впервые реализуя их в виде автоматов-экспериментаторов. Прикладной аспект этих результатов состоит в том, что, фактически, построена концептуальная модель для унифицированной разработки средств адаптивного контроля систем дискретных событий, представленных конечными автоматами. Впервые получено полное решение проблемы представления функций переходов и выходов конечных автоматов конечными группами. Выделение множества представлений, согласованных с функцией переходов, привело к классу перестановочных автоматов, каждая компонента связанности которых имеет одно и тоже число состояний. Показано, что этот класс содержит важный специальный подкласс, состоящий из автоматов, представимых композициями циклических групп (или, что то же самое, декартовым произведением счетчиков с отождествлением их входа). Прикладной аспект последнего подкласса проиллюстрирован его применением для конструирования нестационарных секретных замков со сколь угодно высокой сложностью расшифровки.
Результаты, связанные с исследованием булевых функций, состоят в следующем. Впервые разработаны комбинаторные алгоритмы решения фундаментальных проблем поиска одной и всех простых импликант, покрывающих заданную точку. Предложенные алгоритмы являются детализацией вышеупомянутых разработанных в работе общих алгоритмов поиска и основаны на последовательном вычеркивании литералов. На основе последовательного применения этих алгоритмов решены фундаментальные проблемы поиска не очень сложной ДНФ, состоящей только из простых импликант, а также сокращенной ДНФ. Предложенные в работе формальные определения множеств управляемости и наблюдаемости для булевых функций дали возможность установить связь между проблемой анализа управляемости/наблюдаемости булевых функций и теорией минимизации ДНФ. На этой основе впервые построена математическая теория анализа управляемости/наблюдаемости булевых функций и их композиций. Алгоритмические и метрические аспекты этого анализа основаны на разработанных комбинаторных алгоритах поиска простых импликант и состоящих из них ДНФ. Прикладной аспект этих результатов состоит в том, что развитые средства являются основой для конструирования совместимой с системой моделирования электронных схем подсистемы, предназначенной для анализа параметров управляемости и наблюдаемости узлов комбинационных схем, а также для построения входных наборов, обеспечивающих требуемые значения в заданных узлах. Впервые решена проблема идентификации булевых вектор-функций методами теории линейных пространств над конечными полями. Прикладной аспект этих результатов состоит в том, что, фактически, разработаны унифицированные средства как on-line, так и off-line контроля комбинационных схем. Показана возможность эффективного использования булевых матриц при идентификации неисправностей для схем с памятью методом выделения ядра.
Впервые разработан новый фрагмент математической теории сис тем - теория ДДФ-систем, предназначенный для анализа систем, под верженных дестабилизирующим воздействиям внешней среды. На ос нове аксиоматического подхода (М. Месарович, Я. Такахара) впервые проработаны основы (т.е. модели и методы) как абстрактной, так и структурной теории ДДФ-систем. Построенные модели, по своей сути, являются семействами обычных систем, что дает возможность исполь зовать для их анализа весь арсенал методов и средств современной ма тематической теории систем. Решена проблема адаптивного управле ния ДЦФ-системой методами теории информации. Предложеннный ме ханизм контроля является основой для унифицированного построения адаптивных систем управления как траекторией, так и финальным со стоянием ДДФ-систем. Заложенная в нем возможность адаптации раз мерности к сложившейся ситуации является унифицированным средст вом построения моделей, отражающих внутреннюю сложность иссле дуемой проблемы. \
Таким образом, в работе построены основы комбинаторно-алгебраической теории, предназначенной для решения проблем идентификации дискретных систем. Эффективность этих основ продемонстрирована на стандартных моделях таких систем.
Практическая ценность результатов, полученных в диссертационной работе состоит в следующем. Разработанные общие схемы поиска решений дают возможность унифицировать построение программных реализаций конкретных алгоритмов поиска, что существенно для их эффективного использования в современных системах поддержки принятия решений. Разработанные модели и методы для решения проблем идентификации конечных автоматов дают возможность унифициро- вать построение средств как безусловного, так и адаптивного контроля систем дискретных событий, представленных конечными автоматами. Представления конечных автоматов, согласованные с функцией переходов, являются эффективным средством для реализации автоматных моделей при решении проблем защиты информации. Разработанные модели и методы анализа управляемости/наблюдаемости булевых функций и их композиций являются основой для конструирования совместимой с системой моделирования электронных схем подсистемы, предназначенной для анализа параметров управляемости и наблюдаемости узлов комбинационных схем, для построения входных наборов, обеспечивающих требуемые значения в заданных узлах, а также для построения тестов, локализирующих неисправности. Разработанные модели и методы идентификации булевых вектор-функций методами теории линейных пространств над конечными полями являются основой для конструирования унифицированных средств как on-line, так и off-line контроля комбинационных схем. Разработанные модели и методы анализа ДДФ-систем дают возможность унифицировать исследование и управление системами, поверженными дестабилизирующим воздействиям внешней среды, что существенно для их эффективного использования в современных системах поддержки принятия решений.
Реализация результатов. Проведенные в работе исследования выполнены в рамках следующих госбюджетных НИР Института прикладной математики и механики НАН Украины: "Разработать методы построения тестов для систем базовых ТЭЗов и модификации структуры ТЭЗов с целью улучшения их диагности-руемости и выдать рекомендации организациям Минавиапома по их использованию" (1979-1981, ГР N 79033304); "Анализ непрерывных и дискретных систем с применением в задачах управления и оптимизации " (1982-1985, ГР N 01820073577); "Разработать математические методы оптимизации управления с приложением в технической диагностике, транспортных и технологи- ческих процессах" (1986-1989, ГР N 01.860.042947); " Исследование математических вопросов теории цифровых устройств и создание программных систем их контроля и диагностирования" (1990-
1993, ГР 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 наименований и приложения.
Содержание работы - следующее.
В разделе 1 изложен необходимый математический аппарат, проведен ретроспективный анализ предмета исследования, сформулированы основные проблемы.
В разделе 2 впервые систематически изложена разработанная автором общая теория поиска на частично упорядоченных структурах.
Основы математической теории систем
В результате интенсивного развития теории систем появилось значительное число публикаций, излагающих на аксиоматической основе различные подходы и аспекты с использованием логико-лингвистических, теоретико-множест.зенных, алгебраических и тополей гических методов (см. напр. [21,29-31,96-98]), Это направление - математическая теория систем - характеризуется тем, что для него до сих пор не выработана единая общепризнанная аксиоматика. Для дальнейшего изложения удобным и адекватным является теоретико-множественный подход, систематически изложенный в [31]. Рассмотрим его кратко, В основе этого подхода лежит выделение ряда уровней абстракции при определении понятия система. На высшем уровне абстракции система определяется как отношение 5СПК, (1.1) где V — {Vi\i Є 1} - семейство объектов. Отметим, что запись (1.1) автоматически предполагает, что множество индексов / - линейно упорядоченное. При фиксированном V все многообразие систем определяется комплексами условий, накладываемых на отношение «S, а так же с помощью математических структур, определенных на множестве J \\. Так как П Ц = {/ : / - U Vi I /(0 Щі ЄІ)}=? (1-2) и переименованием элементов множества / всегда можно добиться выполнения равенства / П ( U V ) = 0, то любой элемент множества П И іІ ІЄІ можно рассматривать как частичную унарную операцию, определенную на множестве /U (U V ). Следовательно, система (1.1) является алгеброй A=(IU(\JVi),Ts), (1.3) где = {/Є {/йкє5}. (1.4) Представление (1.3) дает возможность непосредственно перенести в теорию систем все основные понятия теории алгебраических систем [29], в том числе такие, как подсистема, гомоморфизм и изоморфизм. Действительно, пусть система Т Q Q( П Uj) представлена алгеброй B={J и(иШвт), где Qr = {9 Є Q {/(І) W Є Г}. Определение 1.1. Система Т называется подсистемой системы S, если выполнены следующие три условия: 1) J С /; 2) Uj С V} для всех j Є J] 3) для каждого g Є Qj существует такое f Є Ts, что (І) — f(j) для всех j Є J. Определение 1.2. Система Т называется гомоморфным образом системы 5, если существуют такие сюръективные отображения а : / -» J, A : VS -+ (7о(0 (г є /), 7 = - т, (1-5) что равенство й(/Ю) = (7(/)) (а(0) (1.6) справедливо для всех г Є / и / Є Определение 1.3. Системы S и Т называются изомоморфными, если отображения (1.5), удовлетворяющие условию (1-6) являются биективными. Значение определения 1.3 состоите следующем. Представление системы в виде (1.1) предполагает упорядочение множества объектов. Этот порядок фиксируется с помощью (линейно упорядоченного) множества индексов I. Упорядочение множества объектов влияет на внешнюю фор-му системы, но не затрагивает комплекс абстрактных характеристик отношения $. При определении математических структур на системе (1.1), для упрощения изложения, удобно изменять предписанный порядок объектов соответствующим образом, т.е. переходить к изоморфной системе. Такой переход, если он не вызывает недоразумений, как правило, не оговаривается в явном виде. Определение тех или иных отношений на множествах индексов и объектов системы (1.1) дает возможность выделить различные типы систем. Каждая из них представляется уже не алгеброй вида (1-3), а алгебраической системой общего вида [29], т.е. упорядоченной тройкой (AtQFtQP)t (1.7) t где Л - основное множество, QF И Up - множества основных, соответственно, операций и предикатов (т.е. характеристических функций отношений, определенных на множествах индексов и объектов системы). Определения гомоморфизма и изоморфизма алгебраических систем типа (1.7) требуют сохранения свойств как основных операций, так и основных предикатов. Именно по этой причине определения гомоморфизма и изоморфизма - различные для различных типов систем.
Рассмотрим детализации, применяемые для понижения уровня абстракции при определении понятия скстема. Пусть зафиксирована упорядоченная пара тг = {hniIout)t где Iin Л lout = 0, lin U lout = I. (1.8) Формула (1.1) может быть преобразована к виду абсолютного черного ящика (т.е. системы вход-выходного типа) SCXxY, (1.9) где X = Yl V5 и У = _ П У{ называются, соответственно, входным и вы-ходным объектом системы S. Ясно, что существует взаимно-однозначное соответствие между множеством всевозможных представлений системы (1.1) в виде абсолютного черного ящика и множеством всех упорядоченных пар 7г = (1{п, lout), удовлетворяющих условиям (1.8). Среди этих представлений особую роль играют следующие два, соответствующие случаям, когда одно из множеств 1{п или / - пустое. Представления, определяемые парами тгі = (0,/) и тгз = (/,0) называются системами, соответственно, без входа и без выхода. К этим типам относятся, в частности, соответственно, автономные системы и акцепторы.
Несмотря на высокий уровень абстракции, представления (1.1) и (1.9) могут быть успешно использованы при решении конкретных прикладных проблем. Проиллюстрируем сказанное следующими тремя примерами. Пример 1.1. Текущее состояние любой организации естественно представляется набором показателей V = (t?i,..., vn). Это означает, что концептуальная математическая модель организации - система S С 72, определяемая как n-арное отношение (т.е. представление (1.1)). На множестве S обычным образом можно определить отношение предпочтения s, а, следовательно, и определяемую им функцию полезности и : S — 71. Последняя дает возможность строить кривые безразличия rv = {w S I -u(w) = w(v)} (v Є S), а также представить систему S в виде 5 = (5Крит,5„ср,5(Глае), где SKpum, Snep и 8бАйг - подмножества, соответственно, критических, переходных и благоприятных состояний исследуемой организации.
Общие схемы поиска безусловных решений
Основные проблемы поиска решений - проблемы 1.4-1.8 - сформулированы в п. 1.5 в терминах базовой модели - источника. Четыре из них, а именно, проблемы 1.4-1.7 - это поиск безусловных решений. Поэтому актуальной является разработка метатеории поиска безусловных решений, т.е. средств, позволяющих единым образом представить все многообразие проблем и методов поиска безусловных решений и выделить факторы, определяющие внутреннюю сложность решения конкретных проблем. Основная цель настоящего пункта - исследование общей проблемы поиска безусловных решений для источника.
В соответствии с подходом, развитым в п.1.5, множество безусловных решений для источника - это множество выигрышных операторов (т.е. переводящих начальную ситуацию в множество финальных ситуаций), удовлетворяющих заданному комплексу условий. Унифицированное средство представления множества - его характеристическая функция. Следовательно, для заданного источника S = (S, F,SiniSfin) определение множества безусловных решений эквивалентно построению характеристической функции хп некоторого подмножества ГЇ множества T t удовлетворяющего условию П С (S). Итак, характеристическая функция хи множества безусловных решений Q для источника S всегда представляет собой такое отображение хи J {0,1}, что (VF Є F ){xo(F) = 1 = F Є П), где равенство xu{F) = 1 с необходимостью включает в себя выполнение условия F Є С($). Отметим, что условия F Є JC(»S) И SinF Є S/in эквивалентны. Пример 2.1 Если хтгп и Хгг - характеристические функции множеств Cmin(S) и Ctr(S) всех, соответственно, минимальных и неприводимых решений для источника S, то (см. п. 1.5) Xn(F) = 1 (F Є {$))& &(VFi Є .Г)И і) d(F) V d(Fi) d{F) = Xmin{Fi) = 0) и xir(F) = 1 ( е C{S)) FX є erase{F)){Xir{Fi) = 0). Зафиксируем источник о — (о, , Sjnj Sfijij и множество безусловных решений О (О С C(S)). Обозначим через х характеристическую функцию, определяющую множество О,. Положим CX(S) = Гї. Общая проблема поиска безусловных решений имеет следующий вид Проблема 2.1. Для заданных источника S и характеристической функции х построить множество безусловных решений CX{S). Рассмотрим решение проблемы 2.1. Пусть Т (х,$) - минимальное поддерево дерева T s, содержащее корень v\ и множество вершин V/in = {vp I F Є X(S). Отметим, что: 1) дерево T {Xi$) состоит из единственной вершины - корня г А тогда и только тогда, когда X{S) = 0; 2) дерево V(x,S) содержит конечное число вершин тогда и только тогда, когда х{$) - конечное множество. Будем интерпретировать вершины дерева T s как состояния, корень г л - как начальное состояние, а множество вершин Vjin - как множество финальных состояний. Тогда множество CX(S) - это язык, представленный настроенным автоматом {1)(х, 5), v\, Vfin). Все многообразие методов решения проблемы 1.9 сводится, по своей сути, к различным способам построения некоторой последовательности деревьев 2 (0),1 (1),2 (2),..., (2.1) удовлетворяющей следующим шести условиям. Условие 2.1. V{i) (г = 0,1,...) - поддерево дерева T st содержащее корень г л Условие 2.2. V(x,S) С ЩО) U V(l) \J...CVS. Условие 2.3. V(i) (г = 1,2,...) полностью определяется последовательностью деревьев Х (0),... ,D(i — 1). Условие 2.4. V(i) (г = 0,1,...) содержит как можно меньше вершин. Условие 2.5. Если V(x,S) - конечное дерево, то (2.1) - конечная последовательность. Условие 2.6. Если (2.1) - бесконечная последовательность, то X(S) \V((\J Щ))Щ)\ бесконечное множество и lim \vmtps)[h))\ Где 2?И ( = 0,1,...) -максимальное поддерево высоты h дерева Т , a V{T ) - множество вершин дерева Т . Отметим, что условие 2.2 обеспечивает корректность, а условия 2.4-2.6 - максимальное снижение сложности поиска.
Если T (x,S) - бесконечное дерево, то возникает проблема остановки. Последняя алгоритмически разрешима, если Сх{$) - регулярное множество. В этом случае существует конечное поддерево Т дерева (х, 5), которое может быть свернуто в (возможно, частичный) конечный настроенный автомат, представляющий множество CX(S). Высота Lvx дерева Vgi как правило, зараннєє не известна, т.е. она определяется в процессе построения дерева 2? в явном виде. Отметим, что mm(tS) и Cir(S) - регулярные множества, т.к. они - конечные. В силу последнего обстоятельства для проблем 1.4 и 1.6 имеет место равенство Т = T (Xi ?) Всюду в дальнейшем будем считать, что х( 5) - регулярное множество. Это предположение дает возможность, не ограничивая общности изложения, перейти от дерева Т (х, S) к дереву V$ и считать, что CX{S) - это конечное множество, представляемое конечным настроенным автоматом {T $,v\,Vfin). Таким образом, всюду в дальнейшем предполагается, что (2.1) - это конечная последовательность деревьев ї (0),2 (1),...,2 ( ), (2.2) удовлетворяющая условиям 2.1-2.4.
Поиск идентифицирующих слов
Раздел посвящен разработке комбинаторно-алгебраических основ анализа конечных автоматов - фундаментального класса дискретных систем как в теоретическом, так и прикладном плане. Равное внимание уделяется каждому из трех основных аспектов исследования, а именно: алгоритмическому, метрическому и дескриптивному.
В пп.3.1-3.3 решены проблемы 1.9 и 1.10. Решение проблемы 1.9 получено методами теории поиска на части чно-упорядоченных структурах, разработанной в разделе 2. В п.3.1 построены прямые и обратные Л4-источники для поиска идентифицирующих слов (т.е. диагностических, установочных и синхронизирующих) для заданного слабоинициального автомата. В п.3.2 разработан общий метод построения нижних экспоненциальных оценок. На его основе исследован метрический аспект симметрической группы - классической структуры алгебры, имеющей многочисленные применения. В п.3.3, на основе разработанного в п.3.2 метода, получены экспоненциальные нижние оценки длин минимальных диагностических и синхронизирующих слов для слабоинициального автомата с двухбу к венным входным алфавитом. В п. 3.4 построена мера для оценки диагностических свойств класса автоматов. В п.3.5 построены ДЛі-источники для решения проблем идентификации начального и финального состояний слабоинициального автомата и контроля правильности функционирания автомата при наличии сбоев. В п.3.6 исследуются представления функций переходов и выходов автомата конечными группами. В п.3.7, на основе результатов, полученных в пп.3.2, 3.3 и 3.6 решена проблема построения нестационарных секретных замков сколь угодно большой сложности расшифровки.
Основная цель данного пункта - решение проблемы 1.9, т.е. детализация разработанных в разделе 2 алгоритмов для организации безусловных экспериментов по идентификации начального или финального со 121 стояния заданного слабоинициального автомата (Л/, Qo), где М = {Q,X,Y,S,\) (\Q\ = к 2,Х = m 2, У = п 2) и Q0 С Q (jQol = г 2). Для достижения этой цели достаточно построить Л (-источник, множеством выигрышных операторов которого является либо множество всех диагностических слов D(M, Qo)) либо множество всех установочных слов Н(М, QQ), либо множество всех синхронизирующих слов S(MfQo). Так как в определении синхронизирующего слова не задействована функция выходов А, то при поиске множества S(M, QQ) считаем, что М - автомат без выхода,1 т.е. М = (Q, X, 5). Предложенная в разделе 2 классификация обосновывает целесообразность построения как прямых, так и обратных At-источников, что открывает возможности организации параллельных вычислений для соответствующих безусловных экспериментов.
Построение прямых Л -источников. В процессе поиска идентифицирующих слов восстановлением их начальных отрезков необходимо помнить, какие состояния необходимо в дальнейшем: 1) различить, если слово - диагностическое; 2) или различить, или склеить, если слово - установочное; 3) склеить, если слово - синхронизирующее. Следовательно, множество ситуаций источника, применяемого в процессе восстановления начальных отрезков идентифицирующих слов, естественно определяется следующим образом: 1. Если идентифицирующее слово - диагностическое или установочное, то множеством ситуаций является такое множество W(k,r) (W(fc,r) С B{B[Q)))y что W W{k,r) (W С B(Q)) тогда и только тогда, когда выполнены следующие три условия: Условие 3.1. \w\ 2 для всех w Є W. Условие 3.2. Если w\ W2 Є W (w\ ф іиг)» то w\ $ wi и wi w\. Условие 3.3. E \w\ r. 122 2. Если идентифицирующее слово - синхронизирующее, то множес-тво ситуаций - это множество B{k,r) = {W Є B{Q)\{$) \W\ г}. Для построенных множеств следующая интерпретация - истинная: 1, Ситуация W Є W(k,r) содержит информацию о том, что любые два состояния, принадлежащие одному и тому же множеству w Є W необходимо в дальнейшем различить, если идентифицирующее слово - диагностическое и раличить или склеить, если идентифицирующее слово - установочное. 2. Ситуация W Є В{к, г) содержит информацию о том, что все состо яния, принадлежащие множеству W необходимо в дальнейшем склеить, если идентифицирующее слово - синхронизирующее. Из этой интерпретации вытекает, что: 1. Начальной ситуацией является: 1) { Зо}, если идентифицирующее слово - диагностическое или уста v новочное; 2) QQ, если идентифицирующее слово - синхронизирующее. 2. Множеством финальных ситуаций является: 1) {0}, если идентифицирующее слово - диагностическое или уста новочное; 2) В(к, 1), если идентифицирующее слово - синхронизирующее.
Комбинаторные алгоритмы построения ДНФ
Многочисленные приложения задач минимизации булевых функций в классе ДНФ и возникающие при этом вычислительные трудности обосновывают актуальность разработки алгоритмов минимизации, ориентированных на использование ЭВМ. Основная цель настоящего пункта - разработка общих алгоритмов построения достаточно простой ДНФ, а также сокращенной ДНФ, основанных на последовательном построении простых импликант.
Как обычно, под длиной ДНФ D — V К% будем понимать количество h составляющих D элементарных конъюнкций. Обозначим через 1(D) длину ДНФ D. Рассмотрим следующие проблемы построения ДНФ. Проблема 4Л. Для заданной булевой функции / Є Лг(та) (п Є jV) 183 построить ДНФ D(f) длины l(D(f)} Л/}, состоящую из простых импликант. Проблема 4.2. Для заданной булевой функции / Рз( ) {п Є М) построить сокращенную ДНФ Dj0Kp. Проблема 4.3. Для заданной булевой функции / Рг( ) (п Є Л/") построить одну, безразлично, какую именно, простую импликанту К, покрывающую заданную точку s = ( 7i,..., ап) Є Л/}.
Проблема 4.4. Для заданной булевой функции / Є Рііп) (« М) построить множество всех простых импликант, покрывающих заданную точку s = (сі,..., тп) Є Л//.
Решение проблем 4.1, 4.3 и 4.4 может быть получено на основе решения проблемы 4.2. Действительно, построим ДНФ f)j.0Kp каким-либо из классических методов (см. п.1.4). Для решения проблемы 4.1 достаточно построить любую минимальную ДНФ, т.е. репіить проблему поиска какого-либо минимального (по числу элементов) покрытия множества Mf максимальными гранями п-мерного единичного куба, содержащимися в множестве Af/. Известные методы решения последней проблемы - преобразование специальным образом построенной КНФ в ДНФ за счет раскрытия скобок с применением операции элементарного поглощение. Для решения проблем 4.3 и 4.4 достаточно подставить значение s = ((Ті,... , тп) в ДНФ Dj0Kp и выбрать, соответственно, одну или все простые импликанты, значение которых равно 1. Такой метод решения проблем 4.1, 4.3 и 4.4 обладает следующим существенным недостатком: сложность каждого решения не меньше, чем сложность построения сокращенной ДНФ D%0Kp.
Этот недостаток действительно является существенным. Во-первых, как известно, длина сокращенной ДНФ может быть достаточно большой - экспонентой от числа переменных, значительно превышающей мощность множества Л// (см., напр., [18,47]). Во-вторых, все известные классические методы построения сокращенной ДНФ (см. п.1.4) основаны на аналитических преобразованиях, обладающих следующей особенностью. Объем памяти, необходимой на промежуточных шагах алгоритма, может существенно превышать объем памяти, необходимой для хранения сокращенной ДНФ и только на завершающих шагах работы алгоритма эти объемы выравниваются. В третьих, проблемы 4.3 и 4.4 представляют и самостоятельный интерес. К ним, например, сводятся проблемы поиска тестов для схем, реализованных на ПЛМ, а также (как будет показано в п.4.2), проблемы анализа управляемости/наблюдаемости комбинационных схем. Таким образом, разработка комбинаторных алгоритмов построения ДНФ, основанных на последовательном построении простых импликант - и актуальная, и естественная проблема.
Таким образом, алгоритм А вычисляет значение булевой функции f в точке s Є 6п, а алгоритм В порождаеи точку s Є J\f/\S. Обозначим через tcj и vcjj соответственно, временную и емкостную сложность алгоритма С Є {Л, В} для функции / Є Р2{гі), а через tc(n) - временную сложность алгоритма С Є {А, В} для почти всех функций / Є / ).
Доказательство. Корректность алгоритма 4.2 вытекает из следующих фактов. Конъюнкции, конструируемые в цикле, определяемом шагами 2 и 3 - импликанты булевой функции / Є (w)» покрывающие точку s — (о"і,... , тп) J\ff (см. доказательство теоремы 4.1). В процессе выполнения шага 6 осуществляется проверка, является ли каждая из этих импликант простой. Использование общего алгоритма поиска с возвращением (см. пл. 2.1 и 2.3) гарантирует построение всез элементов множества S/jS.
Оценим временную сложность алгоритма 4.2.
Обозначим через Л4, і (/, s) конструируемую в результате работы алгоритма 4.1 простую импликанту булевой функции / Є р2Ір)і покрывающую точку s Є Nf) а через A C/jS) - конструируемое в результате работы алгоритма 4.2 множество Sj)B всех простых импликант булевой функции / Р2(п) покрывающих точку s Є Aff.
Построение ДНФ булевой функции Sfp можно осуществить последовательным поиском с помощью алгоритма 4.1 простых импликант, покрывающих выбираемые точки до тех пор, пока не будет получено покрытие множества Л// содержащимися в нем гранями максимальных размерностей.
