Студii з теорii автоматiв, теорii iнформацiйных мереж та вибраних проблем дискретноi математики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

чь

1нстнтут гЛбернетики ¡м. Б, М. Гдушкова АН Украши

'г* г.рс'ах рухопису

Кратко Мирослав 1ванович

- Студ1'1

з тзорм автомата, теорп шформацшшпг перегл та зпбраннх проблем дискретно? математшш

Спец1алш!сгь — 01.01.09 математична ¡иберпетика

ДисгртацЬ у вигляд! науконо! допопЩ па здсбутгя науксзого ступени доктора фчзияо-матештичних наук

КяТв -1592 р.

Робота виконанана в Ьгегитут! математики АН УкраТни

0ф1ц1йи1 оноиенти:

доктор ф^зико-математичних наук, профссор, член-кореснондент Росшсько! ЛИ

О.Б.Луныюв

доктор ф1зико-математичних наук, профссор, член-кореспондент АН УкраТни

В.Н.Редьдо

доктор ф13ико-математичних наук,

А.О.Лсрнгська

ПроЫдна орган1зац1я КнТбський нол!теяшч1Шй Ьютитут

3-зхист вЦбудеться 1 1995р.

на засЗдати сннцал^зовано! вченоТ ради А. 016 4>.01 и 1иститут1 кибернетики 'т. В.М.Глухакова АН УкраТни Кил 6, буя. Академий Гяушкова, 40

3 днсертафею можна ознайомитися у б!бл!отец11нституту к1бернстикн 1м. В.М.Глушкова АН УкраТни Кшв, бул. Акадежко Гяушкова, 40

Дисертацт роз!слано «. /Г, /Л

Вчений секретар спец'1ал1зованоТ вченоТ ради, к. ф.-м. н.

В.Ф.Синявський

I. Загальна характеристика роботи

Ахтуальн!сть теми. Багато наукових проблем, що линикли з потреб конструювання пристроТз сучасно! техн!ки, зокрема пристроТв автоматики, обчислювально! техшки, систем зв'язку, як також багато проблем, що постають у б!ологи, ехономщ!, соцюлогП тощо, мають ч1гхо виражений дискретний характер. Тому при теоретичних досл^джешшх таких проблей застосовуються засоби та методи сучасно! дискретно! математики, яка, у поршняни! з дискретною математикою початку нашого столотя, значко розширила свою область. Ниш, кр1м традицшних роздЫв комбшаторики (до реч!*, також суттево розширенних), до дисхретно! математики долучилися так! нов1 дисциплши як тсорш граф!в, теор!я скшченннх I несмнчешшх автоматЬ, теорш планування сксперииитв, теорш розклад1в « багато штих. Актуальнкть та важлив1сть досл!джень в дЬигац! дискретно! математики загадыю визиа-на. Студи, що складають предмет дисертацн, стосуються двох напряпшв — теори автомат! теорп шформацШних мереж, а також спор!днених з шши (або таких, що близья! до них) проблем дискретно! математихи.

Автомата увшшли у сучасну математику як натеиатичн! модел1 азто-матичних 1 обчислювальних пристроТз. Перш! публкацп з теорп автомата з'явилися у 30-х роках нашого столотя (роботи А.Тюр!нга та Е.Поста). 3 50-х рошв розпочався бурхливий розвиток теори скигченних автомата, зумовлеиий потребами роззитку технки релейно-хонтактних, автоматичних та обчислювальпих пристроТз. Дещо п!зшше, потреби програмування та неабзздшсть враховувати складн!сть обчислень приведи до розширення модельно! облает! I активного вивчення клас!з иесшпчешшх автоматЬ, таких як автомата з магазинной пам'яттю, 6а-гатостр^чкоз! та багатоголозков! автомата, тощо. У дисертацц розгля-пут! проблеш! теори автоматЬ, що належать до основоположных у цШ д1аяицЗ. Це проблема мови задавапня сличенного (абстрактного) автомата 1 проблема реал!зацП такого автомата у вигляд! схеш (композици

з

автоматов), а також проблема побудови моделей самов1дтворного автомата.

Теор!я !нформац!йних мереж бере свш початок в!д задач, що виникли у телефоннш та обчислювальнШ техшц!, зокрема при проекту-ваши багатопроцесорних комп'ютерних систем та комп'ютерних мереж, а також в1д задач розпаралёлювання обчислень, програмування тощо. У теоретико-графових терм'шах Тх можна • формулювати як задач! видиення систем маршругсв у графах даного роду, що мають т1 чи тип бажан} властивост!, або як задач! побудови графив.у яких так! системи маршрупв !снують. Наш! студи в основному зосереджувалися на задач! оптимально? системи комунжацш у багатопроцесорних обчислювальних системах. Як в1домо, осиовн! трудиощ! проектування таких обчислювальних систем з.багатьма паралелыю д!ючими процесорами зводяться до проблемк побудови каналов зв'язку «¡ж ними. Подалыш досл!дження у цш д^лянщ, ям стосуються елементш загально! теорц !нформац!йних мереж, продиктоваш як внутршшми мотивами теори, так 1 бмьш за-гальними задачами комушкацшного характеру.

До дисертацн долучено також робота дискертного напрямку, що мають безпосередне в}дношення до викладених аище двох роздШв: теори автоматов та теорп шформацшних мереж. Це теоретичш роботи, що стосуються теори граф1в, абстрактно"! теори складност! обчислень та теорп ймов1рностей, а також роботи застосовного характеру в облает! дискретних перетворювач!в, структури канал!в зв'язку, розпод!лу пам'ят! у компьютерах тощо. Причини включения цих роб1г у дясер-тац1ю, 1хня актуальн!сть та важливкть визначаються тим, що:

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

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

Мета роботи. Досл1Джеиня у диянц! теорп автомата мали метою:

— вивчення багатопосилкових регулярних рахунюв Поста, зв'ясу-ваняя клас)в, породжуваних такими рахункаии множин сл!в та можливостей використання Тх для задавания ск!нчекних автоматов [1,2, 36];

— вивчення сшввщношення м!ж стабмьними та регуляркими

!теративними системами [3] та »¡ж стаб1льними ¡теративними системами 1 машинами Тюршга, що працюють на площиш [4];

— з'ягування функцюнальних иоклнвостей автомате Беркса [5];

— вивчення предиката Л (а,Р): «сшнченний автомата реал!зуеться у вигляд1композищ1'елеме1ш'в базису Р » [6, 7, 8, 37, 38];

— внвчення аналогичного предиката для автомат Реддшга [58];

— з'ясування можливост! декомпозица регулярних [9] 1 групових [39] Ггеративних автоматов;

— формал1защя глкематичноГ модел1 самов1дтворних автоматов [10, 43, 46] на основ! поняття породжувального автомата.

Досл1дження у дшшщ те ори шформацшних мереж мали метою:

— вивчення р!зних вар1а!тв сполучення процесор|'в у багато-машинних комп'ютерних системах [11, 12, 13, 14, 15, 16, 40, 45, 47], зок-рема, розв'язання задач! Ю.Г.Решетняка про оптимальний метод сполучення при обмеженш емност! комутатора;

— вивчення проблем трикаскадних схем [17, 18, 20, 21, 41, 42] на основ! моделей дводольних граф!в;

— вивчення проблем загальноТ теори комушкацшних мереж та 1хне застосування для побудови паралельних обчислювальних систем [27].

В роботах, що близыс! по своему характеру до викладених вище двох йапрямшв 1 як! включен! в дисертац!ю ставилася мета:

— розв'язати поставлену В.М.Глушковим задачу про шру 1нформацпшоТ надлишковосп симетричноТ п!вгрупи [29];

— з'ясувати можлнвосп узагальнення введено! М.Блюмом абстракт-»01 М1ри складносп обчислень та досл!дити зластивост! Ц1е! шри [29, 44, 51, 53, 54, 55];

