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

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

д

¡И

Чернов Андрей Владимирович

Модели и методы логико-алгебраического анализа и синтеза в задачах технической диагностики информационных систем

Специальность 05.13.18 -Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ

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

00347Э68Э

Ростов-на-Дону - 2009

003479689

Работа выполнена на кафедре «Прикладная математика и вычислительная техника» в государственном образовательном учреждении высшего профессионального образования «Ростовский государственный строительный университет»

Научный консультант: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Белявский Григорий Исаакович

доктор технических наук, профессор Немолочнов Олег Фомич

доктор технических наук, профессор Чернухин Юрий Викторович

доктор технических наук, профессор Ковалев Сергей Михайлович

Учреждение Российской академии наук Вычислительный центр им. A.A. Дородницына РАН

Защита состоится 28 декабря 2009 г. в 1500 часов на заседании диссертационного совета Д 218.010.03 в Ростовском государственном университете путей сообщения по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

С диссертацией можно ознакомиться в научной библиотеке РГУПС по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

Автореферат разослан « б » CMldJ)fUt 2009 ]

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

диссертационного совета Д 218.010.03 доктор технических наук, профессор "1Г Бутакова М.А.

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

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

Предлагаемый в работе новый комплексный подход к решению задач моделирования и синтеза ИС является дальнейшим развитием математических методов исследования линейных и нелинейных дискретных систем, определяемых над конечными полями, которые используют усовершенствованные методы логического дифференциального, интегрального исчислений, спектральных и символьных преобразований логических функций. При этом использованы результаты основополагающих работ в области логико-алгебраического моделирования, математических моделей технической диагностики и синтеза надежных ИС, а именно труды: Биргера И.А., Дружинина Г.В., Журавлева Ю.И., Майерса Г., Не-молочнова О.Ф., Пархоменко П.П., Поспелова Д.А., СапожниковаВ.В., Сапож-никоваВл.В., Шубинского И.Б., Ушакова И.А.; в области дифференциального исчисления логических функций - работы Акерса С.Б., Астола Р., Бохманна Д., Гиббса Д.Е., Горбатова В.А., Давно М.Д., Закревского А.Д., Сэллерса Ф.Ф., Тей-за А., Янушкевич С.Н.; в области алгебраического подхода к общей теории моделирования систем - труды Арбиба М., Калмана P.E., Уонема М., Фалба П.Л.; в теории конечных полей - труды Лидла Р., Нидеррайдера Г.

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

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

Актуальность тематики подтверждается тем фактом, что работа подержана:

- грантом РФФИ 09-08-00097а «Дискретные динамические и стохастические модели анализа информационно-управляющих систем на транспорте и синтеза надежных цифровых структур» (2009 - 2011 гг.);

- грантом Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009 - 2013 гг. (мероприятие

1.1 «Проведение научных исследований коллективами научно-образовательны;

А

центров»-IV очередь), шифр 2009-1.1-113-050 «Проведение научных исследований коллективами научно-образовательных центров в области информатики», тема 2009-1.1-113-050-043 (2009-2011 гг.);

- грантом программы «Развитие научного потенциала высшей школы (2006 - 2008 гг.)» РНП.2.1.1.1038 тема РОСТ-НИЧ-692;

- грантом научно-исследовательской и опытно-конструкторской разработки Южного федерального университета per. № 3793 (2009 г.).

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

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

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

2. Разработка методологии синтеза самодиагностируемых ИС.

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

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

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

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

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

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

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

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

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

Предметом исследования являются модели и методы анализа, синтеза и алгоритмической реализации контролируемых ИС с возможностями самодиагностики.

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

временных методов технической диагностики программного и аппаратного обеспечения ИС.

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

Объект, предмет и методы исследования отвечают формуле специальности 05.13.18, так как содержанием работы является разработка фундаментальных основ и применение математического моделирования, численных методов и комплексов программ для решения научно-технической прикладной проблемы, исследование математических моделей технических объектов и соответствуют пунктам паспорта специальности: «1. Разработка новых математических методов моделирования объектов и явлений...»; «2. Разработка, исследование и обоснование математических объектов...»; «5. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; «6. Комплексное исследование научных и технических, фундаментальных и прикладных проблем с применением современной технологии математического моделирования и вычислительного эксперимента».

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

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

1. На основе сравнительного анализа существующих моделей и методов в технической диагностике ИС

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

2. На основе анализа моделей и алгоритмов, которыми располагает логическое дифференциальное исчисление

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

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

- получена общая модель дифференциальной дискретной системы;

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

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

3. На основе анализа описаний динамических систем над конечными полями, а именно, моделей: авторегрессионной, типа вход-выход, вход-состояние-выход;

- введено свойство «контролируемости» системы и решена задача синтеза контролируемой системы;

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

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

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

- получена предикатная логическая производная, как аналог логической производной, обобщенной для анализа спецификаций ПО;

- разработан метод анализа изменений в спецификации ПО с помощью предикатной производной;

- разработана обобщенная предикатная модель диагностики ПО ИС;

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

Основные результаты, выносимые на защиту.

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

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

3. Постановка и решение задачи разработки модели онлайновой диагностики аппаратного и ПО.

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

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

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

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

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

9. Метод синтеза контрольных уравнений с минимальным запаздыванием для линейной динамической системы.

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

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

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

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

Практическую ценность представляют следующие результаты.

1. Разработан комплекс программ, в котором реализованы:

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

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

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

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

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

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

- анализировать функционирование дискретных динамических систем на основе линейных контрольных соотношений;

- синтезировать контрольные соотношения для динамических систем с минимальным запаздыванием.

3. Разработано и внедрено ПО:

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

- реализующее алгоритмы и программы диагностики на основе предикатной производной;

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

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

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

Реализация результатов работы.

Результаты работы прошли успешную апробацию, внедрены и используются: в научно-производственном предприятии (НПП) «Югпромавтоматизация» при разработке диагностических подсистем для информационно-управляющих систем на транспорте; в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи в контрольно-диагностическом комплексе устройств сортировочных станций; в телекоммуникационной компании «Альянс-Телеком» в системе мониторинга и контроля предоставления информационных услуг связи по передаче данных и доступу к сети Интернет. Разработанный автором программный комплекс зарегистрирован в отраслевом фонде алгоритмов и программ. Научные результаты работы используются в учебном процессе Ростовского государственного строительного университета.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на всероссийских симпозиумах по прикладной и промышленной математике (2001-2009 гг., Сочи, Ростов-на-Дону, Йошкар-Ола, Петрозаводск, Кисловодск, Волжский, Санкт-Петербург); на научно-практической конференции Санкт-Петербургского государственного политехнического университета (2008 г.) «Управление созданием и развитием систем, сетей и устройств телекоммуникаций»; на международных научно-практических конференциях Южно-Российского государственного технического университета (НПИ), Новочеркасск: «Теория, методы и средства измерений, контроля и диагностики» (2007 г.), «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (2007 г.); на межведомственных и международных конференциях «Телекоммуникационные и информационные технологии на транспорте России» (2001, 2006, 2007, 2008 гг., Сочи); на международных конференциях «Математика. Экономика. Образование» (2002, 2006 гг., Новороссийск); на международной научно-практической конференции «Организационно-экономические проблемы проектирования и применения информационных систем» (1996 г., Ростов-на-Дону); на ведомственной конференции МПС «Проблемы обеспечения информационной безопасности на федеральном железнодорожном транспорте» (2001 г., Санкт-Петербург); на научной конференции «Безопасность информационных технологий» (2002 г., Таганрог); на международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (2009 г., Коломна); на конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (РГУПС) (1999 - 2001 гг.), и Ростовского государственного строительного университета (РГСУ) (2009 г.); на научных семинарах кафедр «Информатика» РГУПС, «Прикладная математика и вычислительная

техника» РГСУ, «Алгебра и дискретная математика» Южного федерального университета.

Публикации. Полученные в диссертации теоретические и практические результаты нашли свое отражение в 52 печатных работах, в том числе монографии, 23 статьях в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, приложений, списка литературных источников из 175 наименований. Общий объем диссертации составляет 281 стр., из которых объем основного текста составляет 256 стр.

В главе 1 «Математические модели и методы дискретного анализа в технической диагностике и их новые направления» проведен общий анализ современного состояния исследований в области моделей технической диагностики дискретных устройств и строящихся на их базе ИС. Рассмотрен круг задач, связанных с развитием новых направлений в моделировании задач технической диагностики ИС с учетом обновления их элементной базы, требований безопасности и качественного обслуживания, широким внедрением телекоммуникационных технологий. В главе выполняется систематизация методов и моделей представления булевых функций и их производных, что позволило объединить и развить существующие подходы в виде дискретного логико-алгебраического анализа над конечными полями Галуа.

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

Базовым понятием, необходимым для развития идей анализа динамических характеристик дискретных систем, является булева разность, также называемая булевой производной. Простейшее объяснение данного понятия, пригодного для анализа изменений в дискретных системах, заключается в следующем. Пусть имеется техническая система, у которой цифровой сигнал е {0,1} может изменить свое значение после возникновения некоторого события, например, вследствие возникновения ошибки. Ситуацию изменения сигнала можно выразить в виде ^ ® ' причем она обнаруживается только в случаях, когда значение изменяется с логического 0 на логическую 1 и наоборот. Тогда получается, что для произвольной булевой функции изменения можно выявить, если /,(х1,...,х1,...,х„)Ф /п1(х1,...,х,,....,х„) = 1, а это возможно в случае, когда хотя бы одна переменная х, изменила свое значение на противоположное.

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

Для комплексного изучения моделей булева дифференциального исчисления оказывается пригодным математический аппарат остаточных функций, определяемых в конечных полях. Пусть Е2 - множество со структурой поля порядка 2. Для произвольного натурального числа леК1 будем рассматривать векторное пространство наборов длины п с компонентами из Е2: Е2 х...х Е2 = Е".

Определение 1

Остаточными функциями по 1-му аргументу называются функции размерности, на единицу меньшие размерности исходной функции /, а именно:

......Ъ-|>Т1+1» — »Т#.) = /(Т1.....Т/-1»аГ»Х|Ч1» —»^я)

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

Определение 2

Производной булевой функции / по ¡-му аргументу (булевой производной) называется сумма по модулю 2 остаточных функций по этому аргументу. О

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

Определение 3

Производной от булевой функции /(х,,...,х„) по подмножеству переменных у с х , |У| = т называется выражение вида:

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

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

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

входа. В реализации используется код Хэмминга с проверочной матрицей Хэм-минга для того, чтобы обнаруживать любой двойной отказ и исправлять любой одиночный отказ. Структурная схема дискретного устройства с функцией самодиагностики представлена на рис. 1, где блоки «А» и «В» - это блоки реализации булевых функций и их производных.

Рис. 1. Структурная схема дискретного устройства с функцией самодиагностики Из входных значений исходной булевой функции / и её производной /' формируется кодовый вектор g, и задается проверочная матрица кода Хэмминга Н. Если при передаче кодового вектора 8 появилась ошибка, то в анализатор синдрома ошибки поступит вектор ^ + е), где е - вектор, содержащий «1» в том разряде, где произошла ошибка, и «О» - во всех остальных разрядах, и будет вычислен синдром ошибки ^ + е)Нт = еНт +еНт =еНт, так как вектор % принадлежит нулевому пространству проверочной матрицы Н. С помощью этого подхода могут быть реализованы и другие схемы помехоустойчивого кодирования.

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

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

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

