Некоторые вопросы теории билинейных последовательностных машин тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ ¡!Ш А35?РЛЗДА1'А ИШ1ИТУТ КИБЕРШТИКЙ

|р"..............................— -—~-=л-ятя.<

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

1ШЕД0РЛ ГАМАР ГАМ КЫЗУ

НЕКОТОРКЕ BOOPOCU' ТЕОРИИ БИЯИНЗЙИЙ ПОСЛЕДОВИЕЛЬНОСТШХ МАШИН

01.01.09 - «агомпткчесиая кибернетика

АВТОРЕФЕРАТ

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

БАКУ - 1992

PafioTu выполнена e ЕакинскоД/Государстве ином Униворси-чете им.М.Э.Расул-эаде.

Научный руководитель: -- доктор технических наук, профессор Р.Г'.^АРАДйКь.

ЦЦциадьиие оппоненты:

- доктор физико-математических наук, профессор А.М.РУБЛШВ (Институт математики и механики ЛИ Азербайджана, г.Баку);

- кандидат физико-математических наук Н.Х.АСМШВА (Институт кибернетики Ali Азербайджана, г.Баку).

Йоаущая организация - Лнститут математики АН Беларуси, г.Минск.

сов на заседании Специализированного совета К 004.21.02 по присуждению ученой степени кандидата физико-математических наук в Институте кибернетики АН Азербайджана по 'адресу: 370141, г.Баку, ул.^.Агаева, квартал 553, д.9.

Отзывы на автореферат просим высылать в двух экземплярах с заверенными подписями.

С диссертацией можно ознакомиться в библиотеке Института кибернетики АН Азербайджана.

Автореферат разослан "X ¥"с £_1992г.

Защита состоится

Ученый секретарь специализированного совета

кандидат физико-математических наук,старший научный сотрудник

А.М.БАГИРС

/: л OBLAfl XAPAtCTEP.iCT.HA ?AU№

Актуальность работы. 3 последние годы возрос интерес ис— следователей к вопросам теории и практики дискретных автоматических систем. Одним из классов таких систем являптся после довательностнио машины, характеризующиеся тем, что множества входных воздействий, состояний и выходов их конечна и являются векторными пространствами над полем Галуа. Послеюва-телыюстные машины (Ш) находят широкое применение п современных системах кодирования я аекодировагая дискретной информации в качестве кодирующих и декодирующих, фильтров, в цифровых вычислительных машинах яри описании отдельных узлов и схем, реализукитих логические функции и арифметические спера- ■ ции, в качеств? генераторов псевдослучайных сигналов и счетчиков импульсов, в системах радиосвязи, при управления технологическими процессами, в имитационном моделировании макроэкономических систем и в других областях 'науки, техники и производства.

Наиболее изученным и широко используемым подклассов ПЧ является класс линейннх Ш (ЛПМ). Такие из: динамические характеристики, как управляемость, наблюдаемость, устойчивость и др., всесторонне изучены в работах А.Гилла, Р.Г.5араттепа, К.Негойце, С.Л.Блмина, Г.С.Поспслова, В.Б.Кудрявцева, A.B. Шапиро, Я.З.Цыпкинг и ар.

Что касается нелинейных кснзчнмх последовательностпн* машин, то'здесь до завершения теории очень далеко. Интересным' во многих отношениях.подклассом таких конечных автоматов

являются билинейные конечние последовательностные машины 1&T.Í). . ^следование вопросов теории b¡¿i, а также билинейных дискретшх систем vbC) представлязт собой ныне интенсиЬно развивающийся раздел дискретной математики. Укажем здесь на работы ¡-.Р.Котта, п.л Гайауна, Л.Л.Степанюка, и.Иаксоо и др. несмотря на обилие работ, такие вопросы теории Ы1М как диагностируемость, управляемость и обратимость остаются к настоящему времени е^е недостаточно изученными.

Предметом исследования данной диссертации являются как общие динамические свойства l!i:,;, так и вышеупомянутые вопросы управляемости и обратимости, гесмотря на некоторую схожесть cñiim динамических свойств LU.Í с аналогичными свой- • ствами Г-! и Lo, такие свойства biiM как диагностирование, управляемость и обратимость имеют принципиальные особенности, весьма существенно отличаледю ЬД'А как от JÜLV, так и от ВС.

Цель paioT» заключается в

а) исследовании otlhx динамических cb-íctb Ьи.'.;

б) получении юсгагочкых условии управляемости и обратимости Ых;