— вивчити клас граф!в з даними щ!льшстю та числом всесум!жност1 ¡^32] та дати спос!б конструкци класу граф1в охоплення 5 та б [32];

— вивести теорему Б.С.Севастьянова, що стосуеться випадкових в!дображень та розбитт!в схтченнихмножнн з теореми де Брейна [33];

— розв'язати поставлену Е.Лосем проблему щодо характерястичних мнолшн систем Е1Дношень екв!валентностей [34, 35, 56].

Методи доел!дгзень. У дисертацП використовуються методи мате-МатичноТлогки та теорП автоиатш, теор!Тграф!в I комб!яаторики, теори ймов!рносте» та загальноТ алгебри.

Наукова новизна. Результати, викладеш у включених в дисертащю роботах е новими. Вони дають в!дпов!д! на низку проблем, сформульо-ваних в1домими вченими як важлиш нерозв'язаш проблеми, В1Д вир1шення яких залежить подалыпий прогрес досл1джснь у даних галу-зях. Закладен! нов! напрямки досл!джень: у теори скшчених автомат!в — алгоритаично нерозв'язш проблеми як у структур шй так 1 в абст-рактшй теори, та розвиток теори самов1дтворення иа баз! породжуючих автомаив; у теорп шформацшних мереж — до сложения трикаскадних схем иа основ! дводолышх графив; у теори складност! обчислень — . досл1дження розширеного поняття абстрактно: М1ри складност! обчислень.

Автор уперше:

— доказав ¡снування алгоритмгаю нерозв'язних проблем у теори ск'шченних автоматов та дов1в, що центральна проблема структурно! теори скшченних автоматов — проблема повяоти — е алгоритм!чно не-розв'язною;

— остатоуно з'ясував пророджувальщ властивоси регулярних рахунгав Поста;

— розз'язав проблему Ф.Геш про сп!вв!дношення м1ж регулярними та стаб1льними ¡теративними системами;

— запропонував строгу математичну формал!запую кшематичноТмо-дел! самов1дтворювального автомата фон Неймана на основ! породжу-вального автомата;

— розв'язав проблему Ю.Г.Решетняка про степ!нь !нформац!йних граф1в;

— запропонував як модель трикаскадних схем використовувати дво-дольн! графи з фарбоваиими ребрами, що даЛо можливкть на ц!й основ! розв'язати низку в!дкритих проблем та значно спростити доведения ряду вЦомих теорем ц1еТ теори;

— заклав основи загальноТ теори шформацшних мереж;

— дав оцшки М1ри шформацшно! надлишковост! симетричноТ швгрупи степет N нижч! за И' (задача В.М.Глушкова);

— запропонував узагальнення блюм!всько! м!ри складност! обчислень та довгв низку загальних теорем для тако? м1ри;

— запропонучав нове просте доведения теореми Б.С.Севастянова

прошшадксш1 воображения i розбиття скшченнихмножин оперте на теорему де Брейна;

— дов1Н, гцо гипотеза б.Аося щодо характеристичных множйн систем в!дношення екв1вален'Шог.гей не справдзхуеться, i що, взагал!, властив!сть бути характеристичною множимою таких систем в^дношень не моясе бути ncpenipena локальними засобами.

Впроваджеиня результатов. Результати дисертанта увшшлн в учбов! програми курсу з дискретно! математики для механко-математичних факультет ушЕсрсит<гпв, вони викладаються у ряд! монографий, шдручнмюв, навчальних поабшшв, зб!рник!в задач, книг з математики для шженерш. На mrift ocuoai читалися спецкурси для студент ушверсите-пи та полггехшчних шститупв.

На основ! розроблених у дисертацй теоретнчних метод!в на Луцько-му завод! скнтетичних шзар та на 1ван!вському камвольному комбшат! у 1976—1984 роках буди створен! мереяи зв'язку для передач! Ыщативних снгпал!в систем АСУТП. Загальиий економ1чний ефект — 523 тис. крб. на рЗх. ЗдШснена та кож розробка структури каналу зв'язку для АСУТП потушшх установок кондиц!онування повигря, що дала економш контрольного кабелю в 5—7 pa3ia пор!вняно з перв!сно запланованою.

Методи, розроблен! дисертантом, використовувались також при проехтуванш систем контролю мкроюлмату, вибор! оптималышх спо-co6ia подключения електрод!в у термоелектроА1тичних пгрометрах тощо.

Апробац!я. Результата, що ув1Йшли до дисертацй, допов!далися на 12 м!жнародних конференциях, зокрема, на МЬхнародному мате-матичному коигрес! у Mockb'i, на 5 та на 8 Мшнародпих конгресах з аопки, методологи та фиософи науки в Канад!, 1975 р., та Mocrai, 1987 р., М1;кнародш"й зимовШ школ! з арх^техтури м!кропроцесорннх систем у Будапешт!, 1978 р., Четвертому мЬхнародному симпозиум! «Форматор» у ПразЗ, 1983 р., М1жнородн!й конференцй «Основи теорн телеграф!^» у Mocol, 1984 р., М!жнародн!й конференци «Основа теорп обчислень» у Казан!, 1987 р., Другому штхнародпому ceMinapi з теор!Г телетрафка та комтЛотерного моделювання у Москв!, 1989 р., МнкнороднШ конференцп « Аогиса у ботику» в Переславл!-Зал5сьхому, 1989 р., трич! у МЬмюродноиу математичному центр! !м.С.Банаха у Вар-шав! та in.

Результата допсшдалися також б!лып як на двадцяти Всесоюзних та республжанських конференц'шх, а також на наукових сем шарах в 1нститут! математики АН УкраТни, 1нститут1 прикладних проблем механики i математики АН УкраТни, 1нститут! к1бернетики АН УкраТни, 1нституп проблем иоделювання в енергетищ АН УкраТни, КиТвському 1нститут1 автоматики, КиТвському та Льв^вському ушверситетах, КиТвському та Аьв'шському пол!техн!чних шститутах, Московському, Новосиб1рському та Красноярському ун!верситетах, Красноярському полггехшчному шститут!, Обчислювальному центр! АН СРСР, 1нститут1 математики Сиб^рсьхого в!дд5лення АН СРСР, в 1нститут1 математики та в 1нституи 1нформатики ПольскоТ Академп наук, та !н.

Ряд результате вперше отриманих дисертантом викладалися шшими авторами у Тхшх наручниках, монограф1ях та навчальних поабниках. Розв'язки проблем, сформульованих шшими вченими доведен! до в)дома авторов цих проблем i признан! ними як пратшльш.

Цикл poöiT з теорн !нформац!йних мереж та Тх застосувань в'1дзначений у 1985 р. Академ'шю наук Украши прем!ею 1М.С. О.Лебедева.

Публ1кацИ. Матер1али дисертацй опубликован! у 58 роботах, поданих у вигляд! двох списыв. Перший список шстить назви 35 poöiT, в яких викладено Bei основн!, принципово важлив! результата дисертаци. Робота з другого списку це або nepmi приоритета! цублжацЛ отриманих результат (як правило, у вигляд! тез), що мають метою встановлення прнор!тету та наукового форуму, на якому в^дбувалася апробацш результат, або робота, у яких розвиваються та доповню-ються ochobhi результати, як правило в напрям! Тхнього практичного застосування.

Всього дисертантом опублковано понад 140 наукових роб!т.

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

1з 30 робге, написаних з сшвавторами, 19 — це робота, написан! з нешрантами дисертанта I 4 робота написан! з шженерами, у яких мате-маттия частина належить дисертанту, а техшчна — його enisa вторам. У ц;п: 7.3 роботах чистина особистого внеску дисертанта оцшюеться

S

приблизно70%.Урешт18спиьнихпубл1кац!яхчастинаособистоговнеску дисертанта не менше 50%.

II. Теоретичн! узагальнення й анал!з результатов

1. Теор1я автомат.

