Методы и алгоритмы решения некоторых задач дискретной математики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САРАТОВСКИЙ орданл ТРУДОВОГО КРАСНОГО энашм ГОСУДАРСТВАМ«

университет им. н.г.чврныквского

3Г8 ОД

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

Лаврудан Владимир Иванович

УЖ 519.93

метода и алгоритмы гекния некоторых задач

ДИСКРЕТНОЙ МАТЕМАТИКИ

( 01.01.09 - математическая кибернетика >

Автореферат

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

Саратов - 1993

Диссертационная работа выполнена ь Саратовском государственно, университете им. Н.Г.Чернывевокого.

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

академик ЛЕИ РФ А.И.Богомолов.

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

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

ведущая организация - НИИ прикладной математики и кибернетик при нижегородском госуниверонтете им Н.И.Лобачевского

Зздита состоится " II' »у^ и<сЛ499& г. в_ ч. пин.

на заседании специализированнсич) Ответа К 063.74. £М Саратовског государственного университета им. Н.г.Чернышевского по адресу: 410071, г.Саратов, ул.Астраханская,83.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета и». Н.Г.Чернышевского. Автореферат разослан "_" _ 1993 г.

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

доцент П.ф.недорезс

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

ШаальносТьлТ:'^^. в пооледное вр«?мя большое разонтие гл-лучнли следования в области разработки методов и создэнял на их ссно? * горитмоэ решения многих задач дискретной математики. однако, (л решения некотор»« задач до сих пор не созданы вакие-лисЯ? ¡■годы решения или оувдстеукжие метода являются неприводимыми по южнооти и времени их решения. •

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

Объект и. предмат исследований. В диссегяационной работе исоле-¡тэтоя такие объекты дискретной математики как: корневые деревья, втономниэ автоматы, граф* и после довательнехли де Брейнал-знач-ыо цепочки и булевы функции. Предмет исследований составляют не-оторые свойства перечисленных объектов - автоморфизмы автонота втэматов, классы эквивалентности к-значных цепочек, бесговтор-ооть булевых Функций, методы их распознавания, методы и алгорит-ыгенерации корневых деревьев и последовательностей де Боейна.

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

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

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

- и ~

много автомата. Данные методы основываются на гонягии характер«' тики корневого дерева, введенном автором. Предложен мето.;

на основе которого создан алгоритм генерации пооль: девать № де Брейна, затрачивающий линейное от числа гензрируе>шх символ время. На основе анализа k-значиых цепочек создан новый метод разработан ajiroptfTM. распознавания Оесиовтоукюти булевих <>ункии5

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

АЩ&^ШЗ-РЗЗоту • По материалам работы были сделаны доклады сообщения на 4-ой Всесоюзной конференции по теоретическим пробле мам кибернетики /Саратов, 28-30 июня 1983г./. на 2 -ом Воесогонс совещании-семинаре "Методы синтеза и планирования развитая отрук тур крупномасштабных систем" /Саратов 26-28 июня 1986г./, на 8-е Всесоюзной конференции по проблемам теоретической кибернетик /Горький июль 1988г./, на 2-ом Всесоюзном сешнаре по дискретно математике н ее приложения« /Москва 30 янв.-2 Фев. 1989г./. н 3-ем Всесоюзном семинаре по дискретной математике и ее приложена ям /Москва 29 янв.-1 1991г./, на 7-ом Всесоюзном ооведанм по технической диагностике и отказоустойчивоетх /Саратов, июн 1990 г./. на 9-ой Всесоюзной конференции по проблеем теоретичес кой кибернетики /Волгоград, сентябрь 1990г./. основные направле ния и результаты исследований обсуждались на семинарах академик АТН России В.Б. Кудрявцева /Москва 1988г./, академика ЛЕН Росси

A.M. Богомолова /Саратов 1980 г. - 1992 г./.

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

печатных работах.

Диссертация состоит и

- s -

(ения. четырех глав, заключения, приложений и стока литера-j <23 наименований). Общий объем диссертации - 125 страниц »ношеного текста.