в) получении aociелочных условиЛ управляемости и обратимости двухпарамегр ичееких Ьи;

г) решении на a¿ü некоторых тестовых задач.

сб;..ая методика исследований основывается на результатах математический теории систем, теория конечных нолей, теории Muí. а работа используются понятия н методы отдельных разделов дискретной ¡.«тематики.

Тоорйткческая и практичесш-л t;c:iiK?crb. Пэяучемгггэ в работе результата, могут бить пологегг о ocwcy теории и методов НИ.;По полуъетш рос.--ль тагам йоят составнть алгоритмы решения конкретных прикладные задач спалим и синтеза кодирующих «. гофор^гцяетмх спстеи. .. . -

■Апробация работа. Отдельные раздали и результата диссертации докладывались аа Ресяубяшакгппс гклйеревдЬтх мсыюде ученых Мадешm Наук АзгрбзДдгзнл/ ¡'л covnmp'r. кг£эдри -"изтемдгическая етбервига»".. Бйсшеааго Гссунхссрсятега км. Ц.Э.Расул-задз и отдояа азгобра и'тсгтзгкй'Института иато-катшш и L'OH2-K5K;i /Л АссрбзЯдтанз. ' . ■

Научная откгека. В работа muqrrää есседздо ссгашет рззуямаиг: . . ' ,• " '

- гапэдиа 4эрнуг:а поякэА ps'iaatia Ell;