Рассмотрим подробнее полученные в главе новые результаты.

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

Определение 4

Для произвольной булевой алгебры < В, ОЯ, АМО, N01,0,1 > двойственные бинарные операции можно получить, заменяя ОК на Л/Ш и 0 на 1.0

Далее обозначим через 0 любую решеточную операцию: либо ОК, либо AND, тогда двойственную к выбранной операции будем обозначать как У. Двойственная булева алгебра Вв может быть определена следующим образом.

Определение 5

Структура вида является булевой алгеброй, изоморфной

булевой алгебре

Выполним переход от решеточных двойственных операций в алгебре Вв к операциям в кольцах. Рассмотрим теперь булево кольцо {/?,+,«,0,1), у которого каждый элемент является идемпотентным, и оно представляет собой булеву алгебру. Введем обозначение Ка для кольца, изоморфного булеву кольцу Я, и назовем его кольцом с двойственными операциями. Теперь определимся с символическими обозначениями для нейтральных элементов относительно введенных двойственных операций для кольца .

Определение 6

ДляУ(а,Ь)еВв,

= тогда является нейтральным эле-

ментом относительно операции аналогично еи - {а (I Ж)Г(а))д

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

Утверждение 1

Булева алгебра с учетом вводимых обозначений принципа

двойственности представляет собой булево кольцо

</г0,Р,е(1,е11>, (1)

где § обозначает аддитивную операцию вида

а С Ь = (а и КОТ(Ь)) А (Ж>Г(а) У Ь) и, двойственно: булево кольцо (1) является булевой алгеброй В0, если операции О и N0 Т определены в ней следующим образом: а1и = а0ьи(а11г>), ИОТ(а) = а § е„ .□

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

Утверждение 2

Булеву функцию / (х) можно представить в виде'.

Разложение Шеннона с избыточным членом доказывается в следствии 1.

Разложения Рида-Маллера по одной переменной доказываются в утверждениях 3 и 4.

Утверждение 3

Булеву функцию можно представить в виде: Утверждение 4

Булеву функцию можно представить в виде:

/(*)=г(у)Щ4у)ъ(/т/(уЬп))),

где уе{е^,еа}В

Разложение Рида-Маллера для п переменных, где у с х , |х*| = п,