Теория автомат!в умовно под1ляется на два розд1ли: абстрзктну те-орю та структурну теорпо. Перша з них вивчае функцюнування автомата, тобто воображения посуидовностей вх1дних символ1в автомата у посыдовносп його вих!дних сшдвол1в, коли автомат розглядаеться як абстрактна математична модель — п'ятфка , <Х У, (), X, 5 >, друга — способи побудови складних автомата як композигцй (схем) б1льш простих автомата. Роботи, яы ув1йшли в дисертащю, стосуються як першого так 1 другого роздЫв.

Абстрактна теор!я. Одн1ею з основних проблем абстрактно! теори автомата е проблема, що стосуеться мови, якого здойсшоеться опис функц!оиування скшченних автомат та алогоритму синтезу автомата по заданому опису. ВЦомо дек!лька таких мов, найб!льш вживаною з яких е мова регулярних вираз!в, запропронованя С.К.Клш!. У роботах [1, 2] досл1джуються можлияост! застосування рахункЗв Поста для опису функщонування ск!нченних автомаив.

Як в!домо, Е. Пост для формал1зац11 ¡нтуГтивного поняття алгоритму вв!в спегральн! рахунки, правила перетвореная яких назвав продукции. В1и до в! в, що рахунки з продухц1ями найб!льпг загального вигляду можна звести до так звашсг нормальних рахунк!в, у яких про-дукц!Г маготь двоб1чний вигляд (Р10, стоять з р!зних бок!в в!дносно X):

РХ Хй

1 що за допомогою таких пормальних рахунк!в можна генерувати вс5 рекурсивно перелЬн! множишь

Як покачав Р.Б'юх!, рахунки з одноб1чиими продукц1ямя

РХ -» QX

(1)

генерують т!льки регулярш множини сл1в, тобто множини сл1э, що розшзнаються (або породжуються) скшченними автоматами. Отже рахунки Поста з продукциями виду (1) можуть бути мовою для опису скпгченних (абстрактних) автоматт, оскиьхи для довольно! регулярно! множини icHye рахунок Поста з продукц1ями виду (1), який генеруе цю регулярну множину. Р.Б'кш сформулював проблему, яку йому не вдало-ся розв'язати, але яка мае виршальне значения для вияенення генеру-ючих можливостей рахушив Поста: як! множини генерують рахунки Поста з продукщями виду

PiX-, PiX;..., PJC-+QX (2)

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

Теорема 1. Довгяьний рахунок ПостаП = < L, П >, Зе £ — довыьна регулярна множит елгв, а П — cnimetma система продукцт, до якоi кргя продукцт виду (2) можуть входити однобЫт продукци виду

генеруе регулярну множину сл1в.

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

Теорема 2. Для довольного нормального рахунку Поста можно збуду-вати о&нобЫний рахунок Поста з продуктами виду (4), який геперуе точно ту ж множину сл1в, що даний нормальный рахунок.

Таким чином в [1, 2] отримано остаточний результат, що стосуеться

XR ->ZJ

(3)

PiX-, РгХ ->QX та ХЯц XRi -> XS

(4)

класифЬсаци одноб1чних paxyiiKin Поста: тпкг рахуики подгляються на два класи, перший з яких породxys тг'яьки регулярен mi to кипи i, as,те, може служима noioso опису сктчеипих автомаппв, другий — Cci рекурсивно перглгчш тюжмш.

Роботи [3, 4] стосуються певшие спефалышм чином задаваних несюнчепних клаав скшченних автоматов, що Д1стали назву ¡теративпш: систем. Вони внзначаються як i'.полсипа Bcix ciTOK, складених з одного i того самого елемента (скшченного автомата), екземпляри якого розм!щеш у вкгляд1 паралелешпеда в точках п-вю.йрного ц1лочислобого простору та з'еднаш з суадшми елементамн певиим регулярним способом. Хтеративним системам присвячена велика кыь/псть podix. Важлпвими класами ¡теративних систем е клас регулярних i клас стабкьних ¡теративних систем. Сшвшдношення мЬк регулярними та стаб1\ышми системами вивчав Ф.Геш i, зокрема, дов!в, що яхщо итеративна система е хомбшацшною (елемент не мае пам'ят1), то з того, що вона е стабиьного випливае, що вона е i регулярною. Вш поставив питания, чи кнуе для кожно! регулярно! hepa-raimoT системи оЫвалентна Тй стабиьна регулярна итеративна система i яюцо 1снуе, то чи 1снуе алгоритм знаходження по заданш регулярнш снстш'1 екв^валентноТ Тй стабмьноТ регулярно? системи. До реч! зазначимо, що, як ДОВ1В той же Ф.Геш, проблеми розшзнавання як регулярное« так 1 стабиьност! е алгоритм^чно перозв'язними. У робот1 [3] доводиться:

Теорема 3. 1снуе ефективний cnoci6, що позволю по кожнш регу-яярнШ тератиЗнт систем збудувати еквгваяеитну тстабгяьну регу-яярну гтеративну систему.

За аналопего з розп!знаванням сив сынченними автоматами, у те-opii 5теративних систем вводиться розшзнавання матриць двовшмрними 1теративними системами. У робот! £4] вивчаготься сшввЦношення мЬк двовимарнимн ¡теративнинн системами i машинами Тюр!нга, що оперую-ть не з одновим1рного стр!чкого, а з площиною. Mas мхеце

Теорема 4. За довгльною площитою машиною Тюргнга яожна ефективпо збудувати стабгяьну гтеративну систему, яка умовно розпгзнае той же клас матриць, Ufo i задана машина Ttopinza.

Нарешт! у робот! [5] наводиться приклад алгоритмЗчно иерозв'язно!

проблеми в абстрактнШ теорй" сйнченних автомата. Стосуеться вш так званих автоматов Беркса, як! в!др!зняються в!д звичайних скшченних автомата Т1льки тим, що перебуваючи у певних станах,вони вилають на вих)д «пусту» букву (не видають иного).

Теорема 5. Не ¡снуе алгоритму, який Зля дов{яьних двох автоматШ Беркса визначае, чи г'снуе вхгдне слово, яке переводить щ автоматы в за-кяючм стани 1 породжуе на выход! одиаковг непуст! вихгдт сяова.

Цей приклад, простий на перший погляд, е першим в литератур! прикладом нерозв'язних проблем у абстрактны теорП сюнченних автоматов 1 св1дчить про те, що навггь для таких простих об'емив, як ск!нченн! автомати л'раниця м\ж розв'язними I нерозв'язними проблемами може бути доскть неч!ткою.

Структурна теорЬг. Основна проблема структурно! теорП автомаив полягае у тому, що для заданного абстрактного автомата I наявного набору автомат (бази елемент!в) потребно визначити, чи можна даний автомат збудувати у вигляд1 композицн елементш бази, належиим чином з'еднаних мЬк собою. На сьогодш ця проблема достатньо досл!джеиа ильки для класу автомате без пам'ятк Дисертант розглядав цю проблему для класу ск!нченних автомат)в МЫ та для класу Мщальних автомата Редшга.

У роботах [6, 7, 8], ям свого часу (1964 р.) лягли в основу кандидат-сько! дисерта^Т автора, вивчаготься властивост! предиката Щсс, Р): «автомат а можна реал!зувати ни баз! Р », де автомат а I вс! автомате, що складають базу Р е автоматами МЫ. Доведено так! теореми:

Теорема 6. Якнм би не був автомат а, предикат Я (а, е нерекурсивным.

Теорема 7. Тснують там бази р, що предикат Я (а,р ) е нере-

ку/ли'ним.

У доведена! теореми 7 наводиться конкретикй приклад тако! бази.

У робот! [58] аналопчн! теореми сформульован! для класу !нщ!альних автомат Редшга. Цей клас автоматт наближаеться за своТми властивостями до аток Петр! 1 вивчався Д.Ред'тгом та його уч-иями як приклад мереж, у яких не внникае «проблеми гонок». Б1льше шж 15 рсшв тому вони сформулювали проблему розн!знавання повноги для класу таких автомат, яка залишалася вщкритою, хоч роботи [6, 7, 8] були в!дом1 Д.Редшгу та його учням. Справа у тому, що способи моде-лювання нерозв'язних проблем, як! забезпечують усшх у випадку ск!нченнпх автомат, не можна засгосувати для автомат Ред'шга з причнини специф!ки Тх функц'юнування та специфпш нобудови мерек ¡з них. Запропоноваш у [58] нов! методи дали можливкть встановитн не-розв'язшсть биьш загально! проблеми, з якоТ нерозв'язн!сть розп!знавання повноти випливае як насл!док.

ВажЛивога проблемою структурно! теорп автомат е також проблема декомпозици, яка полягае у представленш даного автомата у вигляд1 композицн автомате у повному сенс! простших за первкний. Ця проблема розглядалася нами у робот! [9] для класу ггеративних автомат!в. Остановлено так! результати:

Теорема 8, За всякою дбовитрною одно6их\дноюрегулпнрою системою £ а тръома напрямами з'еднаиъ можна збудубати еквгваяентну

дво6гт1рцу однобих(дну регулярну 1 стабиъну комбтацтну систему £, яка мае ш* ж ширями з'еднаиъ, що» система X.

Теорема Можна ефехтиЗно збудубати дбовимгрну регуяяну авто-иомиу систему £ а чотирма напрямами з'еднаиъ, яка не може бути пред-сшвяенз у вшяяШ композита дёох систем з тръома напрямами а'еднаю,

Нг»решт!,ло важлнвпх задач структурно! теорц автоматт належить Задача побудопи так званого самов!дтворного автомата, яка протягала увагу бзгдтьрх ендатнпх вчених своею принциповою важлив!стго. Задача формулгоеться так:

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

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

Перша постановка ц!е! задач!, як 1 перше ТТ р'ипення у форм! так звано! шнемагично! модсл!, належать Дж.фон Нейману. Спроба фор-мгшзувати цю модель не була усшшною I тому фон Нейман запрокону-вав шшу, вже математичну модель, яку вщ назвав кл1тинною, яка, по сут!, е итеративною системою. Ця модель, яка дала початок нозому важливому напрямку у теори автомзтЬ — теори 1теративних (в шгшй термшолош, однор!дних чи фон-Неймашвських) систем — все ж в!дносно перв!сно! задач! мае ряд недолшв. Так, наприклад, «вложениям схеми автомата в однор1дну структуру створюе техшчш труднощ!, як! не магогь безпосереднього зв'язку з проблемою самов^дтворення.

У робот! [10] кшематична модель формал!зуеться на основ! поняття породждувального автомата. Показано, що при цьому долаеться ряд перешкод, як! виникають у юитинних моделях ! що нова формалЬащя позволяе збудувати ун!версальний самов'1дтворювальний автомат. Таким чином зазначена вище вимога, щоб автомат, який будуе свою схему був складним поршняно з елементами, з яких гщ схема будуеться, псрестае бути актуальною, тому що при наявносп ун!версального автомата самов!дтворним може бути як завго/чо складяий автомат.

2. Теор!я !нформац!йних мереж.

1нформац!Гш! графи. Основним об'ектом доемджень математично! теори шформац!йних мереж е еюнчеши ор!ентован! графи з двома вид!леними множинами вершин, як1 називаються в!дпов1дно вх!дними та вих!дними полюсами. Множили вх!дних 1 вих!дних полюс!в можуть, вза-тал! кажучи, перетинатися.

Нехак ск!нченний ор!ентований граф С (У) мае множиною вх!дних полкгав г.} 1 множинсю в'^дних полюав У-{уг, ..., у«}. Ка-

жу гь, що в!к реаллзуе вЦображення.

v [ Ул »- Уа

п5дмножинн {яу-,...*^ } с X на р!внопотужну Тй шдмножину { уд , Уд} с У, якщо у G(V) можна встановити таку систему шлях!в 7*1, ..., Тк, що для кожного s= 1, 2, к шлях Т, починаеться з вх1дного полюса xt¡ i зак'шчуеться вих'1дним полюсом уд i híhkí два шляхи

з niel множили пшшв не мають жодноТ сшльноТ дуги. Граф G(V) називается 1нформацШним, якщо множина його вх1дних полюс!в сп!впадае з множиною вих!дних полгос!в i сшвпадае з множиною bcíx його вершин, 1нформацтний граф називаеться повним (або ушверсальним). якщо bíh реалЬуе вех воображения множнни своТх вершин на себе.

'Одшею з найважливших характеристик шформацшних графив е його стушнь — максимальний стушнь його вершин. Проблема знаход-жешш оцшки мнимального ступ ¡ню S(n) для класу п-вершинних 1пформацШних граф!в вперше була сформульована у 1962 р. Ю.Г.Решет-няком, який вважав, що вона дор!внюе logj я. У роботах [13, 14] показано, що ця гшотеза не справджуеться.

Теорема 10.

. ■ с.^¡iwsft

Повний тформацшний граф називаеться А-стшким, якщо хожний, отриманий Í3 яього видаленням к вершин i 1нцидентних цкм вершинам дуг, Ыдграф е повним шформацШним графом. Для А-стшких графив виннкае та ж проблема оцшки ступ(нго S(n, k). Мае шеце теорема:

Теорема 11.

S(tt,k) üS(n) +cife

Як для шфомацшних так i для А-спйкнх граф5в наводяться ефективн! методи синтезу, як! дозволяють отринати в!дпов1дний граф мМмалмюго ступ!нга.

1J

КомутацШн! схеми. Абстрактний комутатор К{п, т, <Э) це пристрш з

п вх!дними полюсами, т вихЦними полюсами 1 множиною внутр1шшх

сташв Q, який у кожному 1з сташв Q здшснюе якесь одно-одноз-

начне- воображения ф : X -» У якоТсь шдмножини множини вх!дних

полюет на р'шнопотужну ¡й шдмножкну множини ВИХ1ДНИХ полюс'ш. Ка-

жуть, що перебуваючи у стан! q комутатор К(п, т, 0) реал!зовуе

в!дображенняф?, а множинуФ (2) = и ф, називають множиною вс!х

Чб о

реал!зованих комутатором в1Дображекь.

Нехай £2 •= { К х ,... , Кр }-скшчснна множина абстрактних комута-торш (база). Клас комутацшних схем над базою О визначаеться так:

1. Кожний комутатор К, е £2 е комутацшною схемою над П. й вх1дними та вих!дними полюсами е в!дпов!дно вх!дш та вих!дш полюси комутатора К^

2. Довиьна пара (Б^ 5г) комутац!йних схем над £2 е комутацШною схемою над £2 . !Т кх!дними полюсами е в« вх!дш полюси схем ^ ! а вих!дними — вс! вих!дш полюси схем ^! 52.

3. Якщо 5 — комутацШна схема над £2, а — П вх!дний полюс I р — и вюадний полюс, то результат ототожнювання (склеювання) полюс!в а ! Р у схем! 5 також е комутацшною схемою над П. II вх!дними полюсами е вс1 вх!дн! полюси схеми 5кр1м полюса а! вюадними — вс! вих!дн! полюси схеми $ кр!м полюса р.

4. Немае н!яких шших хомутацшнийх схем над кр!м тих, що мо-жуть бути отриман! як результат скшченного числа застосувань правил побудови, викладених у пунктах 1—3.

Схема Я реал!зуе множину в!дображень £2, якщо для кожного ф е Ф знайдеться такий стан схеми 5, у якому вона реал!зуе ф ! ш в якому своему стан! 5 не реал1зуе жодного в!дображення, яке б не належало Ф.

Основною задачею теорп комутатщйних схем б задача реал!зовност! множин в!дображень:

задано базу £2 г множину в!дображеньФ, треба бстанобити, ни Iснуе схема надО., яка реаягзуе Ф.

У ц!й задач! виступають два незалежш параметри — £2 ! Ф — ! тому

вона може бути сформульована у вид1 двох биьш вузьхих задам: а) заф!ксована база i2 i змшюеться Ф та б) зафшсовапо Ф i змшюеться Q. Коли остановлено, що для певноТ бази П0 i кожного Ф з заданого класу в!дображень Ф icnye схема, яка реалЬуе Ф, пинихае проблема знаход-ження ефектнпного методу синтезу схем, що реал!зують Ф.

У зв'язку з труднощами, що виникають при визначенш класу мнояпш в!дображень, яи реал1зуються класом Bcix схем над П, розглядаються шдкласи цього класу: паралельпо-посл1довш схеми (П(я)-схеми), /:-цшшчш схеми тощо.

Наведемо деяк.1 результата i3 po6iT [25—27], у яких вивчаються Ц1 питания.

Теорема 12. Нехай а (п) — клас Bcix множин в{дображень, що реалгзуються П (п)-схемами. Справедлив; так! тЗердження:

1. Якщо Ф^ а(п) i Ф2 е а(к) то

Ф1' ф2 = {ф • V : ф е Фи v е Ф2} в а(я)

2. Кяас а (п) замхнений щодо операци обернепня.

3. Клас а (п)ке замкнепий щодо онерацт off еднапня, першипу та 61днмштя.

Теорема 13, Нехайп,,..., кк — бег транспозгщи симетричноТгрупи S„, Hj —група {е, i F — клас Bcix таких груп.

Множина вгдображень Ф реалгзуеться П (п) -схемою modi г тглька modi, коли бона представна у вигляд! добутху груп гз F комножетюго зягва або зправа иа якусь тдстановку з S„.

Теорема 14. Нехай a(n,k ),'лножина 8ido6paxenb, що реалгзуються к-цикяжтми схемами, якг мають n Sxidmtx i п внхгдних пояюяв. Для доЗ>лъною k icnye токе щ(к),що клас а (щ ,k) е бластт тдкласом класу а (щ,к+ 1)

Теорема 15 . Яхою б не була повиа база 11 icnye така хножина вгдображень Ф яка ие реализуешься жодкою схемою над Р. .

Тршсгскадж схемн. Одним з найбьльш популярних метод!в синтезу комутацшних схем е метод, що веде свт початок ще b¡a Ч.Клоза i шзнше вдосконалювався рпними авторами. Схеми, що побудоваш за цим методом, називагаться трккаскадними схемами. Досл!дженню трикаскадних cxe«í присвячеш роботи [1S—22]. Основним досягненням, що дозволило встаиовити ц*1лу низку результат стосовно анализу трикаскадних схем е встановлена у [18,19]:

Теорема 16. 1снуе взаеумо-однозначна вгдпоМдшсть mí ж станами трикоскадног схеми i правильным розфарбуванням ребер дводояьних граф'ьв.

!

Завдяки цш теорем, використовуючи техн!ку теори граф1в, встанов-люеться ряд результат, що сгосуються явища блокування у трикаскадних схемах. Зокрема нехай S(n, т) — трикаскадна схема, у якш еле-менти першого касхаду мають п bxíahhx i ш визодних полюав. Справедлива така:

Теорема 17. Якщоу схем! S(n, т)параметрт < 2п— 1, тоякимби не був алгоритм встановлення з'еднань, 6íh не гарантуе уникнсння бло~ куючих стангв. При т i 2п— 1 схема S(n,, т)е неблокуючою, тобто жодним алгоритмом не вдашься досягнути блохуючого стану.

Оцшку середього значения складност! розблокування дае

Теорема 18. g(n,r) < 4 Vr de г — число xoMymamopie першого (третьего) каскаду, а п — гхня gMHicmb.

3. Вибран! проблеми дискретно? математики.

У цьому роздЫ 3Í6pan¡ роботи дистертанта дискретного характеру, як! безпосерднъо не в!дносяться до проблематики роздШв 1 та 2, але cnopiAHeHi з ними тим чи !ншим способом. Наприклад, задач!, як! розг-лядалися для автоматов чи шформац!йних мереж, модмфшуються на 1ншу предметну область, досл!дкуються Гхн! частинн! випадк!, ц!кав! з практично! Ыженерно! точки зору, тощо.

1s

Робота [28] пов'язана з запропонованою В.М.Глушховнм проблематикою вивчення повноти систем операцп! в обчислгавальним тлашинах. Як зазначив В.М.Глушков, поняття поиноти системи операцш визнача-лося в абстрактно-алгоритм!чному плаш; шшими словами, вважплося, що система onepaqifi поана, яхщо за П допомогого можна моделговатл всякий алгоритм перетворення шформаци при належиону кодуСаинг щеТ шформаци. Але у багатьох випадках цей п!дх*1д виявляеться неза-дов!льним 1 б1льш придатним е ншшй, так званий абстрактно-автоматний п1дх!д, що грунтуеться на cxeMi перетворювача шформацш як система взаемодП двох автомата.

Математичний анал!з ц!еТ системи прив!в Б.М.Глушкова до форму-лювання тако! алгебраТчно! задачи

Нехай 8 симетричнш nidzpyni Ря степеню N вибрана якась система mSipHux S — (gt,gM ). Длякожного елементарзРя7юзначимо через 1(р) довжину одного з найкоротших виразгвеяемента р через mSipui еяе-менти. Нехай I — максимальна з довжин Цр), коли р пробггае Sei еле-менти з Ря. Mipoto гнформацшно1 надхишкобостг системи mSipKUX S назибаетъея добуток 1 на число елеменгт'З т у цм систем. Алгебрагчна задала, про яку йдеться, полпгае у знаходженш систем твгрних симетричног твгрупи з мпимальною тформацтною надхиткобшгро.

В.М.Глушков запропонував систему твфних з Mipoio шформацтно! надлншковост! <10 Ж

У робот! [28] запропоновано дс! системи тв'фних симетрично! швгрупи степеню п з Miporo щформацшно! надлишковосп вЗдповЦно <11 N* та < 40 N2 log N. Зауважимо, що хоч у другому випадку м!ра шформацШноТ надлтпкоБост1. б1льша, »¡ж у першому, зате система тв1рних у другому влпадку мае менше елемент!в. У першому випадку мльккть елементн у систе?« TBipHnx дор5вшое N, тод! як у другому ця к1лыисть < 2 ViV.

Mipy шформацшно! надлишковосп можна, у певному розумшш, розглядати як Mipy складности обчислення, коли це обчислення обме-жуеться сличенного множинок» перетоворень, як! виражаготься елемен-тами симетрично! швгрупи Рп.

1нший п5дх1д до офнки М1рч складоност! обчислснь запропонував М.Блюм. Цейпушд даеможлшисть ввести м!ру складносп для штжяни

вс!х частково рекурсивних функций в найбиьш загальному вигляд1, але цл юра не стосуеться окремих шдклаав класу частково рекурсивних функцш. Нами внзначаеться м'фа складност! для дов!льних обчислю-вальних сшсйств рекурсивних фукцш.

Означсиня. Нехан Р(г,х) — дов1льна частково рекурсивна функц1я. М!рою схладност1 для Р1},х) називаеться така частково рекурсивна функция *У(/,дг), що: 1) область визначення функцШ Р(1,х) та сшвпадаготь 12) граф!к функци*? (»',*•) е рекурсивним.

Заузажимо, що яйцо на Г(!,х) накласти обмеження, щоб вона була ушасрсальною для класу вах одноаргументних частково-рекурсивних функцШ 1 щоб для не! була справедливою теорема Клш1 про »терацио, то отримаемо блюм5вську М1ру складностК В роботах [29, 55] вивчаються основш власгквост! введено! »при складносп Показано, що певш влаетивост! всгановлеш спершу для блюмшськоТ ьпри складносп на-спраад! справедлив! для бшш охоплюючого поняття м«ри. Зокрема справедливими е теореми:

Теорема 19. Для довглъног частково рекурсивног фунщп Р(г^) гснуе,частково рекурсивна функщя ¡,х) , яка е для негмрою складаог стю.