Содержание диссертационной работы. 5о введении дан краткий обзор работ по тематике диссертации и »числены основные результата, полученные в работе, 'лава 1 содержит три параграфа, основное содержание главы i 1Ящено методу генерации корневых деревьев. Решение даннрй за-1 существует; так в работе авторов диниц В.А., зайцев М.А. 'оритш генерации неиэоморФных деревьев" (Автоматика и телеме-«э". 4. 1977 г.> приведены методы генерации корневых деревь-В этих методах используется прдотавленне корневого дерева в î канонического кода длины 2<n-i>. Однако сам метод генерации гоориьй. Для осуществления данного метода при построении дере-з о числом вершин, равным п, необходимо хранить все предыдущие эшчоские коды деревьев о числом вершин, меньшим чем п. 1редложенный в наотоящ&Й диосертации метод генерации использу-тредотавлениа корневого дерева в виде характеристики этого де-1. Тзк. если на вход генератора подшю какое-либо дерево,прея-зленное характеристикой. то генератор преобразует данную ха-геристику в новую характеристику, следующую в лексикогра-ïokom порядке по возрастанию за входной характеристикой. При гроении следующего неизоморфного дерева генератор, используя шя об автоморфизмах исходного дерева, изменяет в нем только гь ого характеристики и поручает новое дерево. Так как число мций по поиску места изменения характеристики и само иэме-ie по порядку равно чжъ-у вершин в дерезе, то сложность метода >рааии корневых неизпморФтв деревьев по времени к по памяти -

- ь -

порядка числа вершин дерева.

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

00В§а§ЛёйИё.1Длй- Хараетериетакой вершины, находящейся на уровне I. назовем число вершин, смежных о ней и находящихся на уровне I*/, иначе говоря, характеристика вершины - это числа предков данной вершины.

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

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

Два корневых дерева изоморфны тогда и только тогда, когда их характеристики равны.

Ш]редел§шй_1 .д^З- Два поддерева' в дереве в, имещие общий узел ( вершину ), являющийся корнем этих поддеревьев. назовем сатоморфними, если характеристики этих поддеревьев равны.

Тшемяд^з. корневое дерево имеет нетривнальну» группу автоморфизмов тогда и только тогда.когда в иен есть поддеревья с общим корнам и равными характеристиками.

В ч 1.2 исследуется структура характеристики корневого дерева, показ«зается, что характеристика корневого дерева являс-тоя вложенной композиидай. Вводятся отношения эквивалентности на

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

В % 1.3 описан метол 'генерации корневых неизо?юр1«ых деревьев ! предложен алгоритм генерации.