- рашвка задача жпзапзгцкя: ЙИ{,.

- кзЯваи с^фэтадонХ аягорэти' даготаетйрзсажя йаяаяыо-п>' соотоянзя !.пиее.гзлык>8 ВП бчаз?гсщ£э со дязггоеякг«гбЯ катряцн; ... " •. '. ■ , .

• -.юйдекв з^екмсгей доояагшйов убяовкя тлтай упраз-Дяейоети и. .обратего'стя ВМ;

- построена.система посяэдопатсямюстт&г: исеот, кгрзкцая роль обратной системы к дагагй ЁШ;, .

- кай£зка г'Хфзпишкс доетаточшг уатсгяя яояйоЯ упразляе-газетя-к обратаюсти.jagntepaaratprssesax БЙЗ.....

. . Публякадяп. Сггавгаз рззу-тетата диссертации опубликованы п работах.

Структура ii обьея работы. Диссертация состоит из вйпдэ-

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

ОСНОВНОЕ содержание Д1ССЕРТАЦДО

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

" Первая глава посвящена изучения общих динамических свойств билинейных последовательности!!}; машин.

Ьилиьейная послеаовательностная машина над полем где р - простое число, описывается следуощей системой уравнений

называемых уравнениями её состояния и выхода соответственно Здесь //, Д ¿7, ¿г ^ - характеристические матрицы

ЫШ, ,$ - /7 - мерный Ебктор состояний ЬПМ, у - /- мери вектор входа, ^ - /77 - керный вектор выхода.

В § 1.1 рассматриваются элементарные составляющие БЩ, реализация ЬШ по характеристическим матрицам, дается стру тур пая схеца БПМ, а также выводится формула полюй реакции

ТЕОРШ I; Дня любого t>2 состояние и реакция БПМ определятся" следующим образом

г

(I

(2

*CSn(t"l)

Б § 1.2 рассматриваются вопросы эквивалентности, минимя-% зщхя, подобия БПН, подобая минимальные БЩ определяется диагностическая катрица ШШ. •

Состояние БШ и состояние ^ . БЩ называются эквиваленттает, если под воздействием одной и той жз входной последовательности ыашад ' и . находившиеся соответственно в состояниях Sf и , генерируют одинако-. виз виходше последосателькост.. - . SEi и / газаваэтся эквивалентными, если каядому состояиш Sf Bffii -df соответствует по меньшей мере одно, состояние БЕ! ^ , эквивалентное Sf • л, наоборот, каждое састояшо ^ БПМ соответствует по меньией мере одно состояние ЫИ ^ , эквивалентное ^ .

Если ЕШ ^ характеризуется -матрицами 4,8,0, G-K р. ШМ характеризуется матрицами

/-/И*"', S-PB, с~сК G.-PG-J-'(к-Ц),

где . Р г некоторая неособенная матрица, то d- и Л- называются подобными ЫМ.

ТЕОРЕМ 2. Если Б1Ш ^ я »/ подобны, то состояние 3 БШ Л- эквивалентно состоянию. 5 т Я& .БПИ .

Цусть БГЫ $ характеризуется матрицами 4 , В . С и <5^. (/( ш Д?) • Ограничимся (в теоремах 3-10) для простота случаем, когда А&^^А, (ЛУ"/7?) • IОбщая- ситуация рассмотрена в §§ 1.2 и 1.3 настояний диссертации) .

Определим диагностическую матрицу К йЫ следующим образом

кокаин К являются всевозможные произведения . .. такие, что о!у ^

'ГЕОГгЖ 3. Для любого / > / и произвольного набора векторов ¡/(О), и(1),

тогда а только тогда, когда Кв^О

'ГЕОПЫА 4. Состояния ^ и ЫИ эквивалентны тогда и только тогда, когда

ЫЦ, не имеющая эквиваленпшх состояний, называется ыиго цельной. Построение минимально» формы Л ЕШ называете! ицци14изацией БШ ".

Пусть ранг Диагностической патрицы Л" ЪШ4 & равен 8 (¿6/7) Составим из первых 1 лиьейно независимых стро

К(р, П) ~ матрицу Т и через & обозначим правую обрат-нуи к матрицу. Определим 2- мерную ЫЫ с

помощью характеристических матриц

А-Щ, З'ТВ, С-СЯ, 4,

ТЕОРЕМА 5. Состояние 5 БПМ эквивалентно состоянию

л " л - л.

& БПМ Л (и состояние 5 ЕПМ ¿т эквивалентно сос-

тоянию. Й БСИв^)..

ТЕОРЕМА 6. Для любого иульгииндекса (с^,оСг,..., вшолняется равенство

. -та'Ъ;.

л Ь

ТЕОРЕМА 7. ^агностическая матрица К БПМ ¿гг задается соотношением

■ к-кя

ТЕОРЕЦА 8. Пусть БЩ и эквивалентны, причём каждое состояние 5 £Ш ^ эквивалентно, состоянию Р$ БШ & где Р - некоторая неособенная матрица. Тогда Й1 и $ подобны. . .

ТЕОРЕМА 9. Если БЩ и Л минимальны и зквивалентш, го каждое состояние 5 БЩ' эквивалентно состоянию Ау БПМ , где Р- некоторая неособенная матрица.

В § 1.3 рассматривается диагностирование минимальных ЕШ. .

ТЕОРЕМА 10. Начальное состояние ¿(ф минимальной Б1Ы определяется однозначно конечным числом ректоров.каждый из

'л

которых соответствует выходу при специальном тестовом

л

входе, т.е. БПМ ыояхет быть "продиагностирована".

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

Вторая глава посвящена вопросам управляемости и обрати. мости билинейных последовательности!« машин.

В § 2.1 даны достаточные условия управляемости однородных двумерных ЕШ с одним входом над полем .

Однородная двумерная ЕШ с одни« входом .описываемая уравнением состояния (I) СВ"0 , /■»/ , /]т2 )« называется вполне управляемой, если супрствуэт натуральное число

N такое, что для лобых двух ненулевых состояний 5' и найдется последовательность управлений (¿/0, ¿¡Т,, ) £ М £ Л/ , переводяя^я НЕЙ из состояния в состояние б". ' " -

ТЕОРЕМА II. Для того, чтобы однородная двумерная БПИ с одним входом над полем была вполне управляемой,

достаточно чтобы

I); п> в-'-бг;

111) ¿а/г А \G-AX, А6Х]-£ Ух? О

Отметим, что условия I) и 111) являются аналогам® соответствующих условий для БС. В диссертации показано, что при нарушении условия П). утверждение теоремы теряет силу.

В § 2.2 даны достаточные условия управляемости однородных /7 - мерных ( ) БПМ с одним входом над полрм &(■?)

Введем обозначение: для 4>О Ж (&) - А%... /8) ~ матрица размерности

,П*П . Для 1°К~П ^(в)- ото матрица размерности получающаяся из ^(¿) удалением /-го столбу.

ТЕОРЬМА 12. Дня того, чтобы однородная /7- мерная ( /7 »^ ) Б® о одним входом в была вполне управ-

ляема, достаточно, чтобы

• I) Г-/