Теорема 20. Для довгльно? частково рекурсивног фунщп те и м!ри скяадностг у¥(г,х) можливе ефективне мажорубанця

а)Р({,х) в(дноснох¥(1,х).

б) Мдносно ?(г,х), якир графы в рекурсибним.

I (

Теорема 21. Нехай Р(г,х) — частково рекурсивна фуикцЫ Ц

мг'ра складности така, що для ИоМАъно! загалрт рекурсивно} фунхцН'

№

В И € * > Я*)

I Ч(п,х) бтначена майже всюдн, ТоЫ для довиьноТ загально рекурсивнаГ функци ч>(х) ¡снуе така загально рекурсивна функцгя Ь(х),

що складность обчислення всякоо фунщп tз сомеистЗа F(b(i),x) для 6cix х болыиа w(x).

Теорема 22. Нехсй F(i,x) функц(я универсальна для класу dcix 'толково рскурсивних функцгй, Kl'(i,x) — ii'w'pa склаоносггл. Для довольно? загаяьно рекурсивноо функцп r(x,y) icnye така загально ргкурсиСна функцгя у(х), що taiye натуральна число п таке, що у(х) ~ F(п,х), i для вах х, больших за п, справедлива nepiGnicmb

Щщх) > г (х.У {п,х)).

Перечислен! вище, та ряд шших теорем, встановлених дисертантом, дають загальну характеристику впровадженого поияття iiipn склад-nocri. При накладешп на нього додаткових обмежень, яга перетпорюгать його на блюм1вську Mipy складностю, з теорем випливають як наоидох так! в!дом1 теоремк.як теорема М.Рабша про кнування пк завгодно складно обчислюваних функцш, теорема М.Блюна про пряскорення та in.

Роботи [30, 31, 32] примикають до проблематики теорп шформацшнийх мереж. Це роботи теоретико-графового характеру.

Робота [30] вшшкла з практичных потреб автоматизацн контролю параметра виробнкчих процейв. При цьому виникае потреба побудови складнкх шформацшних мереж, як! з'еднують теркторшльно рознесеш давач!, пристроТ комутаци та комп'ютер. 1з численкх конфцурацш мереж практичне застосування знаходять т!лькн ма^стральш та дере-вовядн! структура. Математична задача, яка виникае для таких структур, це в!дома задача ком!вояжера, розз'язок якоТ фйктично вимагае перебору вс!х варгэнетв маршрут 1, отже, е дуже гром13дким. Разом з тим, практичне зд!йснення мереж! потребуе не абсолютного мшшуму довжини кабелю, а т1льки такого вар!анту, яхкй в!др!зняеться в!д мшшального не бш.ше, нЬк на задану величину. Пропонусться метод, який позволяв, не вдаючнсь до повного перебору, знаходяти вар!анти сполучень, для яких ножна встанояитилнзск! аькя копи в!др!зняються в!д мЬпмального. Цей метод ycnirono застосовуввзся при прак-пггош ггобу-дов! мереж збору 1н!ц!а'птвних сигнал|'в для ЛСУТП i дав добр! резуль-тати.

Скшченш графи, як коыбшаторш об'екти, характеризуються набором napaMCTpin таких як: киьгасть вершин, кш>к1сть ребер, стешнь вершин (графа); хрояатичняе число, цихломатичне число, i т.п. Щ параметра, що с важливими для внутршньоТ проблематики теорп граф1в як мат;матично1* дисциплин, луже часто використовують в застосовних аспектах Teopifí графш, зокрема, при побудов1 шформацШних мереж. Робота [31, 32] присв{чеш досл1'д:гсеоню таких napaMeTpis скшченних граф1в як пцльшсть (число БнутрипньоТ ctíííkoctí), всесум!жшсть (число зовн1шньоТ ctíííkoctí) та охоплення.

Щиьшстю графа G називаеться число вершин максимального повно-го шдграфа графа G, всесушжшстю — таке мппмальнг число вершин графа G, що кожна вершина графа G сум^жна хоча б з одшею 13 цих вершин.

Позначимо через L(n, ср) Р(н, Р) та Z(t¡, ср, Ь,) п1дножини звичайних (неоркнтованих, без петель i крайних ребер) n-вершинних граф1в з дакими щиьшстю ср, всесушжшстю ¡3 та пцльшстю й всесум1жшстю ф i р bíahobíaho. Через e(L), е(Р) та e(Z) нозпачатимемо число ребер графа з Ь(и,ф), Р{п, Р ) та Р(п, ф, Р) BÍAnoB¡AHo.

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

Мають м1сце таи результата:

Теорема 23.

\ (2«+ ф* - Зф) S e(L) 5 \ [и(я - 1) - *ф(* - 1) - Ikr)

%е. — = к + — i г< ф ф ф

о

Теорема 24.

и- Ь£ e(P)á

«У 1} якщо Р = 1

