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



вах рукописи

1/

Максимов Алексей Алексеевич

МЕТОДЫ АНАЛИЗА И СИНТЕЗА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ НЕЧЕТКИХ ДИСКРЕТНЫХ СИСТЕМ

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

Автореферат

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

Саратов - 2008

003462641

Работа выполнена в ГОУ ВПО «Саратовский государственный социально-экономический университет» и ГОУ ВПО «Саратовский государственный технический университет»

Научный руководитель: Заслуженный деятель науки

Российской Федерации, лауреат премии Президента РФ, доктор технических наук, профессор Сытник Александр Александрович

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

Глазков Виктор Петрович

кандидат физико-математических наук, доцент Богомолов Сергей Анатольевич

Ведущая организация: Институт проблем точной механики

и управления Российской Академии Наук (г. Саратов)

Защита диссертации состоится января 2009 г. в /3 часов на

заседании диссертационного совета Д 212.242.08 при ГОУ ВПО «Саратовский государственный технический университет» (410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319).

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет».

Автореферат разослан "<$>' декабря 2008 г.

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

диссертационного совета ит-^—■А. Терентьев

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

Актуальность темы. Развитие науки и техники ведет к всё большему усложнению, как объектов исследования, так и систем, их моделирующих.

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

Задачи анализа, синтеза, а также задачи, связанные с исследованием функционального поведения автоматов, нашли отражение в работах Айзермана, Гилла, Трахтенброта, Минского, Шеннона, Джона фон Неймана, Яблонского, Богомолова, Сытника, Твердохлебова и многих других.

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

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

Впервые модели такого рода ввел в обиход Лотфи Заде. Несколько позже Бартоломеем Коско было показано, что любая математическая система может быть аппроксимирована некоторой нечеткой моделью. Ви и Фу предложили конструкцию нечеткой автоматной модели, являющейся обобщением конструкции детерминированных автоматов, в которой неопределенность выражалась в том, что изменения состояний определялись не однозначно, а также имели некоторую оценку, например из отрезка [0,1]. Данная модель активно использовалась различными авторами для описания поведения систем с неоднозначно определенными состояниями.

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

Нечеткие матрицы и нечеткие графы являются одними из средств для описания нечетких автоматов. Функция переходов для каждого входного сигнала нечеткого автомата представляется нечеткой матрицей (нечетким графом). Итерации входного сигнала соответствует возведение данной матрицы в степень. В связи с этим, при решении достаточно большого числа задач на нечетких автоматах, исследуют степени нечетких матриц. Так как общий состав элементов нечеткой матрицы при возведении её в степень не расширяется, то для каждой такой матрицы А определены натуральные числа к и т (к<т) такие, что Ак=Ат. Числа Ш(А) = к-1 и р(А)~т—к, где кит- наименьшие из натуральных чисел, для которых

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

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

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

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

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

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

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

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

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

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

Научная новизна диссертации заключается в следующем:

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

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

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

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

их и (индекс и-вершинного нечеткого графа) не превышает (я-])2; данная

оценка лучше оценки, полученной ранее Ли;

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

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

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

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

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

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

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

На защиту выносятся:

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

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

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

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

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

- решение задач по нахождению индексов и периодов некоторых видов графов (неориентированных, бесконтурных, функциональных и др.);

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

- программный комплекс для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов).

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на XIV и XV Международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов» (г. Москва, МГУ, 2007, 2008 гг.); Международной научной конференции «Компьютерные науки и информационные технологии» (г. Саратов, СГУ, 2007 г.); VIII Всероссийской научно-технической конференции (г. Улан-Удэ, ВСГТУ, 2007 г.); Ежегодных конференциях по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета «Социально-экономическое развитие России: Проблемы, поиски, решения» (Саратов, 2007, 2008 гг.).

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

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

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

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

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

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

Нечетким автоматом (или нечетким полуавтоматом) называется тройка A = (S,X,5), где S и Х- непустые конечные множества (множество состояний и множество входных сигналов), a S:SxX-*M(S)-отображение, нечеткая функция переходов (через М (S) обозначена совокупность всех нечетких подмножеств множества S).

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

Подмножество S* множества S называется устойчивым в нечетком автомате А = (5,X,S), если (V/ е S')(Vxe X)(suppd(s',x) cS'), где supp -носитель нечеткого вектора, supp// = {s е 51 ju(s) > 0}.

Нечеткий автомат A' =(S',Х,8') называется подавтоматом нечеткого автомата A = (S,X,S), если S" - устойчивое подмножество множества состояний нечеткого автомата А, a S' - S | . - сужение функции

переходов на множестве S'. Совокупность всех подавтоматов нечеткого автомата À обозначают Sub А .

Пусть A = (S,X,âl) и В - (T,X,S2) - два нечетких автомата с одним и тем же входным алфавитом (сравнимые автоматы), тогда гомоморфизмом нечеткого автомата А в нечеткий автомат В называется отображение tp:S ->Т такое, что (Vs е S)(Vx е = ¿2(<p(s),x)).

Теорема 2.1.1 Пусть <р - гомоморфизм нечеткого автомата A = (S,X,5) в нечеткий автомат В = (Г, Х,5). Тогда:

1) если А' = (S', X,S) с SubA, то В' = (^(S* ), X,8) е SubB ;

2) если В' =(Т',Х,ô)e SubB, то А' =(<р'\Т'),Х,6)е SubA .

Теорема 2.1.2 Совокупность Sub А всех подавтоматов нечеткого

автомата А вместе с пустым подавтоматом образует решетку.

Пусть в - отношение эквивалентности на множестве 5, а р и v - два

нечетких вектора над S. Тогда (p,v)e& (т.е. р и v находятся в отношении эквивалентности в) тогда и только тогда, когда max p{t) - max v{t), VseS .

1ев<Х> 1€в<1>