п) га/?А [¿¡($), Ув-О, ¿-£7т

В § 2.3 даны достаточные условия обратимости БПМ, производится построение обратной системы.

БПМ называется обратимой относительно состояния , если существует натуральное число А/ такое, что каково-бы ни было входное воздействие и(б) » найдется последователь-: ность тестовых входных сигналов 1/(2), • • •, (Л/), М £ N > Л1 а М(§0) • при воздействии которых сигнал Ц (0) однозначно определяется по выходу Ц (А!* 1) .

ТЕ0РЕ!ДА 13. Для того, чтобы БПМ $ была обратима относительно состояния ^ , достаточно, чтобы о

П) '\iifO нашлись бы натуральные числа /П2,..., /Г7„ такие, что

Нетрудно видеть, что на самом деле П) эквивалентно условии

- IE -

гапб(s, As, Л, J*"s) - /г, *s?0

.. В Л- 2.4 рассматрнвается..двухпарамёгричзская БШ & к (юходятся достаточные.условия се. управляемости. ;

Однородная двухпараметрнческая БШ ¿£ описывается следующим уравнением состояния

, Р'7) ~ \A+ii(t,V)G- +£ЩЩ *8>S(i* J,р)

Двухпараметрическая ЕШ «2- , игходяцаяся в начальном состоянии/ ", назнЕаетса Сааккз.$нраяляа$сй, если существует число Af .такое» етг епЙого т^яавого;,сос®эяг . ния Sf - .найдется цоаочшх ¿гфзажигхй: ^C&t^j^g^^ о'б/йк* переводящая БПМ из састояшш у щ а.соигаякпо . Gasx-i, что управление -.шизст pair • / . огнзеителью пара- •

метра есяз"-..

Цуеть - Ыыст^а Ш «й- прт (/¿J) > •

начальном состояшш ■ к 1ф'лсш£.упра£Дг:шп: до /-/ 'ранга относительна тжшггесяькэ» cam /V/ . п

ТЕОРЕМА 14. Дяя того, ото&? дсухпаргше^рксспак ЕЕ .¿3?. била вполне управляемой, достаточю, чтоби дяя нзетго-шбудь / , О£{¿/1-1

tank [GS^frht),&Gtyn^J), 8Г ek^MV*

При этом

" еСЛИ ТО .

^ h.MJ-n-au*-'« f-oн)

СЛКДСТШЕ. При /»¿7 достаточное условие полной управляемости двухпараметрической БПМ ¿4 приобретает вид

• sank [Gai, п >

а при и дополнительном предположении коммутативнос-

ти матриц В и G

В диссертации найдены достаточные условия, при выполнении которых двухпараметрическую БПМ, находящуюся в момент времени и состоянии Câgf О , возможно перевести

в состояние ¿^0 с помощью цепочки управлений

В 5 2.0 даны достаточные условия обратимости двухпарамет-рической БШ, описываемой вышеприведенным уравнением состояния и уравнением выхода

с еотеЬтвенными условиями С+0, Û .........

ТЕОРЕАА 15. Для.того, чтобы двухпараметричеокая Б1Ш Л-была обратимой относительно с<5стояния , достаточно вы-

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

I) гап& js, fiS, B"'fS ]- /7 . для любого S^ú, п) smk [5, 05, • • •, ^''s ]"/7 для любого SfO .

ТЕОРЕМА. 16. Если матрицы ¡4,3 я td перестановочны, то для обратимости двухпараметрической БШ относительно состояния о}0 достаточно, чтобы для любого SfO

¿mk (/г4'(м)зя)8*~т$\ ' я.

В приложении диссертации приведены программы на языке CLIPPER Д®1 решения задач минимизации БПМ, диагносги-рованил начального состояния.и обратимости.

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

По осносньм результатам диссертации опубликована пять работ: ..... ...

1. Мамедова Г.Г. Об обща динамических свойствах конечных билинейных последовательшстных машин. Дэп. в ШИШ, 1939, If 406I-B 89. .. .

2. Мамедова Г.Г. Об управляемости однородных билинейных последозагельностных мозмн. Дзп.в ШНИ5М, 1990,№ 6I72-B9

3. Мамедова Г.Г. Об обратимости биланейнах последователь-■ ноеттах машин. - ¿¡¡эл. в ШШШ, .1991,. № 3275-В 91.

4. Мамедова Г.Г. Об управляемости двумерных од народи« билинейных последовательшстных машин.Материалы ,Х респ;

ликанской конференции молодых уча и к по математика и механика, "Элм", Баку-1991.. .. . ..

5. Цшедова Г. Г. К вопросу об .упра?лг.аностн однородшя билинейных гшследоватедыюстких малин. - Известия АН Аз.ССР, сер.физ.-твх. и мат.пауя, 1990 ,