\ якщо р = 2 (W-p + j)(n-p) ^ор^З

Теорема 25.

^(2л + ф2-Зф)<;

- 1) - *!(*! - 1)(Ф - 1) - 2к1Г1] якща ¡3 = 1 ¿[«(я - 1) - Кк - 1)Ф - 2Лт], якщо Р = 2

- р) (я - р + 1) + к£кг - 1)ф - 1к1ГЬ яйцо ¡1 > 3

де значения п, ф, р, к, г, к,, гг, кг, гг зб'язаш сп1бв1дношенням 2 = к + - ! г< ф; + 1 п<Ф~1;

Ф ф ф—1 ф — 1

п ~ В г . гг ! - ,, ,„

------= Лг Н--1 п < ф .

Ф Ф

Наведен! нижш й верхи! офнкк не можуть бути покращеними, то?,г/ що для кожного розглянутого випадку збудоваш прихслади т.з. екстрс-мальниъх граф1в, тобто таких граф!в, додазанкя або в1лшмгитя у яккх хоча б одного ребра виводить Тх 13 задакого класу,! показано, що саме для цих екстремальних граф1в у теоремах 23—25 справджуються р!вност{.

Робота [32] присвячена внвченню одного з важливих параметр!» граф1в — охоплення. Скшченний ор1'ентований граф без петель! кратких ребер назнваеться графом охоплення т якщо у ньому 1сиуе хоч бн один простий цикл довжянк т! не ¡снуе цйхл!в меншоТдовжини. В робсш про-понусться певний конструктнвний метод породження клаав граф1в охоплення 5 та б. Цей метод названий розшнренням циклами, полягае, грубо кажучи, у тому, що хожну вершину графа С замшюють простим циклом С„ I вершин п цих цккл!в пов'язукэть мЬк собою дугами у в1дпов!дност1 з тим, як були пов'язаш М1>к собою вершини графа С. З'ясо-вано, коли розширення графив, що мають охоплення 5 та б циклами в!дпов!дно довясинн 5 та б знову дае графи, що мають охоплення 5 та б. Очевидно, що не кожний граф в, що мае охоплення 5 та 6, в результат! розпшрення в1дпов!дними циклами знову дае граф цього ж охоплення, для щього С повинен задов эльнитн певш вимогк. Наша операция розширення е такою, що колн граф С задовольняе вказан! зимсгтг, то I граф, отриманкй як результат розширешгя, також задовельняе ц! ж вимоги, тобто !теруючн операцЬо розшнреяня отримуемо н^Ит^еипу

множину граф!в, що мають дане охоплення (5 чи 6). Отримана множина граф1в, що мають охоплення б.може, певним чином, бути цжавою для тих, гго згймаеться проблемою К.3аранкевича: яку каксимаяьну к;льхшг,ь ребер можуть иапш дйодольт графи, у яких не генуе циклИ Вовхюш А. Отриманин в результьат! розширення 3-контура С<-циклами дподольний 3-регулярний граф з числом вершин 181 числом ребер 27 ма-бугь наближаеться до графа Заранкепича.

У робот1.[33] встановлюеться закон розпод5лу та фактор!альн! момента гипадкояо! матрищ, шдуховано! випадковим воображениям та вг.'падг.овим розбкттям сшнченоТ множини.

Кехай А — ехшчена и-множина, Ф — випадкове Т(ги ..., вОображения, яке р!вноймов!рно вибираеться з класу Т(ги ..., взашо однозкачних в^ображень множини А на себе, що мають цикли домешшг! 2 х.г < ... < 5 — анпадкове ..., —розбиття, яке р!ш;оймов1рно вибираеться з класу ..., *г) вс!х розбитпв множини ЛС^и ^и... = 0 для вс^х **/,1^ = ^,1«» 1,2,...

...г). Нехай © = ©(Ф,5) = |4у|-випадкова (Т(г1 ... г, ), Я ... , $г )) ыатриця, у яко! «= | Ф5, п | випадкова величина, що дор!внюе хиькосп числа елемент1в множини 5,, як1 при в1Дображенш Ф попадать у множину SJ [ / - 1, 2, ... , г ; Ф е ,... , 5 5 е ,... , *,)] Задача полягае у знаходженн! закону розпод1лу 1