Отношение эквивалентности в çz SxS называется конгруэнцией нечеткого автомата A =(S,X,S), если (i,,s2) е в => (S(si,x),S(s2,x)) еО для любых s,,Sj€S, х&Х .

Пусть в - конгруэнция нечеткого автомата A = (S,X,S). Фактор-автоматом нечеткого автомата А по конгруэнции в называется нечеткий автомат = , где S-.S/^xX есть перенесение S на

фактор-множество ^ : по определению 6(0 < s >,х) = 9 < ô(s,x) > для любых seS,xeX.

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

Теорема 2.1.6 Множество всех конгруэнции нечеткого автомата образует полную решетку.

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

Теорема 2.1.7 Пусть р- некоторое отношение эквивалентности на

множестве состояний нечеткого автомата А, " семейство

отношений, определенных следующим образом: Л =Р.

шах ¿(.г,*)(/')= тах <5(5',*)(/'),У/ еЯУхе X); рм

Рк = А-

наибольшая конгруэнция, содержащаяся в отношении эквивалентности р. Тогда, если (ЗА е ¿V) (рк = ри1), то рк = рм .

Теорема 2.1.7 предлагает способ построения наибольшей конгруэнции нечеткого автомата, содержащейся в некотором отношении эквивалентности на множестве его состояний.

Нечетким автоматом с функцией выхода называется пятерка А = (Б,Х,У,3,а), где 5, X и У - непустые конечные множества (множества состояний, входных и выходных сигналов соответственно), отображения 8: 5х X -> М(5) и а: 5х X -> М(У) - нечеткие функции переходов и выходов соответственно, а также выполняется следующее условие:

(V* 6 е Х)(((3/ е > 0))о(0у е У)(ф,х){у) > 0))).

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

Теорема 2.2.7. Пусть р - некоторое отношение эквивалентности на

множестве состояний нечеткого автомата А, {а)Г-1 " семейство отношений, определенных следующим образом:

/О, = ') 6 /?|io(s,x) = w{s',x), Vxe x} ,

Pk =