8 главе 2 описаны методы поиска автоморфизмов комичных ¡втономных автоматов (аа>. доказываются три основные теоремы, ю^аолшцие по характеристике автономного автомата стаскать вое |Го автоморфизмы, зги теоремы сформулированы мк условия ¡учеотаования нетривиальной группы автоморфизмов ы» автеном-юго автомата.

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

т

» л, число комюнент связности равно т.е. ^ ^ * где

.-точность ¿-ой компоненты связности, '¿еж в каждой компоненте • вязнэотк характеристики деревьев, подвешенных к ьершинзм цикла, редставить (выписать) в виде циклической последовательности, а атем эту последовательность упорядочить лексикографически по бываник», то подучим характеристики компонент связности. Порядочив характеристика кошонент связности лексикографически ю убыванию, получим характеристику автономного автомата. Та«им образом, характеристику аа ложно записать в виде =■ гг,у, здесь Рг = п,п - так называемый

1 « п I 2 и

рефихя характеристики, - число состояний аа, п - мощности сотояний. компонент связности, записанные в соответствии о

упорядочением компонент, I. - число ьеркин цикга ¿-ой коетоае связности; « ® ^ - числовая харедсге[*кпмка ад,

*» ■ п.

- числовая характеристика >-го состояния «а ( * «-"«Я для состояний циклов и». = <*"(./> дач остальных' состояний, <=Гг/> есть полустепень захода ооотояния j >, а сами «> записа в соответствии овыиеопиоанным упорядочением.

Из этого определения следует, что характеристику мо* представить в виде корневого дерева. Корень дерева помеча числом г». Корень имеет * потомков (число коипоненг связности которые расположены на первом уровне дерева и имеют пометой п каждой вериине первого уровня дерева * подвешена одна верши второго уровня, помеченная числом г., а у каждой вершины пометкой I. есть ^ потомков, которые тляотоя числовы характеристикам« деревьев аа, подвешенных к данным веромн данных циклов. Таким образом, если для данного дерева выпиоа его пометки, начиная о корня и далее по уровням олева направ •го подучим характеристику «а.

Пусть хт» с!,2.....* 1, а = |А4= • »¿»Чв^ - пц

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

г :3 —*3. | <¥¿«1 » <уяез )</.!£ (/. с»> )) v, <2-1.1)

11 I » т I * * , I 4

<У£«3(> «/Г*(й4СвЯ </7*С«>) >Ь . (2.1.2)

а также верно следующее:

x = x - .. . = x , v а v= . . = v . (?..ы

а * » • X ■ •»

Здесь для общности введены как тождествен^

П'.рэстанооки, т.е. /йи>= /*'<«»»

В § 2,2 формулирук/гся и доказыват-ея .теореш об

- а -

>'ГО«ор$изма* звтатаюго звготата.

Тгюрема 2.3.1. Пусть даны А, г,.- и автомат A-ts.ái,

го

(= (1,2,... Вели 5 = и st т.е. а есть объединение

'Пересекающихся июжеств s , a ívs® si ts« я-. 6<s> = лин, то чя элоаентов множества

;S —♦ S|<Ví « l 1 <Vse S ) ((«« S —► « í-sl = / {»)! V

1 _ m 1 « к 7 l

v («« S-. V (M 34U 5-t (8-2.i>

¡рно следующее:

(Vi « I )(«< AutfAM, (2.2.2>

m i

v = <vtj"\ (2.2.3>

Таким образом, показано, что. если автономный автомат л >стоит из а компонент связности и все они, рассматриваемые как сдельные автоматы, иэоморфш между собой, то существуют !рестаноБ :и «. являющиеся элементами группа автоморфизмов iHHoro автомат а, а числовые характеристики компонент связности )вны между собой.

Теорема 2.3.2. Пусть даны A. f,. г/ *и автомат а = <s,6>.

n

= ti.2.. ¿':.яо, Eojm s - и st есть объединение

* i •«

¡пересекакдахся множеств s,. ct - один из элементов цикла \ и = /. tc4> для í « 1м, а Функция переходов 'определена еле душим 5разом:

fi « I )«VM s.)((t » /,1с )-• í(<) ~ <$.(fllv ж .1*1» >

la = / Ce > & ¿>«1-» 6U» = á. </, íc » » ¿ </ «e >>» .

' i » í-t ¿-1 * « m ' u. t

> для

s—> SfíVi « I >.<V«« S.MCii*l-> /?<«) • /(.„/г'®''*'

u=i_ ¿ / «s>n. {'8.2.4)

...

верно, что

0«flut(AJ, (2.2

V » (WJ". <2.2.

Таким образом, показано, что, волн автономный автомат состоит из одной компоненты связности, и число яервин ц№ 1 = ',»>. а каждая часть цикла, оодержавдя верыину соответствующая ftk, изоморфна любой другой части, то оудествэ перестановка п, такая, mu fl» aut<a>, а чиолоеме хзрактеристи этих частей равны между собой.

Теорема ,g.2r3. Пусть даны А, г4, f~* и а = ts,<s>. а в длина цикла it=i. Воли в= и s.U tco>. < со специал

. ' V»* . • . . "

добавленная вершна >. а функция переходов определена так:

(Vi « I I (Vea S.) Чт * fie » V с —» <<5(«> » с ») у

я l 'I I ■ О в

v u«s.-* ¿ta» = <«)>), то для.элементов множества

г = S|tv< • I^XVs« 8.Х(se St-» » v

V <*«S.—• f t») «= /?*«»>.> y (*" SU B—* r. <*> *'> -»•* i- í .■ i . ■ t

.;.':••.'■■■■' <2.2.;

истинно следующее:

(Vi )ty«Áut(M>, . (2-2Л

а V « л(У i"«v >" ... (V >". (2.2.S

здесь через "'cv >"' обозначена »-ая степень чисдовс характеристики У-го уровня дерева <»4.а л - высота дерееа а^. По определению, а строится из а^ следующим образом. К cocí

о»

яниям U в. добавляется состояние ( эершна ) со, петли ^. < i »1

заменяются на дуги <с.,со» и добавляется петля <с ,,со>. изоморфизма fi, и определения хорактериотики следует, что (2.2.

.2.9) для а верно.

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

уоть дан а = <з,г» и пусть «д, уа - множеотва расширений станосок (2.2.1), (2.2.4), (2.2.7) на множество е. ислоеую характеристику для автомата а южно записать как атенацию степеней числовых характеристик неа&томорФннх онент связноота:

v .. (2.3.1)

л 2: г - ччоло автомор<5ных компонент связности о числовой ктеркстккоП v., а * - число различных числовых характеристик онент связнооти.

3 (2.2.2) и (2.2.3) следует, что

V

= £ с « »• (2.3,2)

определение 2.3.2. Последовательности деревьев цикла мадьной длины будем называть автоморФными, если числовые ктеристики последовательностей равны.' а сумма длин едовательностеП {*звна длине цикла, аддуп из (2.3.1) можно записать в следующем виде:

V.»«/ ...V,, >4 (2.3.3)

1. x I - минимальная длина последовательности • числосых ктеристак деревьев, повторяющаяся к. раз, т.е. ^ ь. = ^ длина цикла рассматриваемой компоненты связности, з (Я.2.5) и (2.2.6) следует, Что

- и -

где Г * 1 - бдаскайшее целое большее х. № (2.3.4) следует. I /эд| =о. воли все равны единице.

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

у « и > ... * «. . \ч"ул ... (2.3.Е

*• ** У*у * у

Здесь 1= 17*. л .г 1 - чиоло ветвей поддерева (дерева)

У •

имеющие числовые характеристики, равные V., м - чклго различны к • у ' У

характеристик, а = ]ГЛу1 ~ о^е число ветвей, входящих

( ж«

узел у, ->у - числовая характеристика узла.

Из (2.3„0) и <2-2.9> следует, что число перестановок типа ;

дня любого узла дерева равно к ' У

I гу = V («уГ п. (2.3.6:

V«»

С помощью (2.3.5) можно клаосифицировать узлы дерева I деревья.

В общем случае из (2.3.5) и-(£.3.6) следует Теорема 2.3-1. Пусть \ г £ - множеотро перестановок типа г действую®« на множестве состояний дерева < входящего вершину цикла; 4 б^ - множество листьеь; I - тожество узла ш листьев), причем

I V = 1 * » V* (2-3.7)

Тогда

1 г^ < I а^. (2.3.8)

Т&к кьк суммирование производи.то'зь по всей узлам дерева, а

| получения ц.->щкл ги юючюотеа пег^станоров нг-нривединой теки образую®« необходимо суммировать только ко узлам одной ви из о'Ззк-го чиола » , то полученное пераьечотсо бол-^е олняетоя и Д.Я1 л*рео сановок неприьопмой оиотсмп образут«

Тяг.ин ОбрвЗОМ, ¡Швта

1 i 1

•< I « I

^т—« г— г—*

I' < I V

Нетрудно убедится, что перестановки <>д, г-л являются

ментами неприводимой системы образующих группы (а> , и иость этой оиптемы равна

I г 1<

| 0.^1*1 < I ♦ ¡--¿~| - 5(1)л>.

1»• ' i»i

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

ЯЗУЮЩИХ АиЫП).

Глава 3 поевя>яена методам построения ^йл^ровых оршклов. дложен метод "роспуска" эйлерова оргра<5а - преобразоье».ия рэфа в ордер-;во с сохранением свойств орграфа, необходим!« для троения его эйлерова орцикла.

в § 3.1 описан метод "роспуска" и доказана теорема, что ¡ученный после преобразования орграфа обьект является ордур4всм мелом ребер, равным числу ребер в исходном орграф, и каждая чинна этого ордерева им?ет пометку першины исходного орграфа, юыйэется метод построения из этого ордерева эйлерова орцикла и азываетоя корректность метода.

Б 5 3.2 исследуется специальный класс зЯл-г^занх оргра-1 - графы де-Брейна. Рассматриваются свойства матриц сме»ности ¡х градов. Выявляются характерные особенности этих чатриц. Зти ¡актериае свойства м-л гг*;ц смежности позволяет получи'/!.. формулу

для определения ребра орграф, которое необходимо включить эйлеров орцикл при tro поотроении. Полученная формула козво.г отказаться от хранения в памяги матрицы смежности исходного г рг де-Брейна и хранить только специальны/1 вектор числа оставим) ребер для каждой вершины, которые еще не участвовали в построй орцикла. длина этого сектора равна числу вершин граф«» де-Брей! Так как число вершин графа де-Брейна равно i=■""*, i * - мощность алфавита цепочек длины п, которые последовательности де-Брейна упакованы друг в друга, а чж

ментов матрицы смежности r{vt<J* радно i*, то видно, что памя необходимая для использования предложенного автором метода, в раз меньше, чем память, необходимая для хранения матр| смежности. Затем приводится алгоритм генерации последовательно« де-Брейна и доказывается его корректность. Формулируется теор<

о сложности алгоритма.

Из этих Teo¡>;M следует, что временная сложность алгорип является наилучшей, в том смысле, что на генерацию каждо! символа затрачивается константное время. Поэтому общее epei генерации всей последовательности дз-Ррейна равно по пордш числу генерируемых символов, т.е. равно «". В книге А. Ги.

"Введение* в теорию конечных автоматов" (-M.: Наука, 1s6(

приводится алгоритм генерации переборного типа, т.е. наибо.

сложный да времени.

Глава 4 посвящена решению проблемы распознавания 6éonoev. нооти булевых функций!

В ь 4.1 для решения данной задачи были проведены исследова) цепочлк (слов> из е*. Введено отненение ;>геив<и,ентнос' цепочек. Получены рекуррентные соотношения для чиом кл.зо< экБЧвалвнтооЬти. цепочек. Л^ллозкен метод «.алгоритм.- 1<айпознав;

эквивалентности цепочек.

В <> ч.2 и § 4.3 автором введены операции Функционального умно-ия цепочек (¿.на лог функций из рк>, Доказаны теоремы о том, что ¡у» функцию из Рк можно предотаэить в виде операции Функциона-юго умножения »• цепочек. Показано, что если перемножаются стан-ггные цепочки \ - ах...*-», то результатом умножения является ючка длины л", соответствующая какой-либо Функции из Приве-« таблица соответствий между булевыми Функциями от двух передних и деухмеотниш цепочечными функциями, когда аргументами це-<ечн«х функций являются цепочки

В & 4.4 изложены вопросы реализации цепочечных Функций дис-этными преобразователями. Описывается структура дискретного зобразовашля.

В § 4.5 выявляется сложность преобразователя и предлагается

•год оптимизации дискретного преобразователя, уменьшающий

рвоначалтуп сложность в <■» гда, где п - число аргумента

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

>рности функций из г-а. очевидно.что предложенный метод распознания ('есповторности можно модифицировать так. что было бы аоэмож-> распознавать беспоотирнооть булевых Фушсций над Любым базисом.

ч пр"1 приведены характеристики кеизоморФных корневых ;рэвьев для различных значений числа вершин дерева.

В при .гаже нии ?. приведены последовательности де Врейна для потерях п и где " - мощность алфавита, а « - длина цепочки. . 5а помочь, окаг^-'-ину'! при выполнении диссертационной работ«, зтор благорнГ"*« научному руково/мяелк.'. академику, щх.^ссору католйю "их-IЛ лес, л (у Когочолооу.

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

1. Лав рушим В.И., Папшев C.B.. Печенкин ВВ. Об изомор?«' конечных автоматов. Материалы 6-ой Воесоганой конференции по те речмчеоким проблемам кибернетики, т.2. СГУ, 1986.

2. Лаврушин В.И. Об автоморфизмах автономных автоматов. "Hei ды и системы технической диагностики". Вда.5.Саратов.: СГУ, 198

3. Лавруиин В. И. Линейный по времени алгоритм построения п оледовательнооти де Брейна. "Методы и оиотемы техничеокой диагн отики". Вып.14,часть 2, Саратов.: сту. 1990.

4. Лаврушин в н. Алгоритм вычисления и распознавания Соопу торных Функций А-значной логики. Тезисы докладов 8-ой Всесоих ной конференции по проблемам теоретической кибернетики. Ч^ть i Горький.: ГГПИ, 1988

Ответственный за выпуск к.ф.-м.н., доцент В.И. Салий.

Подписано к печати 30.11.93г. Обьем 1 печ.лиот. "Зжзз{059. Тираж 100 экз. ООП Упрььаенкз с патетики. 410830. Сарятов, Сакко и Ьвкцятти, 54/60.