фахтр!альних моиент!в матриц! 8 .

Цю задачу разглядав Б.А.Севастьяиов ! вегановив вказаш закони, використовуючи схладну хомбшаторну техшку. У робот! [33] ця задача розв'язуеться на основ! просто! теоретико-графово! модел! з оикористанням теореми де Брейна для п!драхунку числа ейлерових циюив^ графа. Основн! результате роботи [33] аналопчш результатам Б.А.Севастьянова з певними уточнениями останнЬс.

Нарешт!, роботи [34, 35] присвячен! одшй гшотез!, сформульованШ б.Лосем, яка <>ере свш початок в!д проблем розпод!лу пам'ят! в ЕОМ, що вивчалися З.Павляком. Нами доведено, що ця г!потеза не справд-жуеться (побудовано контрприклад) 1, б!льш того, що всяк!!! ослабления не справджуються, яыцо вимагати щоб нала м!сце умова лохаль-ност!.

Б1лып точно: характеристичною множиною (£-множина) я-ки в!дношень еквЬалентносп Я, на иножищ А називаеться множила 0-1 посл1довностей.

Ь(Й1.....Д-) = {< Хп^Ь) Хк{а,Ъ) > : (а,Ь) е А!)с {0,1}а

де Хя, означав зарактеристичну функцт на А2. Гшотеза Лося поляга-

ла у тому, що множина С с {0, е Е — множиною.якщо кожну пару и елемент1в можпа розширити, додавши до не! не биьше 4 слеиегтв так, що отримана множина буде Е-множиною. Насправд!, мае глкце:

Теорема 26. Для довольного натурального к гснуе С с {0,1}" глака, що С не е Е-яножиног, але кожна и к-тдпножнпа ?,иэже бути розшнрепа (елешптами з С) до Е-множшт.

Встановлено ряд 1нших факторш, що стосуються Е-мпожин, пзприаклад:

Теорема 27. Дов1льна множина С с {0,1}" що тмстцтъ одничний елепепт » один тнЫальний ележнт е Е-множиною.

Ця теорема е уэагальненням теореми Лося, яка стверджувала, пто довольна множина з однничним I пульовим елементом е Е-множиною. Очевидпо, що якщо яульовий елемент належит до С, то вше у шй единим М1пшальнии елементом.

Теорема 23. Жадна множина С с {0,1}" що теттть ргвно два ттмаяъних елеттти не в Е-множиною.

Теорема 29. Якщо Е-тюжина тстить к елгпенппв, то бона ¡г характеристичною множимоюрелщтпо!системи потуююстг не больше2к.

Теорема 30. Кожна ортогональна множила С с {0,1}" , що яае бххьше двох еяементглв, е Е-множиною.

Заключения.

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

К1льк1сгь стор!нок, видиених у доповЩ для викладу результат!в,не заводи в1дпов!дае 1х важливост!. Результати, що стали широко в!домими як розв'язки принципових задач завдяки !х публтацп у багатьох видан-нях — шдручниках, пособниках, монограф'шх — викладаються биьш конспективно, натом!сгь результати, що стотуються биьш вузышх проблемные т1льки формулюютьея б!льш детально, але 1нод!, для свого розумшня, вимагають наведения й в1дпов1дних означень. Об'ем допов»д1 не дозволяв викласти б!льш детально вах результатов, що м!стяться у роботах, включених в дисертацш, тому хочемо звернути увагу тих, хто ц!кавиться застосуванням наших результат!в, що можуть дата нов! па-прямки, на робота [27, 39,43,46, 47, 48, 50,52].

А!тература

I. Основы! науков! роботи включен! у дисертац'но

1. Теория автомат!в

1. Кратко М.И. Об одном классе исчислений Поста. — Доклады АН СССР, 165, 5,1965, 994—995.

2. Кратко М.И. Формальные исчисления Поста и конечные автоматы. — Проблемы кибернетики, 17, 1966, 41—65.

3. Кратко М.И. Регуляр]гые и стабильные итеративные системы. — Проблемы кибернетики, 19,1967, 95—106.

4. Кратко М.И., Ребип О.М. Машины Тьюринга работающие на плоскости и стабильные итеративныые системы. — Кибернетика, 5, 1977.

5. Кратко М.И. О сводимости комбинаторной проблемы Поста к некоторым массовым проблемам в теории автоматов.'— Вычислительные системы. № 9 — Новосибирск, 1963, 71—73.

6. Кратко М.И. Алгоритмическая неразрешимость одной задачи из теории конечных автоматов. — Дисхретный анализ, 2, Новосибирск, 1964, 37-41.

7. Кратко М.И, Алг оритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. — Доклады АН СССР, 155,1, 1964.

8. Кратко М.И. О существовании нерекурсивных базисов конечных автоматов. — Алгебра и логика, 3, 2, 1964, 33—44.

9. Кратко М.И., Ребин О.М, Проблема декомпозицн регулярных !теративних автомагш. —Допов!д1 АН УРСР, сер!я А, 9,1974.

10. Кратко М.И. Автоматные модели самовоспроизведения, — В кн.: Математические методы в биологии, К., 1977.

2. Теор!а !нфорнац!йних иерея:

11. Кратко МЛ. О степени информационного графа. — Вычислительные системы, 34, Новосибирск, 1969, 64—70.

12. Кратко М.И. Информационные графы. — Сибирский математический журнал, 11, 5, 1970,1093—1097.

13. Кратко М.И. Замечание о верхней оценке степени информационных графов. — Сибирский математический журнал, 18, 5, 1977, 1192—1193.

14. Кратко М.И., Лритуяа М.Г. Информационные сети. — Препринт 81.38, Ин-т математики АН УССР, К., 1981, 36 с.

15. Kratko M.I., PrituJa M.G. Universal networks for informational exchanges. — Four Formator Symposium, Prague, Academia, 1983, 303— 314.

16. КраткоМ.И.,ПрнтулаМ.Г. О системах маршрутов на графах. — В кн.: Архитектура ЭВМ и численные методы, М,, 1988, 77—89.

17. Кратко М.И. Простое доказательство теорем Слепяна-Дыогида и Пола. — В кн.: Теория телетрафика и информационные сети, М., 1977.

18. Кратко М.И. О числе переключений, необходимых для разблокировки трехкаскадного коммутатора. — Доклады АН СССР, 277, 1, 1976, 54—56.

19. Kratko M.I., PavJettko V.A. Combinatorial aspects of the mathematical theory of commutational circuits. — Fundamentals of teletraffic theory, Moscow, 1984, 265-273.