(s,s')e pt_t

max S(s,x)(t') = max S(s',x)(t'),Vt e S,\/x e Л'}, pM

' «А-1 «»

наибольшая конгруэнция, содержащаяся в отношении эквивалентности р. Тогда, если (ЗА: е /V) (/?4 = р4+1), то рк-рм.

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

выхода, со сложностью О

ffn\ \

,т(п+1) 12,'

, где п~ число состоянии нечеткого

автомата, т - число его входных сигналов, а /- число его выходных сигналов.

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

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

Одними из наиболее важных характеристик нечетких матриц являются значения их индекса и периода. Ранее было обнаружено (Томасон), что степени нечетких матриц либо сходятся, либо обладают конечным периодом. То есть, для каждой нечеткой матрицы А определены натуральные числа к и т (к < т) такие, что Ак = А" . Числа ind(A) = к-\ и р{А) = т~к, где к и т - наименьшие из натуральных чисел, для которых выполняется равенство Ак = Ат, называют соответственно индексом и периодом нечеткой матрицы.

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

• сервера баз данных (использовался MS SQL Server),

• диспетчера заданий,

• клиентских частей.

Общая схема взаимодействия модулей программного комплекса

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

В таблице представлены результаты вычислительного эксперимента по подсчету индексов и периодов нечетких матриц с числом порогов, равным двум размерности 4x4. Из таблицы видно, что для данных матриц индексы 6 и 7 остаются нереализованными, хотя значения 8> и 9 для индекса допустимы.

Индексы и периоды всех нечетких матриц размерности 4x4, число порогов 2

-^Период Индекс 1 2 3 4 Всего с фиксированным индексом

0 2360 1042 156 6 3564

1 25096 2616 48 0 27760

2 24036 480 48 0 24564

3 7164 72 0 0 7236

4 2004 0 0 0 2004

5 360 0 0 0 360

6 0 0 0 0 0

7 0 0 0 0 0

8 24 0 0 0 24

9 24 0 0 0 24

Всего с фиксированным периодом 61068 4210 252 6 Всего: 65536

Данное наблюдение верно также и для матриц размерности 5x5 и 6x6, для обсчета которых было задействовано 10 клиентских компьютеров. Обсчет двоичных булевых матриц размерности 6x6 занял около семи часов.

В работе также решаются задачи нахождения индексов и периодов некоторых видов графов (неориентированные, ориентированные, нечеткие). Направленным (или ориентированным) нечетким графом называется пара

(7 = (У,а), где V - конечное непустое множество (вершины графа), а а -нечеткое отношение на множестве V . Пара (и,у) называется дугой графа (или ориентированным ребром) с началом и и концом у; <5(и,у) - значение функции принадлежности для ребра (м,у) (вес ребра). Причем вершины являются инцидентными в том и только в том случае, если ¿(и,у) > 0. Отношения а называют нечетким отношением смежности, а соответствующую ему нечеткую матрицу А (а) - нечеткой матрицей

смежности графа (7.

Говоря об индексе и периоде графа С (нечеткого графа (5), будем иметь в виду индекс и период его матрицы смежности (нечеткой матрицы смежности) и писать /иг/(С) и р{С) (тс1(С) и р{0)) соответственно. Центральное место в данном параграфе занимает следующая теорема. Теорема 3.3.3 Для любой нечеткой матрицы А размерности их и

справедлива следующая оценка 1пс1 (Л) < (л -1)2.

Данная оценка лучше оценки, полученной ранее Ли. Графы Сг, = ,сс,) и 0'2 = (У},а2) называются изоморфными, если существует биекция <р:\\ -о- У2, сохраняющая отношение смежности: («, у) е а, о (ср(и),<р(у)) е аг для любых и, у е V,.

Нечеткая матрица А называется подобной нечеткой матрице В, если существует перестановочная (т.е. имеющая в каждой строке и в каждом столбце точно одну единицу) двоичная булева матрица Ф такая, что В = Ф'АФ. Так как Ф1 Ф = ФФ' = Е (тождественная матрица), то А = ФВФ' = (Ф7)' ВФ\ т.е. В подобна А . Для подобных матриц доказана справедливость следующей теоремы.

Теорема 3.3.5 Подобные нечеткие матрицы имеют равные индексы и равные периоды.

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

Теорема 3.3.9 Пусть С = (У,а) сильносвязный п- вершинный орграф, тогда его период р< п.

Теорема 3.3.10 Неориентированный граф имеет период, равный I или 2.

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

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

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

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

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

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

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

Формализация изложенной ситуации позволяет получить нечеткий автомат с двумя входными сигналами и, например, десятью состояниями: А = (8,Х,ё), где 5 ={$,,я2,...,510}, X = ,х2} и функция переходов 8 задана следующими нечеткими матрицами перехода:

'0.5 0.1 0.4 1 0 0.1 0.5 0.7 0.7 О.П

0.1 0.5 0.4 0 0.1 1 0.4 0.7 0.1 0.7

0.5 0.5 0.4 1 1 1 1 0.7 0.7 0.7

0.3 0.2 0.3 1 0.7 0.2 0.8 1 0.5 1

0.2 0.3 0.3 0.3 1 0.2 0 1 0 1

0.3 0.3 0.3 0 0 1 0.5 1 1 0.6

0.3 0 0.3 0.7 0.6 1 0.4 1 1 0.5

0.4 0.4 0.4 0.8 0.8 0.8 0.8 0.9 0.9 0.9

0 0.4 0.4 0.3 0.4 0.5 0.8 0.9 0.2 0.3

,0.4 0.0 0.4 0.6 0.4 0.5 0.8 0.9 0.3 0-1,

'0.3 0.3 0.3 0.6 0.7 0.1 0.5 0.8 0.7 0.8Ч

0.2 0.3 .0.3 0 0.1 0.7 0.4 0.8 0.8 0.7

0.2 0.2 0.3 0.7 0.7 0.7 0.7 0.8 0.8 0.8

0.3 0.4 0.4 1 0.7 0.2 0.5 1 1 0.7

0.4 0.3 0.4 0.3 0.2 1 0.4 1 0.3 1

0.4 0.3 0.4 0 0.1 1 0.6 1 1 06

0.4 0 0.4 0.7 0.6 1 0.4 1 0.7 1

0.5 0.5 0.5 0.6 0.6 0.6 0.6 0.7 0.7 0.7

0.4 0.2 0.5 0.6 0.4 0.5 0.6 0.7 0.4 0.3

,0-4 0.4 0.5 0.6 0.4 0.5 0.6 0.7 0.4 0.1^

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

03 — {{^1 } '{^4 '} > {^И'^'^ю}} >

Каждой конгруэнции соответствует некоторая модель нечеткого автомата. Состояния данной модели являются обобщениями состояний исходного нечеткого автомата.

Выбирая, например, вг и строя по ней модель исходного автомата, получим автомат с тремя состояниями, которые можно интерпретировать как «хорошее», «удовлетворительное» и «критическое». Полученная модель будет иметь вид: А' где 5* = , ЛГ = {дг,,дг2} и функция

переходов 6 задана следующими нечеткими матрицами перехода:

м; =

0.7

(0.5 1 0.3 1 1 0.4 0.8 0.9

;м =

0.3 0.7 0.8

0.4 1 1 ,0.5 0.6 0.7,

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

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

Эти задачи решаются следующим образом. Функциональное поведение построенной нечеткой модели будет отражать изменение состояния пациента с течением времени. Поскольку два препарата вводятся последовательно, то их совокупному воздействию будет соответствовать матрица переходов, равная произведению матриц, соответствующих введению первого и второго препаратов, т.е. матрица М = М\М\.

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

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

(0.5 1 1 ' 0.5 1 1

Рассматривая наш пример, М - Л/, Мг =

0.5 0.8 0.8

и выполняется

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

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

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

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

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

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

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

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

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

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

пхп (индекс и — вершинного нечеткого графа) не превышает («-1)"; данная

оценка лучше оценки, полученной ранее Ли;

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

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

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

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

1. Максимов A.A. Исследование сложных информационных систем с использованием универсально-алгебраических конструкций нечетких автоматов /А. А. Максимов // Вестник Саратовского государственного социально-экономического университета. - 2006.- №14(3)- С.126-128.

II. Публикации в других изданиях

2. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов /А. А. Максимов // Молодежь. Образование. Экономика: сб. науч. статей участников конф.: в 4 ч. - Ярославль: РЕМДЕР, 2004. -Ч. 4.-С. 309-314.

3. Максимов A.A. Об индексе и периоде нечеткой матрицы / A.A. Максимов; Сарат. гос. ун-т,- Саратов, 2005. - 11 с. - Библиогр.: 2 назв. - Рус. - Деп. в ВИНИТИ 20.01.05, № 78-В2005.

4. Максимов A.A. Базы данных алгебраических свойств некоторых дискретных объектов/ А. А. Максимов // Теоретические проблемы информатики и её приложений: сб. науч. тр. / под ред. проф. A.A. Сытника. - Саратов: Изд-во Сарат. ун-та, 2006. - Вып.7. - С. 81-86.

5. Максимов A.A. Индексы и периоды нечетких матриц и графов / А. А. Максимов, В. Н. Салий // Теоретические проблемы информатики и её приложений: сб. науч. тр. / под ред. проф. A.A. Сытника. - Саратов: Изд-во Сарат. ун-та, 2006. - Вып.7. - С. 87-95.

6. Максимов A.A. Минимизация сложных информационных систем с использованием универсально-алгебраических конструкций нечетких автоматов /A.A. Максимов // Теоретические и прикладные вопросы современных информационных технологий: Материалы Всерос. науч,-техн. конф. - Улан-Удэ: Изд-во ВСГТУ, 2007. - С.187-191.

7. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов «УАК 1.0» /A.A. Максимов // Компьютерные учебные программы и инновации (Телеграф Отраслевого фонда алгоритмов и программ). - 2007, № 1 (24).

8. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов «УАК 1.0» /A.A. Максимов,- М.: ВНТИЦ, 2007. -№50200700129.

9. Максимов A.A. О некоторых свойствах универсально-алгебраических конструкций для нечетких автоматов с функцией выхода /A.A. Максимов // Компьютерные науки и информационные технологии: тез. докл. Междунар. науч. конф., посвящ. памяти проф. A.M. Богомолова. -Саратов: Изд-во Сарат. ун-та, 2007.- С. 76-77.

10. Максимов A.A. Свойства некоторых универсально-алгебраических конструкций нечетких автоматов /A.A. Максимов // Ломоносов - 2007: материалы XIV Междунар. конф. студентов, аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика» - М.: МГУ, 2007.- С. 53.

11. Максимов A.A. О некоторых свойствах универсально-алгебраических конструкций нечетких автоматов /A.A. Максимов // Социально-экономическое развитие России: Проблемы, поиски, решения: сб. науч. трудов по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета в 2006 году: в 4 ч./ Сарапг. гос. соц.-эконом. ун-т. - Саратов, 2007. Ч. 2. - С. 101-102.

12. Максимов A.A. Об индексах и периодах нечетких матриц и графов / A.A. Максимов // Ломоносов - 2008: материалы XV Междунар. конф. студентов, аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика» - М.: МГУ, 2008,- С. 58.

Максимов Алексей Алексеевич

МЕТОДЫ АНАЛИЗА И СИНТЕЗА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ НЕЧЕТКИХ ДИСКРЕТНЫХ СИСТЕМ

Автореферат

Корректор O.A. Панина

Подписано & печать24.12.08 Формат60х84 1/16

Бум. офсет. Усл. пен. л. ¡,0 Уч -изд. л. !,0

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

Саратовский государственный технический университет

410054, Саратов, 1 (олитсхническая ул., 77 Отпечатано а РИЦСГТУ. 410054, Сгрхтов, Политехническая ул., 77

ВВЕДЕНИЕ.

1. ОСНОВНЫЕ ПОНЯТИЯ.

1.1 Элементы алгебры отношений и упорядоченных множеств.

1.2 Элементы теории решеток.

2. МЕТОДЫ АНАЛИЗА И СИНТЕЗА НЕЧЕТКИХ АВТОМАТОВ.

2.1 Методы анализа и синтеза нечетких автоматов без функции выхода

2.2. Методы анализа и синтеза нечетких автоматов с функцией выхода

3. ИССЛЕДОВАНИЕ ФУНКЦИОНАЛЬНОГО ПОВЕДЕНИЯ

НЕЧЕТКИХ АВТОМАТОВ.

3.1 Постановка задачи и основные определения.

3.2 Индексы и периоды нечетких матриц.

3.3 Индексы и периоды нечетких графов.

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

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

Такое поведение систем часто описывается дискретными моделями, в частности, различными видами автоматов.

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

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

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

Первое направление теории автоматов получило развитие в рамках работ академика Глушкова и его последователей, второе — рассматривал в своих работах Арбиб и ряд других исследователей.

Математической моделью устройства преобразования информации является трехосновная алгебраическая система, называемая автоматом, и представляющая собой алгебру А = (5,X,У,8,со), с тремя основными множествами Б, X, У и двумя бинарными операциями 8:5 х X <5, со-.БхХ^У. При этом, множество £ называется множеством состояний,4 Х- множеством входных сигналов, У- множеством выходных сигналов. Операция 8 - называется функцией переходов автомата и показывает, как входной сигнал х преобразует состояние £ в новое состояние £' = Операция со называется выходной функцией автомата А и указывает значение сигнала на выходе у — в зависимости от состояния автомата и значения входного сигнала х.

В качестве динамических систем наиболее часто изучают, автоматы вида А = (5,Х,8), лишенные функции выхода, так называемые полуавтоматы.

Задачи анализа, синтеза, а также задачи, связанные с исследованием функционального поведения автоматов, нашли отражение в работах Айзермана, Гилла, Трахтенброта, Минского, Шеннона, Джона фон Неймана, Яблонского, Богомолова, Твердохлебова и многих других.

В зависимости от специфики рассматриваемых задач, некоторый объект может моделироваться автоматом, у которого множество состояний и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного пространства, упорядоченного множества и другими), которая сохраняется функциями переходов и выходными функциями этого автомата ([8], [16]). Так, многие известные задачи математического моделирования приводят к понятиям линейных [7], упорядоченных [10], булевозначных [20], вероятностью [6] автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова Л.А.[23], Сытника A.A. [25], Сперанского Д.В., Салия В.Н., Плоткина Б.И. и Филькенштейна М.Я. и многих других. Так или иначе, многочисленные исследования в этих направлениях характеризуются широким спектром использования алгебраических средств, так что автоматы того или иного вида становятся предметом исследований в алгебраической теории автоматов, которая очень тесным образом связана со многими разделами универсальной алгебры.

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

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

Впервые модели такого рода ввел в обиход профессор Лотфи Заде (Lotfi Zadeh), опубликовавший в 1965 году основополагающую работу "Fuzzy Sets" в журнале "Information and Control" [79]. Началом практического использования аппарата нечетких множеств можно считать работу Ви (Wee W.G.) и Фу (Fu K.S.) [78] в которой они предложили модель нечеткого автомата, а так же рассмотрели возможность применения его в качестве модели обучающей системы. Далее в 1975г. Мамдани и Ассилиан [60] из Лондонского колледжа Королевы Мэри (Mamdani and Assilian) построили первый нечеткий контролер для управления простым паровым двигателем. Концепцию первого нечеткого контроллера составляют идеи нечеткого логического вывода и нечеткого алгоритма, изложенные Заде в 1973 году [30]. В 1982 Холмблад и Остергад (Holmblad and Osregaad) разработали первый промышленный нечеткий контроллер [46], который был внедрен в управление процессом обжига цемента на заводе в Дании. Несколько позже Бартоломеем Коско (Bart Kosko) была доказана теорема о нечеткой аппроксимации (Fuzzy Approximation Theorem) [54], согласно которой любая математическая система может быть аппроксимирована системой, основанной на нечеткой логике. Другими словами, с помощью естественноязыковых высказываний-правил "если - то", с последующей их формализацией средствами теории нечетких множеств, можно сколько угодно точно отразить произвольную взаимосвязь "вход-выход" без использования сложного аппарата дифференциального и интегрального исчисления, традиционно применяемого в управлении и идентификации.

В январе 1997 года язык нечеткого управления FCL Fuzzy Control Language внесен в Международный стандарт программируемых контроллеров IEC 1131-7. Системы на нечетких множествах разработаны и успешно внедрены в таких областях, как: медицинская диагностика, техническая диагностика, финансовый менеджмент, управление персоналом, биржевое прогнозирование, распознавание образов, разведка ископаемых, выявление мошенничества, управление компьютерными сетями, управление технологическими процессами, управление транспортом, поиск информации в Интернете, радиосвязь и телевидение.

В и и Фу предложили конструкцию нечеткой автоматной модели, являющейся обобщением конструкции детерминированных автоматов, в которой неопределенность выражалась в том, что изменения состояний определялись не однозначно, а также имели некоторую оценку, например из отрезка [0,1]. Данная модель активно использовалась различными авторами для описания поведения систем с неоднозначно определенными состояниями.

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

Некоторые попытки в данном направлении предприняли Малик, Морденсон и Сен (Malik D.S., Mordeson J.N., Sen M.K), которые в [59] предложили один из возможных вариантов минимизации нечеткого автомата, а в работе [58] предложили способ описания полугруппы преобразований нечеткого автомата, а также соединений нечетких автоматов (это требовалось при решении конкретных технических задач), однако в силу того, что ими не использовался алгебраический аппарат, построения получились избыточно сложными, громоздкими и не универсальными. В силу этого представляется необходимым привнести алгебраические методы в теорию моделей нечетких систем, что позволит использовать методы теории конечных детерминированных автоматов при решении задач синтеза и анализа автоматов нечетких.

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

Нечеткие матрицы является одним из языков для описания дискретных систем, не допускающих точного описания [13, 21]. Примером такой системы, как уже отмечалось выше, является нечеткий автомат. Функция переходов для каждого входного сигнала нечеткого автомата представляется нечеткой матрицей. Итерации входного сигнала соответствует возведение данной матрицы в степень. В связи с этим, при решении достаточно большого числа задач исследуют степени различных вещественнозначных матриц (нечетких как частный случай), исследуют их поведение относительно различных операций сложения и умножения, как, например, тах-гшп умножение [38, 76], максимум-сложения [29, 67] (линейные системы с синхронизацией).

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

Нечеткие матрицы являются обобщением булевых матриц, которые в свою очередь достаточно давно являются объектом исследования различных авторов. В частности, Поплавским В.Б. в [17, 18] исследовалась последовательность определителей степеней булевых матриц. В свою очередь, теория булевых матриц ведет своё начало от теории матриц с неотрицательными элементами, большинство наиболее известных результатов для которых были получены между 1906 и 1912 годами Перроном и Фробениусом.

Благодаря широким областям применения нечеткой логики, нечеткие матрицы, а так же нечеткие графы используются в области нейронных сетей [33, 52], например, в нечетких клеточных нейронных сетях [74, 75], которые разрабатывались и применялись при решении задач связанных с обработкой изображений. Задача нахождения степеней нечеткой матрицы также тесно связана с такими задачами как исследование функционирования нечеткой двунаправленной ассоциативной памяти, нахождение решений нечетких уравнений отношения (см., например, [66, 77, 39]).

Одними из наиболее важных характеристик нечетких матриц являются значения их индекса и периода. Изучением степеней нечетких матриц одним из первых начал заниматься Томасон (ТЬотазоп), который заметил, что степени нечетких матриц, либо сходятся, либо обладают конечным периодом [76]. Однако следует отметить, что данные характеристики свойственны не только матрицам, но также и всем конечным циклическим полугруппам, и для каждой циклической полугруппы определены две характеристики называемые индексом и периодом циклической полугруппы соответственно (см. [11]).

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

Так как общий состав элементов нечеткой матрицы при возведении её в степень не расширяется, циклическая полугруппа, порожденная нечеткой, матрицей, конечна и потому для каждой такой матрицы А определены индекс тс1(А) и период р{А).

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

Ответы на эти вопросы позволят решать задачи управления поведением, задачи синхронизации и диагностирования нечетких автоматов. Некоторые из перечисленных выше задач успешно решались для частных случаев нечетких матриц, таких как булевы матрицы, стохастические матрицы. Так в первую очередь исследовались идемпотенты булевых матриц (матрицы имеющие индекс равный нулю и период равный единице), поскольку их характеризация в алгебраических системах важна как для построения структурной теории таких систем, так и в приложениях (см. [51, 55]). Первая характеризационная теорема об идемпотентах над булевой алгеброй была получена в 1963 году Розенблаттом (Rosenblatt D., см. [65]), им были описаны графы идемпотентных булевых матриц. Далее, Шейным (Schein В., [70]) идемпотентные булевы матрицы были охарактеризованы в терминах квазипорядков. Грегори, Киркленд и Пуллман (Gregory D., Kirkland S., Pullman N.) в [45], установили, что идемпотентная булева матрица может быть редуцирована к некоторой блочной форме одновременной перестановкой строк и столбцов. Из последних результатов в данной области " следует отметить работу [3], в которой Бисли Л.Б., Гутерман А.Э., Канг К.-Т. и Сонг С.-З. получили новую структурную характеризацию идемпотентных т булевых матриц над бинарной булевой алгеброй. Данная характеризация применяется авторами для описания всех булевых матриц мажорирующихся идемпотентами.

Отдельно изучались перестановочные двоичные булевы матрицы. Так независимо друг от друга Ким [49] и Шварц [68] сф ормулировали необходимое условие сходимости последовательности степеней перестановочных двоичных булевых матриц. В 1997-1999 годах независимо друг от друга Аткин (Atkin A.O.L) [28] и Мартин Гавалек (Gavalec М.) [41] вывели оценку периода для перестановочных нечетких матриц.

Так же особый интерес представляют собой оценки сверху значений индекса и периода нечеткой матрицы общего вида. Шварц в своей работе [69] показал, что индекс двоичной булевой матрицы размерности п не может превосходить (я-l)2, аналогичную оценку получил Розенблатт в [64]. Ли в работе [57] показал, что период нечеткой матрицы размерности п делит [nj, где \п\- наименьшее общее кратное чисел 1,2,.п. В [56] Ли (1л .1.Х.) показал, что для индекса нечеткой матрицы справедлива оценка 1пс}^А)<{п-\)\п\. Гавалек в [42] показал, что задача вычисления периода нечеткой матрицы является КР-полной.

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

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

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

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

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

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

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

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

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

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

- получены оценки для индексов и периодов нечетких графов определенных типов; решены задачи нахождения индексов и периодов некоторых видов графов (неориентированные, бесконтурные, функциональные и др.); показано, что индекс нечеткой матрицы размерности пхп (индекс п — вершинного нечеткого графа) не превышает [п-1)2; данная оценка лучше оценки, полученной ранее Ли [56];

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

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

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

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

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

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

На защиту выносятся:

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

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

-множество подавтоматов и множество конгруэнций нечеткого полуавтомата и собственно нечеткого автомата являются решетками;

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

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

-решение задач по нахождению индексов и периодов некоторых видов графов (неориентированных, бесконтурных, функциональных и др.);

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

-программный комплекс для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов).

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на XIV и XV Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» (МГУ, г. Москва, 2007, 2008 г.); Международной научной конференции «Компьютерные науки и информационные технологии» (СГУ, г. Саратов, 2007 г.); VIII Всероссийской научно-технической конференции. (ВСГТУ, г. Улан-Удэ, 2007 г.); Ежегодной конференции по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета «Социально-экономическое развитие России: Проблемы, поиски, решения» (Саратов, 2007, 2008 г.).

Публикации. Основные результаты опубликованы в работах [М1]-[М12]. Работа [МЗ] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук». Разработанный автором программный комплекс для исследования свойств нечетких моделей дискретных систем зарегистрирован в Отраслевом фонде алгоритмов и программ [М8].

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

Заключение

В данной работе разработан понятийный и методологический аппарат для нечетких полуавтоматов и собственно нечетких автоматов. Для данных видов автоматов введены понятия подавтомата, гомоморфизма, конгруэнции, фактор-автомата (определения 2.1.1-2.1.7, 2.2.1-2.2.7). Для введенных конструкций разработаны и доказаны теоремы о гомоморфизмах и конгруэнциях (теоремы 2.1.1-2.1.5, 2.2.1-2.2.5). Показано, что множество конгруэнций и множество подавтоматов нечеткого автомата (а также и нечеткого полуавтомата) являются решетками (теоремы 2.1.2, 2.1.6, 2.2.2, 2.2.6) .

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

Рассмотрены задачи связанные с нахождением индекса и периода нечетких матриц, а также двоичных булевых матриц; показана пеминимальность алгоритма Клиффорда-Престона (пример 3.1.1).

Проведен компьютерный эксперимент по подсчету индексов и периодов нечетких матриц фиксированных размерностей: до размерности 6x6 -нечеткие матрицы с числом порогов равным двум и до размерности 4x4 с числом порогов до четырех включительно (таблицы 3.2.1-3.2.8), в результате чего был обнаружено то, что не все индексы реализуются нечеткими матрицами фиксированной размерности.

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

99

Показано, что индекс нечеткой матрицы размерности п х п (индекс п-вершинного нечеткого графа) не превышает [п -1)2(теорема 3.3.3) данная оценка лучше оценки, полученной ранее Ли (теорема 3.3.1).

Разработан программный комплекс [М8] (зарегистрирован в Отраслевом Фонде Алгоритмов и Программ) для исследования свойств нечетких моделей дискретных систем (нечетких автоматов, нечетких полуавтоматов). Разработан программный комплекс, позволяющий использовать компьютеры локальной сети для нахождения индексов и периодов нечетких матриц больших размерностей;

1. Артамонов В.А., Салий В.Н., Скорняков Л. А. и др. Под общ. ред. Л.А. Скорнякова. -М.: Наука. Гл. ред. физ.-мат. лит., 1991. 480с. (т. 2).

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

3. Бисли Л. Б., Гутерман А. Э., Канг К.-Т., Сонг С.-З. Идемпотентные матрицы и мажорирование // Фундаментальная и прикладная математика, 2007, том 13, № 1, с. 11—29.

4. Биркгоф Г. Теория решеток: Пер. с англ. М.: Наука. Главная редакция физико-математической литературы, 1984. — 568 с.

5. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. М.:Наука, 1997. 368 с.

6. Бухарев Р.Г. Основы теории вероятностных автоматов. М. Наука, Гл. ред. физ.-мат. лит., 1985. -288 с.

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

8. Глушков В.М., Абстрактная теория автоматов // УМН. 1961. Т. 16. №5. С. 3-62.

9. Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. — ISBN 5-9502-0057-8

10. Кац М. М., Критерий линейной упорядочиваемости частичного автомата, Изв. вузов. Математика. 1997. №10. С. 37-43.

11. Клиффорд А., Престон Г. Алгебраическая теория полугрупп, т. 1. -М.: Мир, 1972.

12. Кон П., Универсальная алгебра. -М., Мир, 1968.

13. Кофман А. Введение в теорию нечетких множеств; Пер. с франц.-М.: Радио и связь, 1982.-432 е., ил.

14. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учеб. Пособие /Пер. с англ. Екатеринбург: Изд-во Урал, ун-та, 1996.

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

16. Плоткин Б.И., Гринглаз Л.Я., Гварамия A.A., Элементы алгебраической теории автоматов. -М.:Высш. шк., 1994.

17. Поплавский В.Б. Определители степеней булевых матриц // Чебышевский сборник. Т.5, №3(11). 2004. С. 98-111.

18. Поплавский В.Б. Ориентированные определители произведения булевых матриц// Математика, механика. Сб. науч. тр. , №6. Саратов: Изд-во Сарат. ун-та, 2004. С. 111-114.

19. Робинсон А., Введение в теорию моделей и метаматематику алгебры. -М., Наука, 1967. -376с.

20. Салий В.Н. Алгебраические конструкции, связанные с булевозначными автоматами// В кн.: "Методы и системы технической диагностики". Вып. 8.- Саратов: СГУ, 1985, с. 12-20.

21. Салий В.Н. Нечеткие дискретные системы //Известия Сарат. гос. ун-та.-2003. -Т.З, вып. 2.-С. 159-168.

22. Салий В.Н. Универсальная алгебра и автоматы.- Саратов: СГУ, 1988.-72 с.

23. Скорняков Л.А., Об алгебраических автоматах // Кибернетика. 1974. -№2.-С. 31-34.

24. Скорняков Л.А. Элементы теории структур. Изд. 2-е, перераб. и доп. — М.: Наука, 1982.-160 с.

25. Сытник A.A. Восстановление поведения сложных систем. Изд-во СГУ. 1992. 192 с.

26. Татт У. Теория графов: Пер. с англ. М.: Мир, 1988 - 424с., ил.

27. Харари Ф. Теория графов. М.: Мир, 1973.

28. Atkin A.O.L., Boros Е., Cechlarova К., Peled U. N., Powers of circulants in bottleneck algebra, Linear Algebra Appl. 258 (1997) 137-148.

29. Baccelli F., Cohen G., Olsder G., Quadrat J. Synchronization and Linearity.-John Wiley & Sons, New York, 1992.

30. Bellman R.E., Zadeh L.A. Decision-Making in Fuzzy Environment // Management Science, vol. 17. 1970. - №4. - P.141 - 160.

31. Berman A., Plemmons R. Nonnegative Matrices in the Mathematical Sciences,- Academic Press, New York, 1979.

32. Brualdi R. Ryser H. Combinatorial Matrix Theory, vol. 39 of Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, UK, 1991.

33. Buckley J., Hayahi Y., Fuzzy neural networks: A survey, Fuzzy Sets and Systems 66 (1994) 1-13.

34. Burris S., Sankappanavar H. P. A Course in Universal Algebra, SpringerVerlag, New York, 1981.

35. Chaudhuri R., Mukherjea A., Idempotent Boolean matrices.// Semigroup Forum.- 1980- Vol. 21- P. 273-282.

36. Cheng W., Mo Z., Minimization algorithm of fuzzy finite automata, Fuzzy Sets and Systems 141 (2004), P. 439-448.

37. Cuninghame-Green R.A., Minimax Algebra, vol. 166 of Lecture Notes in Economics and Mathematical Systems. Berlin, Germany: Springer-Verlag, 1979.

38. Fan Z.T., Liu De-Fu, Convergency of power sequence of monotone increasing fuzzy matrix // Fuzzy Sets and Systems 6 (1997) 281-286.

39. Fernández M. J., Gil P., Some specific types of fuzzy relation equations, Information Sciences, Volume 164, Issues 1-4, 2 August 2004, P. 189-195.

40. Gantmacher F.R., The Theory of Matrices, vol. 2. New York: Chelsea Publishing Company, 1959.

41. Gavalec M., Periods of special fuzzy matrices, Tatra Mt. Math. Publ. 16 (1999) 47-60.

42. Gavalec M., Reaching matrix period is NP-complete, Tatra Mt. Math. Publ. 12 (1997) 81-88.

43. Godsil C., Royle G. Algebraic graph theory, Springer-Verlag, New York, 2001 (ISBN 0387952411)

44. Gratzer G., General Lattice Theory, Birkhauser-Verlag, Basel, 1976.

45. Gregory D., Kirkland S., Pullman N. Power convergent Boolean matrices // Linear Algebra Appl.—1993,—Vol. 179.—P. 105—117.

46. Holmblad L.P., Osregaard J.J. Control of Cement Kiln by Fuzzy Logic. In Approximate Reasoning in Decision Analysis (Gupta M.M. and Sanchez E. Eds.): Amsterdam, New York, Oxford. 1982 P.389 400.

47. Jonsson B., Topics in universal algebra, Lecture Notes in Math.250, Springer -Verlag (Berlin Heidelberg - New York, 1972).

48. Kim K.H., Boolean Matrix Theory and Applications, Marccl Dekker, New York, 1982.

49. Kim K.H., Krabill J.R., Circulant Boolean relation matrices, Czech. Math. J. 24(1974) 247-251.

50. Kim K.H., Roush F.W., Generalized fuzzy matrices, Fuzzy Sets and Systems 4(1980) 293-315.

51. Kolokoltsov V. N., Maslov V. P., Idempotent Analysis and its Applications.—Dordrecht Kluwer Academic, 1997.—(Math. Its Appl.; Vol. 401).

52. Kosko B. Bidirectional Associative Memories, IEEE Transactions on Systems, Man and Cybernetics, vol. 18, no. 1, pp. 49-60, January-February 1988.

53. Kosko B. Fuzziness vs. Probability, International Journal of General Systems, vol. 17, no. 1, pp. 211-240, 1990.

54. Kosko B. Fuzzy Systems as Universal Approximators // IEEE Trans, on Computers. 1994. Vol. 43. №11. P. 1329-1333.

55. Lambek J. Lectures on Rings and Modules.—Second edition.—New York: Chelsea, 1976.

56. Li J.X., An upper bound on indices of finite fuzzy relations, Fuzzy Sets and Systems 49 (1992)317-321.

57. Li J.X., Periodicity of powers of fuzzy matrices (finite fuzzy relations), Fuzzy Sets and Systems 48 (1992) 365-369.

58. Malik D.S., Mordeson J.N., Sen M.K., Products of fuzzy finite state machines, Fuzzy Sets and Systems 92 (1997) 95-102.

59. Malik D.S., Mordeson J.N., Sen M.K., Minimization of fuzzy finite automata, inform. Sci. 113 (1999) 323-330.

60. Mamdani E.H., Assilian S. An Experiment in Linguistic Synthesis with Fuzzy Logic Controller // Int. J. Man-Machine Studies. 1975. - Vol. 7. №1. -P.l-13.

61. Miller W., The maximum order of an element of a finite symmetric group," American Mathematics Monthly, vol. 94, pp. 497-506, June-July 1987.

62. Miyamoto S. On Hierarchical clustering by fuzzy graphs, J/ Japan Soc. Fuzzy Theory Systems 5 (6), 1993 1354-1371

63. Muir A., Warner M.W. Lattice valued relations and automata // Discr. Appl. Math. 1984. - V. 7. - P. 65-78.

64. Rosenblatt D., On the graphs and asymptotic forms of finite Boolean relation matrices, Naval Res. Log. Quart. 4 (1957) 151.

65. Rosenblatt D. On the graphs of finite idempotent Boolean relation matrices // J. Res. Nat. Bureau of Standards.—1963,—Vol. 67B.—P. 249—256.

66. Sanchez, E., Resolution of composite fuzzy relation equations, Information and Control 30 (1976), 38-48.

67. B. De Schutter, On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra // Linear Algebra Appl. 307 (2000) 103-117.

68. Schwarz S., Circulant boolean matrices, Czech. Math. J. 24 (1974) 252-253.

69. Schwarz, S., On the semigroup of binary relations on a finite Set, Czech. Math. J. 20, 632-679 (1970).

70. Schein B. A construction for idempotent binary relations // Proc. Japan Acad.— 1970.—Vol. 46.—P. 246—247.

71. Skornyakov, L.A.: Invertible matrices over distributive structrues, Sibirsk. Mat. Zh. 27(2), 289-292 (1986).

72. Tamura S., Higuchi S. & Tanaka K. Pattern Classification based on Fuzzy Relations. I.E.E.E. Trans. On Syst., Man, and Cybernetics. Vol. SMC-1, №1, Jan. 1971.

73. Tan, Y.J.: The semigroup of circulant matrices over a lattice, Southest Asian Bulletin of Mathematics 24, 475-479 (2000).

74. Tao Yang, Lin-Bao Yang, Fuzzy cellular neural network: A new paradigm for image processing, International Journal of Circuit Theory and Applications, Vol. 25,469- 481(1997).

75. Tao Yang, Lin-Bao Yang, Application of fuzzy cellular neural network to morphological grey-scale reconstruction, International Journal of Circuit Theory and Applications, Vol. 25, 153-165(1997).

76. Thomasson M.G., Convergence of powers of a fuzzy matrix // J. Math. Anal. Appl. 57(1977) 476^180.

77. Wang, H.F. and Chang, Y.C., Resolution of composite interval-valued fuzzy relation equations, Fuzzy Sets and Systems 44 (1991), 227-240.

78. Wee W.G., Fu K.S. A Formulation of Fuzzy Automata and its Applications as a Model of Learning Systems // I.E.E.E. Trans. Syst. Science and Cybernetics. 1969. Vol. SSC-5, pp. 215-223

79. Zadeh L.A. Fuzzy Sets// Inform, and Control. 1965. Vol. 8, pp. 338-353.

80. Zadeh L. Outline of a New Approach to the Analysis of Complex Systems and Decision Processes // IEEE Trans. Syst. Man Cybernet. №3. 1973. - P. 28-44.

81. Zhang, K.L.: Determinant theory for D01- lattice matrices, Fuzzy Sets and Systems 62, 347-353 (1994).

82. Публикации автора по теме диссертации

83. М1. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов // Молодежь. Образование. Экономика. Сб. научных статей участников конференции. Часть 4. Ярославль: РЕМДЕР, 2004. -С. 309-314.

84. М2. Максимов A.A. Об индексе и периоде нечеткой матрицы // Саратов. Гос. ун-т.- Саратов, 2005. 11 с. - Библиогр.: 2 назв. - Рус. - Деп. в ВИНИТИ 20.01.05, № 78-В2005

85. МЗ. Максимов A.A. Исследование сложных информационных систем с использованием универсально-алгебраических конструкций нечетких автоматов // Вестник Саратовского государственного социально-экономического университета. Саратов. 2006. №14(3) С. 126-128

86. М4. Максимов A.A. Базы данных алгебраических свойств некоторых дискретных объектов // Теоретические проблемы информатики и её приложений: Сб. науч. тр. / Под ред. проф. A.A. Сытника. — Саратов': Изд-во Сарат. ун-та, 2006. -Вып.7. С. 81-86.

87. М5. Максимов A.A., Салий В.Н., Индексы и периоды нечетких матриц и графов // Теоретические проблемы информатики и её приложений: Сб. науч. тр. / Под ред. проф. A.A. Сытника. Саратов: Изд-во Сарат. ун-та, 2006.-Вып.7. С. 87-95.

88. М7. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов «УАК 1.0» // Компьютерные учебные программы и инновации (Телеграф отраслевого фонда алгоритмов и программ). 2007, №1(24).

89. М8. Максимов A.A. Универсально-алгебраические конструкции для нечетких автоматов «УАК 1.0» . М.: ВНТИЦ, 2007. - №50200700129.