=(ф,.(/(*\/ = о)) ф,.(/(*>'= 1)) Ф,.(/(*\/=о)§/(*,/=:

в матричной записи доказывается в утверждении 5. Утверждение 5

Булеву функцию можно представить в виде:

< \

е<> вн

(♦-■(/('))) ^ ®

-и си е» еп х х!) е,

где операция 1} выполняется вместо матричного сложения, а операция fi выполняется вместо матричного умножения в прямом (Кронекеровом) произведении матрицП

Вторая, решаемая в главе, задача относится к разработке математических моделей описания производных булевых функций при частично определенных векторах переменных. Основной идеей предлагаемого далее подхода является доопределение частично определенных булевых функций с помощью векторов состояний, содержащих логическую производную. Пусть /(х) - частично определенная булева функция, где вектор входных параметров х е F^ не полностью определен на всем векторном пространстве F2" наборов длины п с компонентами из конечного поля Рг, и также пусть множество М = {0,1,*}, где знак «*» обозначает не полностью определенное значение, то есть либо 0, либо 1. Обозначим векторное пространство наборов длины и с компонентами из М:МхМх...хМ = М". Применим данное ранее утверждение 5 и получим век-

it раз

тор доопределения частично определенной булевой функции для одной переменной.

Определение 7

Вектор доопределения частично определенной булевой функции, составляемый по переменной xt, определяется как

mfi

дх.

(2)

где $ обозначает любую из рассматриваемых ранее двойственных операций. □ Выражение (2) может быть записано для двух переменных в виде

ф, (/(*,.*,))= «к (л,4ф, (лн)а, (л-н-о

Ф„ [fx,,а)Л,,

dxfixj

(3)

Далее используется рекурсивное применение выражений (2) и (3), и получается матричная форма записи вектора доопределения булевой функции. Как и прежде, используем обозначение $ для одной из двойственных операций, и

пусть $ будет являться дистрибутивной для операции 3}. Пусть также е5 и е.

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

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

ег е. е,

Приведенные рассуждения позволяют доказать утверждение 6. Утверждение 6

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

♦ (/) = [/.]

к

®М"

8 8 в

где ФМ" - Кронекерово произведение матриц М0М...ФМ.Р

п раз

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

число. Введем обозначение /„. =/(х......а,,..полагая, что в логической

функции в таком случае переменная х1 заменяется на переменную а..

Основным определением производной логической функции над полем расширения конечного поля является определение 8.

Определение 8

Частной производной логической функции /(х,,х2.....х^р^.х^,,...,^) над

конечным полем Р, по переменной х1 будем называть

(4)

где 1 < / < и, х*=(х,,...,*„),

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

Определение 9

Частной производной т-го порядка логической функции /(х,,х2,...,хь),х(,х,+1,...,хп) над конечным полем по переменным (х......х- ^ будем называть

8х....дх, 5х1

(5)

где 1\<т<*п, х' =(х„...,х„).0

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

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

Утверждение 7

Пусть / -> , а = (а,,...,ал), Ъ тогда выполняется

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

Утверждение 8

Логическая функция /: —> разложима в виде

И-1 '( г— »1» ^ ¿) "* ¡т

[1, еспих^с.\ [О, если х. Ф с,П

Ниже приведены основные вычислительные алгоритмы спектральных преобразований булевых и логических функций к полиномиальным представлениям Рида-Маллера (алгоритм 1 и алгоритм 2).

Алгоритм 1

Спектральное преобразование булевой функции к полиному Рида-Маллера

1. Формируем таблицу истинности У (л) булевой функции /(*,,...,*„), которая представляется в виде вектора.

2. Формируем матрицу Адамара Нт(я).

3. Выполняем конвертирование вектора У(и) = (_ур...,^„)Т, у, е {0,1} в вектор полярной таблицы истинности по правилу г:{0,1} ->{1,-1} и получаем вектор Ъ{п)={2х,...,2$.

4. Выполняем преобразование Уолша Нш(и)г(п) = 8(л) и получаем вектор спектральных коэффициентов.

5. В зависимости от требуемой полярности представления полинома Рида-Маллера рассчитываем матрицу !*■(«) полярностей полинома.

6. Рассчитываем вектор в* (л) = в (и) ■ II (и).

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

7.1. если в", < 0, то в /-ю строку добавляется знак «-»;

7.2. если = 0, то в / -ю строку добавляется знак «0»;

7.3. если в", > 0, то в г -ю строку добавляется знак «+».

8. По построенной таблице составляем полином Рида-Маллера в соответствии со следующими правилами:

8.1. если в ¿-ой строке столбца В, знак «-», то 8.1.1. если значение переменной х, =1, то записать ее в терм полинома с инвертированием;

8.2. если в 1-ой строке столбца В, знак «О», то пропустить строку;

8.3. если в / -ой строке столбца В,, знак «+», то

8.3.1. если значение переменной х(=1, то записать ее в терм полинома без инвертирования.

Алгоритм 2

Преобразование логической функции к полиному Рида-Маллера

1. Формируем код Грея для п переменных и записываем его в матрицу размера (2" х п).

2. В массиве размера 2" вычисляем и записываем значения функции / для аргументов из сформированной матрицы в элементы с индексами, соответствующими коду Грея.

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

4. Исключаем наборы, содержащие четное число нулей (так как суммирование по модулю 2 четного количества единиц дает в результате 0).

5. В каждом из оставшихся наборов заменяем любые его элементы на какой-либо произвольно выбранный символ (например,«+»).

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

Далее в работе рассматриваются символьные преобразования и предлагается алгоритм 3.

Алгоритм 3

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

На входе алгоритма имеется булева функция /(*,,...,*„) от и двоичных переменных.

1. Формируем код Грея для и переменных С(2" х(и+1)|, и в столбец л +1 записываем значения исходной булевой функции / при соответствующих наборах аргументов.

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

3. Формируем пустую матрицу В(2"), в которую будем записывать элементы в соответствии со следующими правилами.

4. В цикле повторений в последнем столбце матрицы С находим наборы из двух соседних элементов, то есть тех, у которых расстояние Хэмминга равно 1:

4.1. Если в сгруппированном наборе имеется одна 1 и один 0, также х1 =1 и значение булевой функции /=1, то такой набор считается сменой полярности булевой производной функции / (в связи с ее известным свойством).

4.2. В ячейки матрицы Б, которые соответствуют индексам элементов найденного набора матрицы С, записываем некоторый, заранее определяемый ключевой символ, например знак «V».

4.3. Повторяем шаги 4.1 и 4.2.

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

Далее рассматривается интерпретация известного абстрактного выражения, которое называется вариацией булевой функции /:

8/-¥ _

6х,

6х,

(8)

6/

гда&

57* 5/ О/

Отметим, что — = — ©—. Таким образом удается разделить изменение дх, Ьх, 5х,

О на 1 и 1 на 0. Обозначим «Д» и «V» - операторы логического изменения булевой функции из значения 0 в значение 1 и из значения 1 в значение 0 соответственно. Тогда вариация (8) может быть проинтерпретирована двумя способами:

д/-=Х ¡=1

дх, ' дх, 1 ^

дх,

дх,

= 1

М-^+Ж-чх,

дх, дх, дх, 1 дх, '

(9)

(10)

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

1сл=|5/=£|

5/ 5/-—х,

Полным интегралом от 6/ является множество функций для которых

г

8Г = 5/". Обратимся к интерпретациям (9) и (10), тогда IД/7 = 2_,

дх,

дх,

¥- Э/

дх, ' дх,

Ч ' ' у

Теперь на основе алгоритма 3 нахождения частных производных и выражений (9) и (10) можно предложить алгоритм 4 символьного вычисления булева интеграла.

Алгоритм 4

Символьное вычисление булева интеграла

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

2. Сформировать матрицу 1(2" х(и+ 1)), заполнив столбцы 1,...,л по принципу кода Грея.

3. Заполнить столбец п + 1 матрицы I символом 1, если вычисление по (9) дает в результате 1.

4. Заполнить столбец п +1 матрицы I символом 0, если вычисление по (10) дает в результате 1.

5. Заполнить единицами все ячейки столбца л +1 матрицы I, если расстояние Хэмминга между соседними с ними ячейками равно 1.

6. Выполнить символьную запись термов булева интеграла аналогично п. 5 алгоритма 3, причем между термами использовать знак «+».

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

В последнем параграфе главы рассматриваются принципы программной реализации предложенных алгоритмов.

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

Постановка и решение задачи синтеза контролируемой системы и контрольных уравнений.

Пусть Рч - конечное поле порядка ц. Линейной стационарной динамической системой (А,В,С), функционирующей в дискретные моменты времени, будем называть систему, наблюдаемая последовательность которой \у= Со/(у,и) удовлетворяет уравнениям:

х, =Ах, ,+Ви,;

' ' (И)

у,=Сх„

где Через

обозначены векторные пространства над полем через Яык (<?) обозначены пространства матриц соответствующих размерностей над полем Ря. Возникновение сбоя или отказа в некоторый момент времени ( приводит к нарушению уравнений (11), то есть мы наблюдаем в этот момент времени \», + ъ,=Со1(у,+ч„и, + 11,) и

В работе свойство системы - контролируемость - связано с контрольным уравнением:

(/,Л-Сх,) = 0,/*0, (13)

предназначенным для обнаружения искажений. Для вычисления контрольного уравнения необходимо вычисление скалярных произведений (/,у,),(ст/,х,). Напомним, что последовательность х - ненаблюдаемая последовательность, поэтому для реализации (13) необходимо исключить х, из контрольного уравнения:

^АЧ + ХА'В«,^. (14)

Далее будем считать, что х0 =0. Из (14) следует, что

(Ст/,*,) = g(CT/,A'BM(_w) = £(Вт (Ат)' с v, J • (15)

i=0 ¡=o v '

Отметим следующий факт. Если Вт(ат)ст/ = 0, для г = 0,1,...,и-1, то

(ст/,х,) = 0 для любого í, что существенно упрощает контрольное уравнение:

Ы = 0. (16)

Другими словами, если

рКег(вт(Ат)'ст)*0 или р]Кег(вт(Ат/)р|1т(Ст)*0, (17)

то существует такой вектор I, для которого контрольное уравнение приобретает вид (16). Приведем основное определение. Определение 10

Систему (А,В,С) будем называть контролируемой, если для нее существует контрольное уравнение (16) или рКег|вт(Ат) jf~]lm(CT)*0.D

Из определения непосредственно получаем, что [~]KerÍBT(ATVWo. Рас-

/=0 * '

им

QKer(BT(AT)'jJ =|(кег(вт(А^У)[ =|lm(A'B).

л-1

Подпространство R^ = ^Im(A'B) совпадает с управляемым подпространство

вом (А,В). Следовательно, справедливо утверждение 9. Утверждение 9

Необходимым условием для контролируемости динамической системы является условие R0 с R", или пара (А,В) является неуправляемой паройП Далее доказано следующее утверждение. Утверждение 10

По любой неуправляемой системе (А,В,С) можно построить контролируемую систему (А,В,С), причем матрица С либо совпадает с матрицей С, либо содержит одну дополнительную строку.О

смотрим

(п-\

Далее рассматривается управляемая система (А,В,С). Пусть Н - собственное подпространство матрицы Ат. Рассмотрим проекцию на подпространство Н:

¡1 < I

Поскольку вектор АТ£( б Н, то Ат^ = • Следовательно,

Поскольку векторы а линейно

I I

независимые, то V/ выполняется равенство = +

к

Пусть г, ={(&-.*,)}. тогда = Аг, + Вы,, где А = (аа), В = ((£„&,)), а Ъ] - ]-й столбец матрицы в. Рассмотрим динамическую систему (а,в,с) с

- (А <0 - Гв4)

пространством состояний К , с матрицей А= ^ ^ , матрицей В = и

матрицей С = (С 0). Наблюдаемая последовательность динамической системы

(А,В,С) совпадает с наблюдаемой последовательностью динамической системы

(А,В,с). Является справедливым следующее утверждение.

Утверждение 1 1

Пара (А,§) не является управляемой.□

Из утверждений (10) и (11) следует теорема. Теорема 1

По любой управляемой динамической системе (А,В,С) можно построить контролируемую динамическую систему (А,В,С), причем матрица С либо совпадает с матрицей С, либо содержит одну дополнительную строку.П

Далее рассматривается случай, когда минимальное собственное подпространство матрицы Ат совпадает с пространством К", то есть характеристический многочлен матрицы Ат неприводим над полем . В этом случае А=А, что эквивалентно дублированию динамической системы.

Динамическую систему (А,В,С) над полем обозначим , и характеристический многочлен / матрицы Ат неприводим над полем Р. Построим поле разложения многочлена / - и рассмотрим динамическую систему (А,В,С) над полем , которую обозначим £>5,. Поскольку Р^ является подпо-лем поля Р^,, то наблюдаемая последовательность совпадает с наблюдаемой последовательностью ., если компоненты входной последовательности и являются элементами поля Р. В диссертации доказывается

Утверждение 12

По любой управляемой динамической системе ББ^ над полем Г^, у которой характеристический многочлен матрицы АТ - /у(х) неприводим над полем можно построить контролируемую динамическую систему над полем ^ „, причем матрица С либо совпадает с матрицей С, либо содержит одну дополнительную строку, размер матрицы А - (п + 1)х(л + 1), размер матрицы В -(и + 1)х /•.□

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

Пусть во время / = 0 система находится в состоянии х0. Состояние х0 неизвестно. Требуется построить линейное контрольное уравнение:

¿(/«.Л) = е(&»и|)- (18)

/=| /»I

В (18) г - запаздывание. При этом тривиальное решение по естественным причинам исключается.

Доказано, что существование контрольного уравнения (18) эквивалентно условию:

= 0 или Кег(Нт) * 0, (19)

где Ь =

/Г

,Н,=((АТ)СТ (АТ)2СТ ... (Ат)ТСт).

В результате было доказано утверждение о минимальном запаздывании.

Утверждение 13

Минимальное значение х, при котором существует контрольное уравнение (16), совпадает с минимальным значением х, при котором

Кег(Н,)*0.0 (20)

Нелинейные динамические системы над конечными полями

Будем рассматривать частный случай динамической системы

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

Общий метод синтеза нелинейных контролируемых систем состоит в следующем.

Рассмотрим на множестве функций от п переменных и на множестве функций от т переменных полиномиальные базисы

, Ф =

которые подробно рассмотрены в главе 2. Выразим в этом базисе функции

П /=' м

Из базисных функций выделим линейные функции ч/рУз,...,^;^,,^;,,...,^.

Введем дополнительные переменные

=¥/2+Ди,.И2.....О-

Допустим, что нелинейные базисные функции имеют вид:

м

где I, с {!,...,«}.

Получаем следующее представление динамической системы:

.....

>1 >1

л

.о.

;

;=|

Хс^,« = 1,...,р.

Отметим, что а„+и е . Рассмотрим /*"(и1;...,иг) - мини-

мальное расширение поля , содержащее элементы ы,,...,ыг.

Рассмотрим над этим полем квадратную матрицу А = /-го порядка, матрицу В = размера /хг и матрицу С = (си) размера рхг. Использование этих матриц позволяет представить динамическую систему над полем ^(к„...,иг) в виде:

(О.

(22)

Приведенные выше выкладки доказывают следующую теорему. Теорема 2

Для любой динамической системы вида (21) существует линеаризация (22) надполем F.,м,)Л

Из теоремы 2 следует алгоритм 5. Алгоритм 5

Алгоритм синтеза контролируемой системы с минимальной избыточностью

1. Разложение булевых функций в линейном базисе.

2. Введение дополнительных переменных состояния и входа.

3. Определение уравнений для дополнительных переменных состояния.

4. Расширение поля Р2 до поля ......).

5. Линеаризация динамической системы над полем ^ (и,,......).

6. Синтез контролируемой линеаризации.

Таким образом, теорема линеаризации позволяет также предложить алгоритм 6.

Алгоритм 6

Алгоритм синтеза контрольного уравнения с запаздыванием

1. Разложение булевых функций в линейном базисе.

2. Введение дополнительных переменных состояния и входа.

3. Определение уравнений для дополнительных переменных состояния.

4. Линеаризация динамической системы.

5. Синтез контрольного уравнения с минимальным запаздыванием.

Глава 4 «Модели диагностики программного обеспечения в процессе

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

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

программы Р обозначим 0иТ(х,у), где х&В, уеЯ. Предикат ОК(с1) обозначает правильность результата исполнения программы при входе с1, тогда ОК(с/) = Ггме, тогда и только тогда, когда Пусть Т - конечное

множество тестовых наборов для программы Р, Тс,В. Определяются следующие предикаты:

1) $СТ(Т) - предикат успешности исполнения тестового набора, то есть БСТ(Т)<*\/1 <Ж(/).

2) ЙЕ1,(Г) = Ггме, предикат надежности тестового набора, обозначающий, что среди тестов, выбираемых из Т, имеются успешные тесты.

3) УАЬ(Т) = 1гие, предикат действенности тестового набора, обозначающий, что при неправильном результате исполнения программы Р хотя бы один из тестов, выбранных из Т, является не успешным.

При таких определениях основной теоремой является следующая.

Теорема 3

(ЗТ)(8СТ(Т)ЯЕЬ(Т)УА1(Т))^>(^)ОК(а).П

Такая формальная модель диагностики ПО имеет некоторые недостатки, препятствующие её применению в условиях нарастающих темпов усовершенствования ПО ИС.

Преодолеть недостатки указанной модели можно с помощью предлагаемой модификации. Пусть SEL(T) - предикат выбора тестового набора из множества Т. Переопределим предикаты правильности результата исполнения программы OK(d) и успешности исполнения теста SCT(T), как зависящие только от результата исполнения программы при входном домене d:

1) ОКи (P,d) - true, тогда когда OUT(d,P(d)) = true\

2) SCTU (Р,Т) = true, тогда когда Vie Г, ОКм (P,t).

Тогда справедливы утверждения 14 и 15.

Утверждение 1 4

VAL(T) о

Утверждение 15

REL(C) <=>

(SCT^PJ^SCT^PJ,))] .□

В утверждениях 14 и 15 (VP) обозначает, что предикат применим для всех программ с заданной выходной спецификацией.

Обозначим С - конечное множество тестовых предикатов из входного домена D так, что на входном наборе deDy для се С, c(d) = true выполняется условие успешности теста. Таким образом, можно определить предикат СМГ (Г, С) полноты выбранного тестового набора в виде следующего утверждения.

Утверждение 16

Для ТcD

СМТ(Т,С) = (Vc е С)(3/ е T)c(t) л (V/ е Г)(3с е С)с(г). □

Утверждение 16 означает, что для каждого тестового предиката выбирается тестовый набор, выполнение которого разрешимо в тестовом предикате.

Утверждение 1 7

Критерий (предикат) выявления ошибок в ПО

DET(P,T) <Р> (3d)CMT(T,C){-,OKu (P,d)) => (V7) а

a(SEL(T) => ->SCTU (P,T)).

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

Пусть Р - множество диагностируемых программ Р, множество формальных спецификаций программ S обозначим S, а множество тестовых наборов Г для них Т, также реРс,Р, seScS, /еГсТ. Определим предикат корректности исполнения программы р, имеющей спецификацию s, через COR(p,s), также предикат RES(p,s,t) обозначающий результат тестирования программы р

тестовым набором t по спецификации программы 5. Тогда обобщенную модель диагностики ПО ИС можно определить в следующем виде.

Определение 11

Обобщенная модель диагностики ПО ИС определяется (P,S,Т,COR,RES), где Р, S, Т - произвольные множества диагностируемых программ, их спецификаций, тестовых наборов соответственно, COR с Р х S, RES с Т х Р х S и

VpVsVt(COR(p,s)=>RES(p,s,t)). □

Утверждение 18

Обобщенной предикатной моделью диагностики ПО ИС является система (p,S,T,COR,RES},ТсT,RES(p,s,t)о Vi(f e TRES(p,s,t)). □

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

Рассмотрим спецификацию Р®Р£ ■

Утверждение 19

Независимость от замены X на В выполняется тогда и только тогда, когда предикат Р н , имеет истинное значение.О

На основе этого сформулируем следующее утверждение.

Утверждение 20

Р ® Pg = 0 тогда и только тогда, когда предикат Р не зависит от замены X на В.U

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

Пусть рассматривается предикатная формула F = /(/¡,...,/>„), предикаты в которой связываются операциями л, v, -i. Тогда определение частной предикатной производной формулируется следующим образом.

Определение 12

dF

Частная предикатная производная определяется формулой — = / © .□

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

Общая методика применения предикатных производных для анализа спецификаций программ заключается в следующем. Введем логическую функцию, предназначенную для контроля над изменениями вида P=$Q, которую обозначим G. По определению 12, для того, чтобы выявить изменения в Р, требуется

„ 3G ,

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

дР

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

торое изменение М, РМ => Q. Также требуется выяснить, что вносимые изменения, если они произошли, не влекут изменений за собой в предикатной производной, то есть PM=>8G/8P. Доказательство этого факта напрямую эквивалентно РМ => Q, которое формализовано в виде теоремы, доказанной в диссертации.

Теорема 4

(Р => Q)[M => SG/dP) о (Р => Q)(PM => Q) .□

Полученные результаты могут быть применены для анализа и контроля над изменениями в программах следующим образом. Пусть Р - предикат, состоящий из композиции элементарных предикатов X,Y, входящий в спецификацию S программы. Определим дифференциальные операторы анализа изменений в спецификациях программ: 8SX

1. 7J = - оператор замены элементарного предиката.

2. Т2= —=4- - оператор инверсии элементарного предиката.

дХ

3. Г3 = q^xy} ~ 0ПеРат0Р замеиы конъюнкции в элементарном предикате.

dSx

4. Г4 = Xvr - оператор замены дизъюнкции в элементарном предикате.

d(XvV)

8S?

5. Т5 - оператор инверсии предиката Р.

В главе доказаны теоремы, устанавливающие соотношения между этими операторами.

Теорема 5

Если диагностические операторы 7J и Т2 одновременно обнаруживают изменения в программной спецификации, то Т{ —> r2.D

В соответствии с этой теоремой устанавливается факт, что если при исполнении диагностического теста 7] = true, тогда Т2 = true.

Таким образом, можно сформулировать следствие из теоремы 5 в следующей формулировке.

Следствие 2

Любой диагностический оператор, обнаруживающий замену элементарного предиката, также обнаруживает инверсию элементарного предиката в программной спецификации. □

Теорема 6

Если инвертирование предиката в диагностическом операторе Т2 вызывает инвертирование предиката в диагностическом операторе Т5, то T2-*Ts.O

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

Следствие 3

Любой диагностический оператор, обнаруживающий инверсию элементарного предиката, обнаруживает также инверсию всего предиката, состоящего из логических связок элементарных предикатов. О Теорема 7

Если диагностический оператор обнаруживает замену элементарного предиката, замену конъюнкции в элементарном предикате, замену дизъюнкции в

элементарном предикате, то ((Г3 V Г4) 7]) (Гз V Т4). О

В соответствии с теоремами 5-7 можно представить графическую интерпретацию введенных диагностических операторов (рис. 2)._

Тъ

оператор инверсии всего предиката

Тг оператор инверсии элементарного предиката

Тл

оператор замены

элементарного предиката

Л-

7з<

! оператор замены конъюнкции в элементарном предикате

Та (

ч

I оператор замены дизъюнкции в элементарном предикате

Рис. 2. Схема взаимосвязи диагностических операторов Следствиями из теоремы 7 являются следующие. Следствие 4

Любая диагностическая процедура, которая состоит из введенных ранее диагностических операторов, обнаруживающих замену конъюнкции либо дизъюнкции в элементарном предикате, также обнаруживает замену и самого элементарного предиката. □ Следствие 5

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

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

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

Програмный комплекс и его модули были реализованы на языке программирования С с использованием кроссплатформенного компилятора GNU g + + / gfortran и кросплатформенной среды разработки визуальных интерфейсов QíDesigner и библиотек QtA. Программный комплекс выполнен в виде opensource продукта, и его исходный код может быть скомпилирован в исполняемый код на платформе Windows / Lima / Solaris / MacOS.

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

1. Уровень символьных вычислений на математическом псевдоязыке.

2. Уровень визуального редактирования и отображения комбинационных

схем.

3. Уровень программирования и использования подключаемых модулей.

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

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

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

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

- функции, реализующие алгоритмы синтеза контролируемых нелинейных

схем;

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

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

Рис. 3. Структура основных классов комплекса программ

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

Методы диагностики, основанные на применении аппарата булевых производных, были реализованы в системе автоматизации контроля и диагностирования устройств железнодорожной автоматики и телемеханики (НЛП «Югпромав-томатизация») в следующих подсистемах:

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

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

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

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

Некоторые из предложенных в диссертации методов внедрены в системе мониторинга и контроля предоставления информационных услуг (МКИУ) телекоммуникационной компании «Альянс-Телеком». Основной подсистемой для реализации новых методов и алгоритмов является подсистема экспертизы и контроля качества в составе МКИУ. В результате внедрения были модифицированы

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

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

Основные результаты диссертации опубликованы в работах:

Публикации в периодических изданиях, рекомендованных ВАК РФ для изложения результатов докторских диссертаций

1. Чернов A.B. Методы линеаризации и модели контролируемых нелинейных дискретных динамических систем // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - СПб., 2009. - №2. - С. 156-162.

2. Белявский Г.И., Чернов A.B. Математические модели линейных контролируемых дискретных динамических систем // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - СПб., 2009.-№2.-С. 145-151.

3. Чернов A.B. Синтез интеллектуальных самотестируемых устройств для систем управления электроэнергетическими объектами // Известия высших учебных заведений. Электромеханика. - 2009. - № 2. - С. 65 - 68.

4. Чернов A.B. Об актуальности развития новых направлений в математической теории надежности информационных сетей с пакетной передачей данных // Обозрение прикладной и промышленной математики, 2008. - Т. 15. - Вып. 1. -С. 184- 185.

5. Чернов A.B. Применение моделей случайных графов и бинарных диаграмм решений к задачам анализа надежности информационных сетей // Обозрение прикладной и промышленной математики. - 2008. - Т. 15. - Вып. 2 - С. 376 -377.

6. Чернов A.B. Развитие аппарата логического дифференциального исчисления в применении к задачам проектирования и диагностики телекоммуникационных систем // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - СПб., 2008. - № 2. - С. 118 - 126.

7. Чернов A.B., Рассказов Д.А. Алгоритмическое и программное обеспечение символьных вычислений для логического дифференциального и интегрального исчисления // Программные продукты и системы, 2008. - № 2. - С. 93 - 96.

8. Гуда А.Н., Чернов A.B. Алгоритмы спектральных и символьных преобразований булевых функций для решения задач анализа и проектирования технологически безопасных информационных систем // Вестник Ростовского государственного университета путей сообщения, 2008. - № 2. - С. 46 - 53.

9. Чернов A.B. Синтез контрольного уравнения для линейной динамической системы // Обозрение прикладной и промышленной математики. - 2008. - Т. 15.-Вып. 5. - С. 945.

10. Чернов A.B. Частично определенные булевы функции с логическими производными в моделях технической диагностики дискретных систем // Известия вузов, Северо-Кавказский регион. Технические науки, 2008. - № 5. - С. 8 -11.

11. Чернов A.B. Модели анализа и диагностики формальных спецификаций программного обеспечения информационно-управляющих систем // Вопросы со-

временной науки и практики. Университет им. В.И.Вернадского, серия «Технические науки», 2008. - Т. 2. - № 4(14). - С. 147 - 153.

12. Чернов A.B. Алгоритм синтеза контрольного уравнения для линейной динамической системы над конечным полем // Обозрение прикладной и промышленной математики, 2008. - Т. 15. - Вып. 6. - С. 999 -1002.

13. Белявский Г.И., Чернов A.B. Контролируемость и управляемость в детерминированных динамических системах над конечными полями // Вестник Донского государственного технического университета, 2008 - Т.8, № 4(39). - С. 357-365.

14. Чернов A.B. К вопросу о разработке математических моделей рефакто-ринга программного обеспечения II Обозрение прикладной и промышленной математики, 2007. - Т. 14. - Вып. 2-С. 368 - 369.

15. Гуда А.Н., Бутакова М.А., Чернов A.B., Чакрян В.Р. Современное состояние исследований в области теории телетрафика - от Марковских процессов до мультифракталов и вейвлетов // Вестник Ростовского государственного университета путей сообщения, 2007. - № 3 - С. 17 - 23.

16. Иванов С.О., Чернов A.B. Об адаптивной методике количественной оценки защищенности автоматизированных банковских систем II Обозрение прикладной и промышленной математики, 2003. - Т. 10. - Вып. 2. - С. 139.

17. Чернов A.B. Применение байесовского статистического вывода для идентификации угроз безопасности рабочих мест в корпоративной сети // Обозрение прикладной и промышленной математики, 2002. - Т. 9. - Вып. 1- С. 264.

18. Чернов A.B. О применении современных методов кодирования информации в автоматизированных системах управления на транспорте // Обозрение прикладной и промышленной математики, 2002. - Т. 9. - Вып. 2. - С.484 - 485.

19. Лябах H.H., Шабельников А.Н., Чернов A.B. Безопасность и качество функционирования программного обеспечения информационно-управляющих систем на транспорте // Вестник Всероссийского научно-исследовательского института железнодорожного транспорта, 2001.-. № 5. - С. 17 - 20.

20. Чернов A.B. Учет свойства безопасности функционирования программного обеспечения информационно-управляющих транспортных систем II Известия вузов. Северо-Кавказский регион. Технические науки, 2001.-№ 3. -С. 17 - 20.

21. Чернов A.B. Формализация критериев технологической безопасности информационных систем на транспорте // Обозрение прикладной и промышленной математики, 2001. - Т. 8. - Вып. 2. - С. 721 - 722.

22. Чернов A.B., Ульяницкий Е.М. Способ повышения точности регистратора параметров аварийного режима воздушной линии электропередачи // Известия высших учебных заведений. Электромеханика, 1997. - № 1-2. - С. 114-117.

23. Чернов A.B., Ульяницкий Е.М. Использование масштабирующего усилителя в регистраторах параметров аварийного режима воздушной линии электропередачи // Известия высших учебных заведений. Электромеханика, 1997. -№1-2. -С. 74-75.

Монография

24. Чернов A.B. Модели и методы дискретного анализа и синтеза в задачах технической диагностики информационных систем: Монография. - Ростов н/Д: Изд-во ЮФУ, 2009. - 170 с.

Другие работы, в которых опубликованы результаты диссертации

25. Белявский Г.И., Чернов A.B. Логические дифференциальные операторы и уравнения над конечными полями и параллельные вычисления // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. науч. тр.

V-й Международной научно-технической конференции (Коломна, 20-3-мая 2009 г.) В 2-х томах. Т. 1. - М.: Физматлит, 2009. - С.190 - 197.

26. Чернов A.B. О задаче онлайновой диагностики и синтеза контролируемых информационных систем // Матер, юбилейной Междунар. науч.-практ. конф. «Строительство-2009». - Ростов н/Д: РГСУ, 2009. - С. 167 - 169.

27. Гуда А.Н., Чернов A.B. Анализ безопасности функционирования программного обеспечения информационных систем на транспорте на основе логического дифференциального исчисления // Телекоммуникационные и информационные технологии на транспорте России / Аннотации докладов Шестой междунар. науч.-практ. конф. «ТелекомТранс-2008». - Сочи, 2008. - С. 43 - 44.

28. Чернов A.B., Рассказов Д.А. Программный комплекс моделирования и синтеза отказоустойчивых контролируемых информационных систем. Св-во о гос. регистрации № 70200600585, св-во об отраслевой регистрации разработки № 8038,2008.

29. Чернов A.B. Двоичные динамические модели диагностики телекоммуникационных сетей на основе логического дифференциального исчисления // Управление созданием и развитием систем, сетей и устройств телекоммуникаций / Тр. науч.-практ. конф. Санкт-Петербургского государственного политехнического университета. - СПб., 2008. - С. 340 - 346.

30. Чернов A.B. Диагностика цифровых устройств на основе анализа помехоустойчивости логических функций // Теория, методы и средства измерений, контроля и диагностики / Матер. VIII Междунар. науч.-практ. конф. ЮжноРоссийского государственного технического университета (НПИ). - Новочеркасск, ЮРГТУ (НПИ), 2007. - С. 97 - 99.

31. Гуда А.Н., Бутакова М.А., Чернов A.B. Концепция моделирования региональных информационных систем железнодорожного транспорта // Телекоммуникационные и информационные технологии на транспорте России / Сб. докл. Пятой юбил. междунар. науч.-практ. конф. «ТелекомТранс-2007». - Ростов н/Д: РГУПС. С. 32-36.

32. Чернов A.B. Методы символьного имитационного моделирования в приложениях к задачам диагностики компьютерных сетей // Пятая междунар. науч.-практ. конф. «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем». - Новочеркасск, ЮРГТУ (НПИ), 2007.-С. 140-142.

33. Гуда А.Н. Чернов A.B. Задача обеспечения безопасности информационных систем на транспорте в современных условиях // Телекоммуникационные и информационные технологии на транспорте Росси / Аннотации докладов Четвертой междунар. науч.-практ. конф. «ТелекомТранс-2006». - Сочи, 2006. - С. 67 -68.

34. Гуда А.Н. Чернов A.B. Обеспечение безопасности транспортных информационных систем // Телекоммуникационные и информационные технологии на транспорте России / Сб. докл. Четвертой междунар. науч.-практ. конф. «Теле-комТранс 2006». - Сочи, 2006. - С. 275 - 281.

35. Бутакова М.А., Чернов A.B. Модель пакетного маршрутизирующего коммутатора в корпоративной телекоммуникационной сети // Тез. докл. XIV Межд. конф. «Математика. Экономика. Образование». - Ростов н/Д: Изд-во РГУ, 2006.-С. 51-52.

36. Чернов A.B. Байесовская модель информационной сети на транспорте с учетом дестабилизирующих факторов // Новые технологии управления движени-

ем технических объектов. - Ростов-н/Д: Изд-во СКНЦ ВШ, 2002. - Вып. 3. - Ч. 2. -С. 38-40.

37. Чернов A.B. Совершенствование средств защиты автоматизированных рабочих мест в корпоративной сети СКЖД // Тр. Второй науч. конф. «Безопасность информационных технологий». - Таганрог, 2002. - С. 26 - 29.

38. Чернов A.B. Байесовский подход в обеспечении информационной безопасности корпоративных компьютерных сетей // X межд. конф. «Математика. Экономика. Образование». Тез. докл. - Ростов н/Д: Изд-во РГУ, 2002. - С. 242 -243.

39. Чернов A.B., Щавельников А.Н. Анализ условий безопасного программного управления в автоматизированных системах железнодорожного транспорта // Сб. матер. Первой ведомств, конф. МПС «Проблемы обеспечения информационной безопасности на федеральном железнодорожном транспорте». ГУП АЦ «Желдоринформзащита МПС». - СПб., 2001. - С. 101 - 104.

40. Чернов A.B. Методы формальных спецификаций программного обеспечения для безопасных информационных транспортных систем // Тр. науч.-теор. конф. проф.-препод. состава «Транспорт-2001». Ч. 1. - Ростов н/Д: РГУПС, 2001. -С. 63-64.

41. Бутакова М.А., Чернов A.B. Способ снижения информационной нагрузки диспетчерского персонала в условиях ограниченного времени // Сб. докл. 6-й ме-ждунар. науч.-практ. конф. «ИНФОТРАНС - 2001». -Ростов н/Д: 2001. -С. 326 -328.

42. Бутакова М.А., Чернов A.B. Об одном методе оценки качества программного обеспечения // Тр. науч.-теор. конф. проф.-препод. состава «Транспорт-2001». Ч. 1. - Ростов н/Д: РГУПС, 2001. - С. 28.

43. Ульяницкий Е.М., Хошафян О.С., Чернов A.B. О свойствах архитектуры распределенных вычислительных систем на железнодорожном транспорте // Вестник Ростовского государственного университета путей сообщения, 2000. -№2.-С. 104-107.

44. Бутакова М.А., Чернов A.B. О развитии технологий обмена информацией в автоматизированных системах железнодорожного транспорта // Тр. Второй междунар. отрасл. науч.-техн. конф. «Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении». - Ростов н/Д: РГУПС, 2000.-С. 17.

45. Чернов A.B. Информационные системы на основе распределенных вычислительных систем // Труды 59-й вузовской науч.-теор. конф. проф.-препод. состава «Транспорт-2000». - Ростов н/Д: РГУПС, 2000. - С. 12.

46. Чернов A.B. О формализованном описании иерархических структур программных средств И Тр. межд. науч.-практ. конф. «Проблемы и перспективы развития железнодорожного транспорта». - Ростов н/Д: РГУПС, 1999. - С. 98 - 99.

47. Чернов A.B. Сравнительный анализ показателей качества современных операционных систем // Матер. 58-й науч. конф. проф.-преп. состава РГУПС. -Ростов н/Д: РГУПС, 1999. - С. 32.

48. Чернов A.B. Исследование критериев качества программных средств информационных систем // Тез. докл. отрасл. науч.-практ. конф. «Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении». - Ростов н/Д: РГУПС, 1998.-С. 227.

49. Чернов A.B. Проблемы системного анализа качества программного обеспечения // Матер, межгосуд. науч.-практ. конф. «Экономико-организационные

w

проблемы проектирования и применения информационных систем». - Ростов н/Д: РГЭА, 1997.-С. 24.

50. Чернов A.B. О принципах построения устройства диагностики в микропроцессорной системе релейной защиты // Вопросы совершенствования систем автоматики, телемеханики и связи на железнодорожном транспорте: Межвуз. сб. науч. тр. - Ростов н/Д: РГУПС, 1996. - С. 33 - 38.

51. Чернов A.B. О подходе к оптимизации структуры операционной системы для компьютерной релейной защиты // Информационные системы на железнодорожном транспорте: Межвуз. сб. науч. тр. / Под ред. д.т.н., проф. Е.М. Ульяниц-кого. - Ростов н/Д: РГУПС, 1998. - С. 15 - 19.

52. Ульяницкий Е.М., Чернов A.B. Алгоритм распределения программ в мультикомпьютерной системе релейной защиты // Матер, межгосуд. науч.-практ. конф. «Организационно-экономические проблемы проектирования и применения информационных систем». - Ростов н/Д: РГЭА, 1996. - С. 28 - 29.

Личный вклад автора в работах, выполненных в соавторстве

/2,13/ - решение задачи синтеза контрольных уравнений; /7, 28/ - постановка и формализация задачи, разработка алгоритмов; /8/ - разработка численных методов спектральных и символьных преобразований булевых функций; /15/ -обзор математических моделей; /16/ - постановка задачи; /19, 27, 33, 34, 39, 43, 52/ - анализ вопросов безопасности и надежности функционирования программного и аппаратного обеспечения; /22, 23, 31, 35/ - анализ методов и разработка математических моделей технической диагностики в исследуемых задачах; /25/ -исследование свойств логических дифференциальных операторов, общая модель дифференциальной дискретной системы; /41, 44/ - анализ риска возникновения ошибок; /42/ - обобщенная модель диагностики программного обеспечения.

Чернов Андрей Владимирович

Модели и методы логико-алгебраического анализа и синтеза в задачах технической диагностики информационных систем

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 2,0. Тираж 100. Заказ № 4682.

Ростовский государственный университет путей сообщения

_Ризография РГУПС_

Адрес университета: 344038, Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2

ВВЕДЕНИЕ.

1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ДИСКРЕТНОГО АНАЛИЗА В ТЕХНИЧЕСКОЙ ДИАГНОСТИКЕ И ИХ НОВЫЕ НАПРАВЛЕНИЯ.

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

1.2. Модели дискретного анализа в технической диагностике.

1.2.1. Предварительные замечания об исследованиях в данной области.

1.2.2. Определение булевых функций в конечных полях.

1.2.3. Базисы разложения булевых функций.

1.2.4. Булевы производные: основные определения.

1.2.5. Булевы производные: свойства.

1.2.6. Аспекты применения рассматриваемых методов и моделей.

1.3. Задачи технической диагностики информационных систем.

1.3.1. Задачи диагностики телекоммуникационных систем.

1.3.2. Задачи диагностики программного обеспечения.

1.3.3. Задачи математического моделирования диагностируемых систем.

1.4. Задача онлайновой диагностики и синтеза контролируемых информационных систем.

1.5. Выводы.

2. МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ДИСКРЕТНОГО АНАЛИЗА ЛОГИЧЕСКИХ ФУНКЦИЙ.

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

2.1.1. Модели декомпозиции с двойственными операгршт.

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

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

2.2. Логические дифференциальные операторы над конечными полями.

2.2.1. Свойства логических дифференциальных операторов.

2.2.2. Разложение логических функций над конечными полями.

2.2.3. Общая модель дифференциальной дискретной системы.

2.3. Модели спектрального представления логических функций над конечными полями.

2.4. Алгоритмы спектральных преобразований булевых функций.

2.5. Алгоритмы вычислений и символьных преобразований в булевом дифференциальном и интегральном исчислении.

2.6. Выводы.

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

3.1. Основные определения, обозначения и факты.

3.1.1. Многочлены над конечными полями.

3.1.2. Алгоритм вычисления поля разложения.

3.2. Модели линейных стационарных динамических систем.

3.2.1. Авторегресснонная модель.

3.2.2. Модель типа вход-выход.

3.2.3. Модели типа вход-состояние-выход.

3.2.4. Связь между авторегрессионной моделью и моделью входвыход.

3.2.5. Связь между авторегрессионной моделью и моделью вход-состояние-выход

3.3. Постановка и решение задачи синтеза контролируемой системы и контрольных уравнений.

3.3.1. Пример синтеза контролируемой системы.

3.3.2. Синтез контрольного уравнения при возможности запаздывания.

3.3.3. Пример синтеза контрольного уравнения.

3.4. Нелинейные динамические системы над конечными полями.

3.4.1. Пример нелинейной динамической системы над полем F2.

3.4.2. Общий метод синтеза нелинейных контролируемых систем.

3.5. Выводы.

4. МОДЕЛИ ДИАГНОСТИКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ В ПРОЦЕССЕ ФУНКЦИОНИРОВАНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ.

4.1. Особенности диагностики программного обеспечения в процессе функционирования и задачи своевременного обнаружения ошибок.

4.2. Обобщенная предикатная модель диагностики программного обеспечения.

4.3. Дифференциальный метод диагностики программного обеспечения.

4.3.1. Критерии анализа изменений спецификаций программ.

4.3.2. Диагностика на основе предикатной производной.

4.4. Метод своевременной диагностики программного обеспечения.

4.5. Выводы.

5. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ МОДЕЛИРОВАНИЯ, ДИАГНОСТИКИ И СИНТЕЗА ИНФОРМАЦИОННЫХ СИСТЕМ.

5.1. Сравнительный анализ систем компьютерной алгебры: возможности логических преобразований в конечных полях.

5.2. Программный комплекс моделирования и анализа задач технической диагностики информационных систем.

5.2.1. Основные функциональные возможности комплекса.

5.2.2. Модули реализации алгоритмов численных вычислений.

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

5.3.1. Модуль реализации алгоритмов синтеза контролируемых линейных систем.

5.3.2. Модуль реализации алгоритмов синтеза нелинейных линеаризуемых систем.

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

5.4. Аспекты реализации методов и моделей в существующих информационных системах.

5.4.1. Диагностические комплексы информационно-управляющих систем железнодороэюиого транспорта.

5.4.2. Подсистемы управления качеством обслуживания в системах предоставления информационных услуг.

5.5. Выводы.

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

Предлагаемый в работе новый комплексный подход к решению задач моделирования и синтеза ИС является дальнейшим развитием математических методов исследования линейных и нелинейных дискретных систем, определяемых над конечными полями, которые используют усовершенствованные методы логического дифференциального, интегрального исчислений, спектральных и символьных преобразований логических функций. При этом использованы результаты основополагающих работ в области логико-алгебраического моделирования, математических моделей технической диагностики и синтеза надежных ИС, а именно труды: Биргера И.А., Дружинина Г.В., Журавлева Ю.И., Майерса Г., Немолочнова О.Ф., Пархоменко П.П., Поспелова Д.А., СапожниковаВ.В., Сапожникова Вл.В., Шубинского И.Б., Ушакова И.А.; в области дифференциального исчисления логических функций - работы Акерса С.Б., Астола Р., Бохманна Д., ГиббсаД.Е., Горбатова В.А., Давно М.Д., Закревского А.Д., Сэллерса Ф.Ф., ТейзаА., Янушкевич С.Н.; в области алгебраического подхода к общей теории моделирования систем - труды Арбиба М., КалманаР.Е., Уонема М., Фалба П.Л.; в теории конечных полей - труды Лидла Р., Нидеррайдера Г.

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

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

Актуальность тематики подтверждается тем фактом, что работа подержана:

- грантом РФФИ 09-08-00097а «Дискретные динамические и стохастические модели анализа информационно-управляющих систем на транспорте и синтеза надежных цифровых структур» (2009 - 2011 гг.);

- грантом Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009 - 2013 гг. (мероприятие 1.1 «Проведение научных исследований коллективами научно-образовательных центров» - IV очередь), шифр 2009-1.1-113-050 «Проведение научных исследований коллективами научно-образовательных центров в области информатики», тема 2009-1.1-113-050-043 (2009-2011 гг.);

- грантом программы «Развитие научного потенциала высшей школы (2006 - 2008 гг.)» РНП.2.1.1.1038 тема РОСТ-НИЧ-692;

- грантом научно-исследовательской и опытно-конструкторской разработки Южного федерального университета per. № 3793 (2009 г.).

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

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

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

2. Разработка методологии синтеза самодиагностируемых ИС.

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

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

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

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

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

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

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

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

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

Предметом исследования являются модели и методы анализа, синтеза и алгоритмической реализации контролируемых ИС с возможностями самодиагностики.

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

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

Объект, предмет и методы исследования отвечают формуле специальности 05.13.18, так как содержанием работы является разработка фундаментальных основ и применение математического моделирования, численных методов и комплексов программ для решения научно-технической прикладной проблемы, исследование математических моделей технических объектов и соответствуют пунктам паспорта специальности: «1. Разработка новых математических методов моделирования объектов и явлений.»; «2. Разработка, исследование и обоснование математических объектов.»; «5. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; «6. Комплексное исследование научных и технических, фундаментальных и прикладных проблем с применением современной технологии математического моделирования и вычислительного эксперимента».

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

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

1. На основе сравнительного анализа существующих моделей и методов в технической диагностике ИС

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

- выявлены задачи диагностики телекоммуникационных систем и ПО;

- сформулированы задачи математического моделирования диагностируемых систем;

- сформулирована задача онлайновой диагностики и синтеза контролируемых ИС.

2. На основе анализа моделей и алгоритмов, которыми располагает логическое дифференциальное исчисление

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

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

- получена общая модель дифференциальной дискретной системы;

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

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

3. На основе анализа описаний динамических систем над конечными полями, а именно, моделей: авторегрессионной, типа вход-выход, вход-состояние-выход;

- введено свойство «контролируемости» системы и решена задача синтеза контролируемой системы;

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

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

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

- получена предикатная логическая производная, как аналог логической производной, обобщенной для анализа спецификаций ПО;

- разработан метод анализа изменений в спецификации ПО с помощью предикатной производной;

- разработана обобщенная предикатная модель диагностики ПО ИС;

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

Основные результаты, выносимые на защиту.

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

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

3. Постановка и решение задачи разработки модели онлайновой диагностики аппаратного и ПО.

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

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

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

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

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

9. Метод синтеза контрольных уравнений с минимальным запаздыванием для линейной динамической системы.

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

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

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

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

Практическую ценность представляют следующие результаты.

1. Разработан комплекс программ, в котором реализованы:

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

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

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

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

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

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

- анализировать функционирование дискретных динамических систем на основе линейных контрольных соотношений;

- синтезировать контрольные соотношения для динамических систем с минимальным запаздыванием.

3. Разработано и внедрено ПО:

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

- реализующее алгоритмы и программы диагностики на основе предикатной производной;

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

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

Реализация результатов работы.

Результаты работы прошли успешную апробацию, внедрены и используются: в научно-производственном предприятии (НПП) «Югпромавтомати-зация» при разработке диагностических подсистем для информационно-управляющих систем на транспорте; в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи в контрольно-диагностическом комплексе устройств сортировочных станций; в телекоммуникационной компании «Альянс-Телеком» в системе мониторинга и контроля предоставления информационных услуг связи по передаче данных и доступу к сети Интернет. Разработанный автором программный комплекс зарегистрирован в отраслевом фонде алгоритмов и программ. Научные результаты работы используются в учебном процессе Ростовского государственного строительного университета.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на всероссийских симпозиумах по прикладной и промышленной математике (2001 - 2009 гг., Сочи, Ростов-нао

Дону, Йошкар-Ола, Петрозаводск, Кисловодск, Волжский, Санкт-Петербург); на научно-практической конференции Санкт-Петербургского государственного политехнического университета (2008 г.) «Управление созданием и развитием систем, сетей и устройств телекоммуникаций»; на международных научно-практических конференциях Южно-Российского государственного технического университета (Н11И), Новочеркасск: «Теория, методы и средства измерений, контроля и диагностики» (2007 г.), «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (2007 г.); на межведомственных и международных конференциях «Телекоммуникационные и информационные технологии на транспорте России» (2001, 2006, 2007, 2008 гг., Сочи); на международных конференциях «Математика. Экономика. Образование» (2002, 2006 гг., Новороссийск); на Международной научно-практической конференции «Организационно-экономические проблемы проектирования и применения информационных систем» (1996 г., Ростов-на-Дону); на Ведомственной конференции МПС «Проблемы обеспечения информационной безопасности на федеральном железнодорожном транспорте» (2001 г., Санкт-Петербург); на научной конференции «Безопасность информационных технологий» (2002 г., Таганрог); на Международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (2009 г., Коломна); на конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (РГУПС) (1999 - 2001 гг.), и Ростовского государственного строительного университета (РГСУ) (2009 г.); на научных семинарах кафедр «Информатика» РГУПС, «Прикладная математика и вычислительная техника» РГСУ, «Алгебра и дискретная математика» Южного федерального университета.

Публикации. Полученные в диссертации теоретические и практические результаты нашли свое отражение в 52 печатных работах, в том числе монографии, 23 статьях в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, приложений, списка литературных источников из 175 наименований. Общий объем диссертации составляет 281 стр., из которых объем основного текста составляет 256 стр.

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

1. Выполнен обзор и анализ современных работ в области технической диагностики аппаратного и ПО ИС, на основе которого выявлены и сформулированы основные проблемы и задачи в данной области.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Аркадьев А. Г., Браверман Э. М. Обучение машины распознаванию образов. М.: Наука, 1964. 110 с.

2. Бек К. Экстремальное программирование: разработка через тестирование. Библиотека программиста. СПб.: Питер, 2003.

3. Беккер П. В., Йенсен Ф. Проектирование надежных электронных схем. М.: Советское радио, 1977. 256 с.

4. Белявский Г. И., Чернов А. В. Контролируемость и управляемость в детерминированных динамических системах над конечными полями // Вестник Донского государственного технического университета. Ростов н/Д, 2008. №4. Т. 8. С. 357-364.

5. Белявский Г. И., Чернов А. В. Математические модели линейных контролируемых дискретных динамических систем // Научно-технические ведомости СПбГПУ. СПб.: Изд-во политехнического университета. 2009. №2. С. 145-151.

6. Бестугин А. Р., Богданова А. Ф., Стогов Г. В. Контроль и диагностирование телекоммуникационных сетей. СПб.: Политехника, 2003. 174 с.

7. Биргер И. А. К математической теории технической диагностики. В кн.: Проблемы надежности в строительной механике. Вильнюс, 1968. С. 10 - 14.

8. Биргер И. А. Техническая диагностика. -М.: Машиностроение, 1978. 240 с.

9. Бохманн Д., Постхофф X. Двоичные динамические системы. М.: Энергоатомиздат, 1986.

10. Бутакова М. А. Исследование телекоммуникационных сетей в условиях автомодельных потоков с сильным последействием // Известия вузов. Северо-Кавказский регион. Сер. Технические науки. Ростов н/Д, 2006. № 4. С. 18-23.

11. Бутакова М.А., Чернов A.B. Модель пакетного маршрутизирующего коммутатора в корпоративной телекоммуникационной сети // XIV межд. конф. «Математика, Экономика. Образование». Тез. докл. Ростов н/Д, Изд-во РГУ, 2006. С. 51-52.

12. Виллемс Я. От временного ряда к линейной системе // Теория систем. Математические методы и моделирование. М.: Мир. 1989. С. 10 - 191.

13. Владимиров Д. А. Булевы алгебры. М.: Наука, 1969.

14. Гнеденко Б. В. Курс теории вероятностей. М.: Наука, 1969. 399 с.

15. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука, Физматлит, 2000.

16. Горелик А. Л., Скрипкин В. А. Построение систем распознавания. М.: Советское радио, 1974. 222 с.

17. Граф ÜI., Гесселъ М. Схемы поиска неисправностей / пер. с нем. -М.: Энергоатомиздат, 1989. 144 с.

18. Гретцер Г. Общая теория решеток: пер. с англ.: под ред. Д. М. Смирнова. -М.: Мир, 1981.

19. Дружинин Г. В. Надежность автоматизированных систем. Изд. 3-е, перераб. и доп. М.: Энергия, 1977. 536 с.

20. Жегалкин И. И. Арифметизация символической логики // Математический сборник. 1928. Т. 35. С. 311 377.

21. Жегалкин И. И. О технике вычисления предложений в символической логике // Математический сборник. 1927. Т. 34. С. 9 28.

22. Избранные вопросы теории булевых функций / под ред. С. Ф. Винокурова, Н. А. Перязева- М.: Физматлит, 2001.

23. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. Изд. 2-е. М.: Едиториал УРСС, 2004. 400 с.

24. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений. Пер. с англ. К.: Издательство «ДиаСофт», 2001.

25. Коваленко А. Е., Гула В. В. Отказоустойчивые микропроцессорные системы.-Киев: Технша, 1986.

26. Колчин В. Ф. Случайные графы. М.: Физматлит, 2004.

27. Котляров В.П., Коликова Т.В. Основы тестирования программного обеспечения. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006.

28. Крылов В. В., Самохвалова С. С. Теория телетрафика и ее приложения. СПб.: БВХ-Петербург, 2005.

29. Кусраев А. Г., Кутателадзе С. С. Булевозначный анализ. Новосибирск: Изд-во ин-та математики, 1999.41 .Ледли Р. Программирование и использование вычислительных машин. М.: Мир, 1966. 642 с.

30. Лидл Р., Нидерайтер Г. Конечные поля. Т. 1. Т. 2. М.: Мир, 1988.818 с.43 .JIunaee В. В. Качество программного обеспечения. М.: СИНТЕГ,

31. JIunaee В.В. Надежность программного обеспечения АСУ. М.: Энергоиздат, 1981.

32. JIunaee В.В. Тестирование программ. М.: Радио и Связь, 1986.

33. Логачев О. А., Сальников А. А.,Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 470 с.

34. Лупанов О. Б. Конспект лекций по курсу «Введение в математическую логику». М.: Изд-во ЦПИ при мех.-мат. факультете МГУ им. М. В. Ломоносова, 2007.

35. Майерс Г. Искусство тестирования программ: Пер. с англ. -М.: Финансы и статистика, 1982.

36. Майерс Г. Надежность программного обеспечения / пер. с англ. -М.: Мир, 1980. 360 с.

37. Майерс Г. Надежность программного обеспечения: Пер. с англ. / Под ред. В.Ш. Кауфмана. М., Мир, 1980.

38. Мойсил Гр. К. Алгебраическая теория дискретных автоматических устройств. М.: Изд-во иностранной литературы, 1963. 680 с.

39. Немолочнов О.Ф. Методы технической диагностики. Л., 1978.

40. Нейман В. И. Системы и сети передачи данных на железнодорожном транспорте: учебник для вузов ж.-д. транспорта. М.: Маршрут, 2005.

41. Перязев Н. А. Основы теории булевых функций. М.: Физматлит,

42. Поспелов Д. А. Логические методы анализа и синтеза схем. Изд. 3-е, перераб. и доп. М.: Энергия, 1974. 368 с.

43. Сабинин О. Ю., Зверев В. В. Символьное имитационное моделирование технических систем // Приборы и системы управления. 1997. № 3. С. 24-36.

44. Сапожников В. В., Сапожников Вл. В. Основы технической диагностики: учеб. пособие для студентов вузов ж.-д. транспорта. — М.: Маршрут, 2004.318 с.

45. Сапожников В. В., Сапожников Вл. В., Валиев Р. Ш. Синтез самодвойственных дискретных систем. СПб.: Элмор, 2006. 224 с.

46. Сафарбаков А. М., Лукьянов А. В., Пахомов С. В. Основы технической диагностики: учеб. пособие. Иркутск: изд-во Иркутского государственного университета путей сообщения, 2006. 217 с.

47. Сикорский Р. Булевы алгебры. М.: Мир, 1969.

48. Тамре Л. Введение в тестирование программного обеспечения. Пер. с англ. М.: Издательский дом «Вильяме», 2003.

49. Тейер Т., Липов М., Нельсон Э. Надежность программного обеспечения. Анализ крупномасштабных разработок / пер. с англ. М.: Мир, 1981. 323 с.

50. Тейер Т., Липов М., Нельсон Э. Надежность программного обеспечения. Пер. с англ. М.: Мир, 1981.

51. Тожич Ж. Арифметическое представление логических функций // Доклады АН СССР.-М.: 1970. С. 131 136.

52. Ульяницкий Е. М, Чернов А. В., Хошафян О. С. О свойствах архитектуры распределенных вычислительных систем на железнодорожном транспорте // Вестник Ростовского государственного университета путей сообщения. -Ростов н/Д, 2000. № 2. С. 104 107.

53. Ульяницкий Е.М, Чернов A.B. Использование масштабирующего усилителя в регистраторах параметров аварийного режима воздушной линии электропередачи // Известия высших учебных заведений. Электромеханика, 1997, № 1-2. С. 74-75.

54. Ульяницкий Е.М., Чернов A.B. Способ повышения точности регистратора параметров аварийного режима воздушной линии электропередачи // Известия высших учебных заведений. Электромеханика, 1997, № 1-2. С. 114-117.

55. Уонем М. Линейные многомерные системы управления. М.: Наука, 1980. 375 с.

56. Ушаков И. А. и др. Надежность технических систем: справочник под ред. И. А. Ушакова. М.: Радио и связь, 1985. 606 с.

57. Цыпкин Я. 3. Адаптация и обучение в автоматических системах. -М.: Наука, 1968.399 с.

58. Цыпкин Я. 3. Основы теории обучающих систем. М.: Наука, 1970.251 с.

59. Чернов А. В. К вопросу о разработке математических моделей ре-факторинга программного обеспечения // Обозрение прикладной и промышленной математики. 2007. Т. 14. Вып. 2. С. 368 369.

60. Чернов А. В. Методы линеаризации и модели контролируемых нелинейных дискретных динамических систем // Научно-технические ведомости СПбГПУ. СПб.: Изд-во политехнического университета. 2009. № 2. С. 156- 162.

61. Чернов А. В. О задаче онлайновой диагностики и синтеза контролируемых информационных систем // Мат. юбилейной Междунар. науч.-практ. конф. «Строительство-2009». Ростов н/Д, РГСУ, 2009. С. 167 - 169.

62. Чернов А. В. Об актуальности развития новых направлений в математической теории надежности информационных сетей с пакетной передачей данных // Обозрение прикладной и промышленной математики. 2008. Т. 15. Вып. 1.С. 184- 185.

63. Чернов А. В. Синтез интеллектуальных самотестируемых устройств для систем управления электроэнергетическими объектами // Известия высших учебных заведений. Электромеханика. 2009. № 2. С. 65 68.

64. Чернов А. В. Учет свойства безопасности функционирования программного обеспечения информационно-управляющих транспортных систем // Известия вузов, Северо-Кавказский регион. Технические науки. Ростов н/Д, 2001. №3. С. 17-20.

65. Чернов А. В. Формализация критериев технологической безопасности информационных систем на транспорте // Обозрение прикладной и промышленной математики. 2001. Т. 8. Вып. 2. С. 721 722.

66. Чернов А. В. Частично определенные булевы функции с логическими производными в моделях технической диагностики дискретных систем //

67. Известия вузов. Северо-Кавказский регион. Технические науки. Ростов н/Д. 2008. №5. С. 8- И.

68. Чернов А. В., Рассказов Д. А. Алгоритмическое и программное обеспечение символьных вычислений для логического дифференциального и интегрального исчисления // Программные продукты и системы. 2008. №2. С. 93-96.

69. Чернов A.B. Алгоритм синтеза контрольного уравнения для линейной динамической системы над конечным полем // Обозрение прикладной и промышленной математики. -М., т. 15, вып. 6, 2008. С. 999- 1002.

70. Чернов A.B. Байесовская модель информационной сети на транспорте с учетом дестабилизирующих факторов // Новые технологии управления движением технических объектов. Ростов-н/Д: Изд-во СКНЦ ВШ, 2002. Вып. 3, ч. 2. С. 38 - 40.

71. Чернов A.B. Байесовский подход в обеспечении информационной безопасности корпоративных компьютерных сетей // X межд. конф. «Математика. Экономика. Образование». Тез. докл. Ростов н/Д, 2002. С. 242 -243.

72. Чернов A.B. Модели анализа и диагностики формальных спецификаций программного обеспечения информационно-управляющих систем //

73. Вопросы современной науки и практики. Университет им. В.И.Вернадского, Серия «Технические науки», т.2, № 4(14), 2008. С. 147 153.

74. Черное A.B. Модели и методы дискретного анализа и синтеза в задачах технической диагностики информационных систем. Ростов-на-Дону, Издательство Южного федерального университета, 2009. 170 с.

75. Чернов A.B. О применении современных методов кодирования информации в автоматизированных системах управления на транспорте // Обозрение прикладной и промышленной математики. М., т.9, вып. 2, 2002. С. 484-485.

76. Чернов A.B. Применение байесовского статистического вывода для идентификации угроз безопасности рабочих мест в корпоративной сети // Обозрение прикладной и промышленной математики. М., т. 9, вып. 1, 2002. С. 264.

77. Чернов A.B. Применение моделей случайных графов и бинарных диаграмм решений к задачам анализа надежности информационных сетей // Обозрение прикладной и промышленной математики. М., т. 15, вып. 2, 2008. С. 376-377.

78. Чернов A.B. Синтез контрольного уравнения для линейной динамической системы // Обозрение прикладной и промышленной математики. М., т. 15, вып. 5. 2008. С. 945.

79. Чернов A.B. Совершенствование средств защиты автоматизированных рабочих мест в корпоративной сети СКЖД // Труды 2 научной конференции «Безопасность информационных технологий». Таганрог, 2002. С. 26-29.

80. Чернов A.B. Сравнительный анализ показателей качества современных операционных систем // Материалы 58 научной конф. проф.-преп. состава РГУПС, 20-22 апреля 1999, РГУПС, Ростов н/Д, 1999. С. 32.

81. Чернов A.B., Иванов С. О. Об адаптивной методике количественной оценки защищенности автоматизированных банковских систем // Обозрение прикладной и промышленной математики. М., т. 10, вып. 2, 2003. С. 139.

82. Шубинский И. Б. и др. Активная защита от отказов управляющих модульных вычислительных систем. СПб.: Наука, 1993. 142 с.

83. Янушкевич С., Бохманн Д., Станкович Р., Тожич Ж., Шмерко В. Логическое дифференциальное исчисление: достижения, тенденции и приложения // Автоматика и телемеханика. 2000. № 6. С. 155 170.

84. Abramovici M. M., Breuer A., Friedman A. Digital Systems Testing and Testable Design, Wiley-IEEE Press, New York, 1994.

85. Akers S. B. On a theory of Boolean functions // J. Society for Industrial and Applied Mathematics. 1959. V. 7. № 4. P. 487 498.

86. Amman P. Offut J. Introduction to Software Testing. Cambridge University Press, 2008.

87. Barabasi A. L., Reka A. Emergence of scaling in Random networks // Science, v. 286, october, 1999. P. 509 512.

88. Bartee T. C., SchneiderD. I. Computation with Finite Fields // Inform, and Contr., v. 6, 1963. P. 79 98.

89. Benjauthrit B., Reed I. S. Galois Switching Functions and the Applications // IEEE Trans. Comput., v. C-25, 1976. P. 78 86.

90. Benjauthrit B., Reed I. S. On the Fundamental Structure of Galois Switching Functions // IEEE Trans. Comput., v. C-27, № 8, 1978. P. 757 762.

91. Berdard J. F, Jaswa V. C. Self-Checking Digital Fault Detector for Modular Redundant Real Time Oclock. US PS 4683570, G06F 11/18, 1987.

92. Boole G. The Laws of Thought. -London: Macmillan, 1854.

93. Boros E., Ibaraki T., Makino K. Error-free and best-fit extensions of partially defined Boolean functions I I Information and Computation. V. 140, 1998. P. 254-283.

94. Bryant R. E. Symbolic Simulation-Techniques and Applications // 27th Design Automation Conference. №6, 1990. P. 517 521.

95. Butzer P. L., Stankovic R. S., Eds. Theory and Applications of Gibbs Derivatives. Mathematical Institute, Belgrade, 1990.

96. Chen J., Patton R. J. Robust model-based fault diagnosis for dynamic systems. Kluwer Academic Publishers, January 1, 1999.

97. Clark R. N. A simplified instrument detection scheme // IEEE Trans. Aerospace Electron. Syst., v. 14, 1978. P. 456 465, 558 - 563.

98. Davio M. J., Deschamps P., Thayse A. Discrete and Switching Functions. McGraw-Hill, New York, 1978.

99. Feldmann A, Gilbert A. C., Willindger W. Data Networks as Cascades: Investigating the Multifractal Nature of Internet WAN Traffic. ACM Computer Communication Review, v. 28, September, 1998. P. 42-55.

100. Figueiredo D. R. et al. On TCP and self-similar traffic // Performance Evaluation, 2005, v. 61, № 2 3. P. 129 - 141.

101. Frank P. M. Fault diagnosis in dynamic systems using analytical and knowledge-based redundancy // Automatica, v. 26, 1990. P. 459 474.

102. Fujiwara H. Logic Testing and Design for Testability. MIT Press,1985.

103. Gertler J. Fault detection and diagnosis in engineering systems. Marcel Dekker, New York, 1998.

104. Gibbs J. E., Millard M. S. Walsh functions as solutions of a logical differential equation. DES Report № 1 National Physical Laboratory Middlesex, England, 1969.

105. Goodenough J. B., Gerhart S. L. Toward a Theory of Test Data Selection. IEEE Transactions on Software Engineering, №6, 1975. P. 26 37.

106. Hellwagner H. Fault Detection Method in Partially Utilized Cellular (Systolic) Arrays. Proc. Parcella 86, Mathematical Research 29, Berlin, AkademieVerlag, 1986. P. 138- 146.

107. Himelblay D. M. Fault detection and diagnosis in chemical and petro-chemmical processes. Elsevier, Amsterdam, 1978.

108. Horwarth J. Checking Sequential Logic Circuits. UP PS 4556976, G06F 11/00, 1985.

109. Hurst H. E. Long-term storage capacity of reservoirs // Trans. Amer. Soc. Of Civil Engineers, № 116, 1951. P. 770 799.

110. Isermann R. Fault-Diagnostics System: An introduction from fault detection to fault Tolerance. Springer-Verlag. Berlin, 2006.

111. Isermann R. Supervision, fault-detection and fault-diagnosis methods. An introduction. Control Eng. Practice, v. 5, №. 5, 1997. P. 639 652.

112. Jacky J., Veanes M., Campbell C., Schute W. Model-Based software Testing and Analysis with C#. Cambridge University Press, 2007.

113. Jaha S., Patel J. H. Error Correction in Arithmetic Operations Using Time Redundancy. 13 Int. Symp. Fault Tolerant Comp., Milano, 1983. P. 198 — 305.

114. Jakson D. K. Method and Circuit for Checking Integrated Circuit Chips. US PS 4176258, GOIR 31/28, 1975.

115. Jennings G. Symbolic incompletely specified functions for correct evaluation in the presents of indeterminate input values // HICSS IEEE. V. 1, 1995.1. P. 23-31.

116. Kalman R. E. Algebraic Structure of Linear Dynamical Systems I. The Module of Z // Proc. Nat. Acad. Sci. (USA). V. 54, 1965. P. 1503 1508.

117. Kalman R. E. Mathematical Description of Linear Dynamical Systems // SIAM Journal on Control. V. 1(2), 1963. P. 152 192.

118. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design. OBDD Foundations and Applications. - Berlin: Springer-Verlag, Heidelberg, New York, 1998. 280 p.

119. Menger K. S. Jr. A Transform for Logic Networks // IEEE Trans. Comput., v. C-18, 1969. P. 241 -250.

120. Minero R. H., Anello A. J., Furey R. G„ Palounek L. R. Checking by pseudodublication. US PS 3660646, G06F, 11/00, 1972.

121. Muller D. E. Application of Boolean algebra to switching circuits design and to error detection // IRE Trans. Electron. Comp. Vol. EC-3, 1954. P. 6 -12.

122. Ninomia I. A Study of the Structures of Boolean Function and its Application to Synthesis of Switching Circuits // Memoirs. Fac. Engg. Nagoya Univ., v. 13, 1961. P. 149-363.

123. Ninomia I. Theory of Coordinate Representation of Swichin Functions //Memoirs. Fac. Engg., v. 10, 1958. P. 175 190.

124. Park K., Willinger W. Self-similar network traffic and performance evaluation. Wiley-Interscience, 2000.

125. Patel J. H., Fung L. Y Concurrent Error Detection in ALU's by Recomputing with Shifted Operands. IEEE Trans. Comp. C-31, 1982. P. 589 595.

126. Patel J. H., Fung L. Y. Concurrent Error Detection in Multiply and Divide Arrays. IEEE Trans. Comp. S-32, 1983. P. 417 422.

127. Patton R. J., Frank P. M., Clark R. (Eds.) Issues of Fault Diagnosis for Dynamical Systems. Springer-Verlag, London, 1999.

128. Pau L. Failure diagnosis and performance monitoring. Marcel Dekk-ers, New York, 1981.

129. Posthojf C., Steinbach B. Logic Functions and Equations. Binary Models for Computer Science. Springer, 2003. 392 p.

130. Pradhan D. K. A Theory of Galois Switching Function // IEEE Trans. Comput., v. C-27, 1978. P. 239 248.

131. Reddy S. M. Easily Testable Realizations for Logic Functions // IEEE Trans. Computers. V. 21, no. 11, Nov., 1972. P. 183 188.

132. Reddy S. M. Easily Testable Realizations for Logic Functions // IEEE Trans. Computers, v. 21, no. 11. P. 183 188, Nov. 1972.

133. Reed S. M. A class of multiple error correcting codes and their decoding scheme // IRE Trans. Inf. Th. V. PGIT-4, 1954. P. 38 49.

134. Reinert D. Entwurf und Diagnose komplexer digitaler Systeme. Berline, VEB, Verlag Tecnik, 1983.

135. Roth J. P. Computer Locic, Testing and Verification. Computer Science Press, 1980. 426 p.

136. Roth J. P., Bouricius W. G., Schneider P.R. Programmed algorithms to compute tests to detect and distinguish between failures in logic circuits // IEEE Trans. On Electronic Computers. V. EC-16, № 7, 1967. P. 676 683.

137. Rudeamt S. Lattice Functions and Equations. Springer, 2001. 435 p.

138. Sasao T. Easily Testable Realizations for Generalized Reed-Muller Expressions // IEEE Transactions on Computers. V. 46, no. 6, June 1997. P. 709 -716.

139. Sasao T. Switching Theory for Logic Synthesis. Kluwer Academic Publishers, Boston, MA, USA, 1999.

140. Sellers F. P., Hsiao M. Y., Bearson L. W. Analyzing errors with the Boolean difference // IEEE Transactions on Computers, 1, 1968. P. 676 683.

141. Shooman M. L. Reliability of Computer Systems and Networks. -New York: John Wiley & Sons, 2002.

142. Siewiorek D. P., Scliwarz R. S. The Theory and Practice of Reliable System Design. Bedford, Digital Press, 1982.

143. Simani S., Fantuzzi C., Patton R. J. Model-based fault diagnosis in dynamic systems using identification techniques. Springer-Verlag, January 17, 2003.

144. Spivey J. M. The Z notation: Reference manual. Prentice Hall International, 1992. 168 p.

145. Stankovic R. Fast algorithm for calculation of Gibbs derivative on finite group. Approximation Theory and its Applications, 7(2), 1991. P. 1-19.

146. Steinbach B., Posthoff C. Logic Functions and Equations. Examples and Exercises. Springer, 2009. 234 p.

147. Stone M. H. The theory of representation for Boolean algebras. Trans. AMS. V. 40, 1936. P. 37-111.

148. Takahashi I. Switching Function Constructed by Galois Extension Fields // Inform. Contr., v. 48, № 2, 1981. P. 95 108.

149. Thayse A., DavioM. Boolean differential calculus and its application to switching theory // IEEE Transactions on Computers, 22, 1973. P. 409 420.

150. Tucker J. H. Tapia M. A. Bennett A. W. Boolean Integral Calculus for Digital Systems // IEEE Trans. On Comp., v. 34, issue 1, Jan. 1985. P. 78 81.

151. Xie M, Dai Y S., Poh K. L. Computing Systems Reliability. Models and Analysis. New York: Kluwer Academic Publishers, 2004.

152. Yanushkevich S. N. Logic Differential Caluclus in Multi-Valued Logic Design. Technical University of Szczecin Academic Publishers, Poland, 1998.