20. Кратко М.И., Павленко В. А. Трехкаскадные схемы. — Препринт 84.8, Ин-т математики АН УССР, К., 1984, 36 с.

21. Кратко М.И., Павленко В.А. О случайных раскрасках ребер двудольных графов. — В кн.: Применение аналитических методов в вероятностных задачах, К., 1986, с. 80—87.

22. Кратко М.И., Притуяа М.Г. Тестирование сетей коммутации. — Методы и системы технической диагностки, 3, Саратов, 1984, 24—31.

23. Кратко М.И., Притула М.Г. О принципе нулей и единиц для сетей Сортировки. — Методы и системы технической диагностики, 4, Саратов, 1985, J1—56.

24. Кратко М.И., Павленко В.А. Анализ коммутационных схем. — Препринт 83.48, Ин-т математики АН УССР, К., 1983, 44 с.

25. КраткоМ.И., Павленко В.А. О множествах подстановок, порождаемых коммутационными сетями. — Комбинаторные исследования графов и сетей. Препринт 81.15, Ин-т математики АН УССР, К., 1981, 21— 33.

26. Кратко М.И., Павленко В.А. О системах маршрутов в орграфах. —

В кн.: Труды 2 Международного семинара по теории телетрафика и компьютерному моделированию, часть 1, М., 1989, 25—28.

27. БагилаковЕ.П., Кратко М.И. Синтез структур микропроцессоров и микропроцессорных систем. — В кн.: Tanulmanyok МТА Szamitastechnikai es Automatizalasi Kutato Intezet, Budapest, 91/1978, c. 39-60.

3. Вибран! проблешг дискретно! математики

28. Кратко М.И., Плесневич Г.С. Об одной задаче В.М.Глушкова. — Кибернетика, 2, 1967, с. 97.

29. KratkoM.I. On the axiomatic definition of the concept of computational complexity. — 5 International Congress of Logiic, Metodology and Philosophy of Science. Contributed Papers, London; Ont, Canada, 1975.

30. Литвинов A.M., Кратко М.И., Петренко В. А. Магистральный канал связи для центральных структур. — В кн.: Системы и средства автоматизации производств и управления. Научные труды Института автоматики, т. 6, М., 1977, 218—226.

31. Винниченко Н.Г., Кратко М.И. Верхняя и нижняя оценки числа ребер графа с данными плотностью и числом всесмежности. — Техническая кибернетика, Изд. Ин-та кибернетики АН УССР, К., 1971, с. 178— 186.

32. Винниченко Н.Г., Кратко М.И. О расширении графов циклами. — Комбинаторно-алгебраические методы в прикладной математике, Горький, 1986, 22—39.

33. Кратко М.И., Строк В.В. О случайных отображениях и разбиениях конечных множеств. — В кн.: Аналитические методы в теории вероятностей, К., 1979, 80—84.

34. Кратко M.I. Характеристичш множини реляцшшшс систем. — До-пов1Д1 АН УРСР, сер'ш А, 7, 1984, 13-15.

35. Kratko M.I. On characteristic sets of a system of equivalence relations, — Colloquium mathematicum, v.55, № 1, 5—9.

II. Irani публЬгацй* за темою дисертзцП

36. Кратко М.И. Одиин класс исчислений Поста. — Резюме сообщений 7 Всесоюзного коллоквиума по общей алгебре, Кишинев, 1965, 5S-59.

3 7. Барздинь Я.М., Кратко М.И., Трахтенброт Б. А. Проблема универсальности в теории автоматов. — Тезисы 3 Всесоюзной конференции по автоматическому управлению, 1965.

38. Кратко М.И. Вопросы распознавания реализуемости в теории конечных автоматов. — Резюме сообщений Международного конгресса математиков в Москве, секция 13, 1966, с.23.

39. Плесневич Г.С., Кратко М.И. О декомпозиции групповых итеративных автоматов. — Резюме сообщений 9 Всесоюзного коллоквиума по общей алгебре, Гомель, 1968.

40. Кратко М.И. Об одной задаче Ю.Г.Решетняка. — Тезисы дохладов 1 Всесоюзной конференции по теоретической кибернетике, Новосибирск, 1969.

41. Кратко М.И. Коммутаторные сети, — Тезисы докладов 2 Всесоюзной конференции по теоретической кибернетике, Новосибирск, 1971.

42. Кратко М.И. Анализ коммутаторных схем методами теории графов.

— Тезисы докладов 3 Всесоюзной конференции по проблемам теоретической кибернетики, Новосибирск, 1974.

43. Кратко М.И. Некоторые методологические вопросы теории автоматов и алгоритмов. — Тезисы сообщений 7 Всесоюзного симпозиума по логике и методо \огии науки, Киев, 1976.

44. Кратко М.И. Обобщение Блюмовской меры сложности вычислений.

— Тезисы докладов и сообщений 4 Всесоюзной конференции по математической логике, Кишинев, 1976.

45. Кратко М.И., Строк В.В. Об одном оптимальном способе соединения ЭВМ в многомашинных комплексах. — Материалы конференции «Развитие технических наук в республике и использование их оезультатов», секция Вычислительная техника, Вильнюс, 1977.

46. Кратко М.И. Проблема самовоспроизведения в теории автоматов.

— Тезисы докладов 4 Всесоюзной конференции по теоретической кибернетике, Новосибирск, 1977.

47. Кратко М.И. Информационные сети и параллельные вычисления. — Тезисы докладов школы-семинара «Параллельное программирование и высокопроизводительные системы», Киев, 1977.

48. Кратко М.И., Пяесневт Т.С. О выводимости константных литер из

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

49. Кратко М.И., Павленко В.А. Множества отображений порождаемые коммутационными схемами. — Тезисы доклядов 5 Всесоюзной ксп-ферепцпи по проблемам теоретической кибернетики, Новосибирск, 1980.

50. Литвинов А.М., Кратко М.И. Анализ способов подключения элек-тродоа з тсрмоэлектролнтнческих гигрометрах. — Тезисы докладов Республиканской научно-технической конференции «Структурные методы повышения точности, быстродействия и чувствительности измерительных устройств и систем» , Киев, 1981.

51. Кратко М.И., ЯцишипЮ.В. Об оценках сложности вычислений. — Тезисы докладов 7 Всесоюзной конференции по математической логике, Нозсснбкрск, 1934.

52. Кратка М.И., Завьялов Ю.Г. Оптимизация канала связи при контроле микроклимата. — Материалы 4 Всесоюзной конференции «Автоматизация контроля к прогнозирования загрязнения воздуха $, Киев, 1935.

53. Кратко М.И., Яцишин Ю.В. Некоторые свойства обобщенной меры сложности вычислений. — Тезисы докладов 8 Всесоюзной конференции по математической логике, Москва, 1986.

54. Кратко М.И., Яциишн Ю.В. Некоторые теоремы общей теории сложности вычислений. — Тезисы докладов 9 Всесоюзного совещания по лотке, методологии и философии науки, Москва, 1986.

55. Кратко М.1., Яцишин Ю.В. Склядшсть обчислення рекурсивних фупкцш. — Допов!д5 АН УРСР, сер'м А, №2,1987, 17—20.

56. Кратко М.И. О характеристических множествах системы отношений эквивалентности (к проблеме Лося). — Материалы Всесоюзного семинара по дискретной математике и ее приложениям, Москва, 1986.

57. Воебодт В.В., КраткоМ.1. ГнформацШш мереж! та Тх застосуванпя. — Вюпкк АН УРСР, 9, 1988.

58. Кратко М.И., Хрузип А.Н. Неразрешимость проблемы реализуемости и полноты в классе инициальных автоматов Реддипга. В кн.: Проблемы теоретической кибернетики. Тезисы докладов XI Всесоюзной конференции. Волгоград, 1990, часть 1(1), с. 63.