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

Р Г Б ОД

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 519.714.2

Колпаков Роман Максимович

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

Специальность 01.01.09 — математическая кибернетика

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

Москва — 1994

¿V- /

Работа выполнена на кафедре дискретной математики механико-математического факультета МГУ им. М.В.Ломоносов!

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

доцент А.Б. Угольников.

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

В М. Сидельников, — кандидат физико-математических не H.H. Нурмеев.

Ведущая: организация — Институт математики

Сибирского отделения РАН.

■ [Ц-ОРЩ diSW

Защита диссертации состоится " I I "ЩчХМ | 1994 в час. мин. на заседании Специализированного сов<

Д.053.05.05 по математике при МГУ им. М.В. Ломоносова адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, механи математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке механи

математического факультета МГУ (14 эт! Автореферат разослан "J__L"

А

1994 г.

Ученый секретарь Специализированного совета. Д.053.05.05 при МГУ д. ф.-м. и., профессор / В.Н. Чубарик

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

Актуальность темы

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

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

* См., напр.: Гашков С. Б. О сложности приближенного вычисления действительных чисел схемами и формулами в различных базисах //Дискретная математика, 1990. т. 2. Лл 4. 26-46.

** Бух&раев Р. Г. Основы теории вероятностных автоматов. Москва, "Наука". 1985.

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

Случайным ходом, или булевой случайной величиной, назь вается случайная величина с двумя возможными значениями и 1. Большое значение для синтеза управляемых источников сл] чайных кодов имеет задача моделирования булевых случайны величин на основе некоторого исходного семейства элементарны случайных кодов. Центральное место в этой задаче занимает пс нятие преобразователя вероятностных распределений как некс торой управляющей системы, перерабатывающей элементарны случайные коды в другие булевы случайные величины. В диссер тации изучаются два типа преобразователей вероятностных рас пределений, исследовавшихся ранее в научной литературе: фун* ции алгебры логики и вероятностные контактные сети. Поскол! к у распределение вероятностей булевой случайной величины он нозначно задается вероятностью принятия ею значения 1, задач моделирования булевых случайных величин допускает перефор мулировку в терминах порождения чисел в различных класса преобразователей вероятностных распределений.

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

* См., напр.: Захаров В.М., Салимов Ф.И. К теории cTpyi турного синтеза детерминированных • преобразователей вероя-] ности //Problems of Control and Information Theory, Vol. 6 (2 pp. 137-148 (1977); Нурмеев H.H. О сложности реализации пр<

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

Цель работы

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

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

обраэователей вероятностей схемами из функциональных элементов //Методы и системы тех. диагностики (межвуз. сборник научных трудов), Саратов, 1993. вып. 18, 131-132.

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

Научная в. лиэна

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

Теоретическая и практическая ценность Работа носит теоретический характер. Разработанные в ди сертации методы могут быть использованы для доказательст: порождаемости и оценки сложности порождения множеств рац опальных чисел в более узких классах булевых функций, а т^кз для получения более сильных оценок сложности порождения р циокальных чисел в классе вероятностных контактных тг-сете Примененная в диссертации методика доказательства конечна порожденности множеств пятирк -.о- и семирично-рационалып чисел в классе вероятностных контактных сетей произвольно вида является полезной для исследования конечной порожденн сти в этом классе множеств р-ично рациональных чисел при пр стых р, больших 7. Полученные в диссертации результаты мог; найти применение при моделировании генераторов случайных ч сел на ЭВМ.

Методика исследования

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

Апробация результатов

Результаты диссертации докладывались на Школе-семинаре по синтезу и сложности управляющих систем (Нижний Новгород,

1992), IV Межгосударственном семинар>е по дискретной математике и ее приложениям (Москва, 1993), X Международной конференции по проблемам теоретической кибернетики (Саратов,

1993), на научных семинарах C.B. Яблонского по математическим вопросам кибернетики и О. Б. Лупанова по синтезу управляющих систем, а также на других школах и семинарах.

Публикации

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

Объем и структура работы

Диссертация состоит из введения, четырех глав, разбитых на 9 параграфов, и списка литературы, включающего 27 наименований. Общий объем работы составляет 86 страниц. Изложение материала проиллюстрировано 4 рисунками.

Содержание работы

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

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

В главе 1 изучается порождение рациональных чисел бул< выми функциями. Число о 6 (0,1) порождается множеством М < С (0,1) относительно булевой функции /(ж 1,... ,хп), если сущ« ствуют р1, ..., рп € М такие, что

а= У^ (Р1)®1 • • •(Рп)^п/(°'1» • • • ><*")>

(»»,....¿^{0,1}"

где

/ Р, если а = 1;

\1-р, если а = 0.

Другими словами, число а порождается множеством чисел М 01 носительно функции /(«1,... , яп), если найдутся числа рг, ..., р из М такие, что, подавая вместо переменной г;, 1 = 1, ..., 7 на соответствующий вход функционального элемента, реализ] ющего функцию /(«1,... , значение 1 с вероятностью р{ значение 0 с вероятностью 1 — р; соответственно, мы получи] на выходе этого элемента значение 1 с вероятностью, равной (предполагается, что значения, подаваемые на входы элемент« не зависят друг от друга). Число а порождается множеством Л в некотором классе булевых функций 1г, если оно порождаете множеством М относительно какой-либо функции из Р. Пр этом сложность £&(а) порождения числа а множеством М классе Р определяется как минимальное возможное число пер< менных у такой функции. Множество А С (0, I) порождаете

множеством М в классе Р, если множество М порождает в классе Р любое число из А. При этом, если множество А конечно, то положим = Величина (А) называется

сложностью порождения множества А множеством М в классе Р. В параграфе 2 главы 1 доказано, что при п ^ к — 2 > 1 сложность

яг/1 V, Г 1 2 - 1 "1

порождения множества п)] = ^ , ,... , —^— ^ систе-

мой чисел 0[(1е, 1)] = ^ £> • • • » в классе всех булевых

функций равна п + 1.

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

-У"* (Р1)|Т1 • • • (рл)<г„/(<п, • • • ,0п) можно представить в ("1.....<£Уе{о,1}"

виде полинома с целочисленными коэффициентами от переменных р\, ..., рп • Обозначим коэффициент этого полинома при одночлене р\ .. .рп через к(/). В параграфе 3 главы 1 на основе приведенных оценок доказано, что при простом к > 3 множество £?[£] всех &-ично рациональных чисел в интервале (0, 1) порождается системой чисел 0[(Л:,1)],в некотором классе булевых функций Р только тогда, когда для любого натурального л в классе Р найдется функция д(х\,... , ач) такая, что пи /с(^) делится на к. В качестве следствия из этого результата получено, что, если класс Р является замыканием относительна операции бесповторной суперпозиции некоторой системы булевых функций, не содержащей констант,то при простом к > 3 множество С7[А:] порождается системой чисел 1)] в классе Р только тогда, когда эта система содержит функцию д такую, что к(д) делится на к. Отметим, что условие отсутствия в системе булевых функций констант не является существенным ограничением, поскольку

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

В главе 2 вводятся понятия вероятностной контактной сети и порождения чисел вероятностными контактными сетями. Под вероятностной контактной сетью понимается двухполюсная сильно связная сеть, всем ребрам которой (называемым контактами) однозначным образом приписываются независимые булевы случайные величины (называемые проводимостями этих контактов). Вероятность принятия значения 1 проводимостью контакта вероятностной контактной сети называется вероятностью проводимости этого контакта. Проводимость вероятностной контактной сети определяется как булева случайная величина, принимающая значение 1 в том и только том случае, если между полюсами сети существует цепь из контактов с проводимостями, равными 1. Вероятность принятия значения 1 проводимостью вероятностной контактной сети называется вероятностью проводимости этой сети. Число а € (0,1) порождается множеством чисел М С (О, 1) в некотором классе вероятностных контактных сетей Ф, если существует сеть из класса Ф такая, что вероятность проводимости всех ее контактов принадлежат множеству М, а вероятность проводимости самой сети равна а. При этом сложность порождения числа а множеством М в клас-

се Ф определяется как минимальное возможное число контактов у такой сети. Множество А С (0, 1) порождается множеством М в классе Ф, если множество М порождает в классе Ф любое число из А. Множество чисел называется конечно порожденным в классе Ф, если оно порождается в классе Ф некоторым своим конечным подмножеством. На множестве всех вероятностных контактных

■ ■тей вводится операция суперпозиции, определяемая как опера-

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

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

В главе 3 рассматривается порождение рациональных чисел в классе П всех вероятностных контактных тг-сетей, т. е. в классе, являющемся замыканием отноститеяьно операции суперпозиции системы вероятностных контактных сетей, состоящей из тривиальной сети (сети, имеющей один контакт) н сетей, изображенных на рис. 1. Доказана конечная порожденность в классе П множеств <?И для составных I. При Этом приведены конечные подмножества, порождающие эти множества в классе П, н указана сложность порождения рациональных чисел данными подмножествами.

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

о-

•о

Рис. 1.

различные простые числа. Обозначим через С?[ро,Р1,..

г. - т

жество всех рациональных чисел вида О < „ „-^

Ро Р1 • • • Ра

..,Рк) мно-йГ < 1. где

т <Е N и щ £ Z+, г — 0, 1, к. Отметим, что для любого

составного числа I ^ 2 имеем

G[í] = G[p0,pi, ••• ,Р*],

где ро, pi, рл — все различные простые делители числа I. Пусть Ао, Ai, ..., Ajt — натуральные числа. Обозначим через G[(p0, До), (pi, Ai),..., (р*, А*)] подмножество

Г . . 1 . -1\

| 1... pí- ''''' P¿°pí'... pi- f множества G[po, pi,.. ., p*].

В параграфе 1 главы 3 доказано, что, если ро равно 2 или 3, то множество G[po,Pi, • • •, f>k] порождается в классе П подмножеством Мо = С?[(ро, 1), (pi, Ai),.. -, (р*, А*)] при любых натуральных Al, ..., Afc и при этом для любого числа n.m-д-г- из

Ро Pi • • -Pjb

G(po,pi,___,pjb] выполняется неравенство

В параграфе 2 главы 3 установлено, что, если ро > 3, то при к ^ 1 множество G[po,pi, —,pt] порождается в классе П подмножеством G[(po, 7о), (pi, Ti),.. •, (р*, Tt)]i где

Г1пЗ Г1

70 = — Vi bgpo pi

71 = J^Pi j > » — 1, • • •, fc, . r = [loga Ро].

В параграфе 3 главы 3 исследуется вопрос о сложности порождения в классе П чисел из множеств G[po, Pi, - • •, Рк], где ро > 3 и Jfc ^ 1. Показано, что для любого натурального г ^ [loga Ро]

множество О[ро,р1,___порождается подмножеством Мг

- С![(ро,7о(г)), (рг,7г(г)),..., (рк,7*(»-))], где

7о(г) = ^Рг Рг| ,

7»'(Г) = 1пр°| > » = 1, • - •,

причем для любого числа п -щ- из О[ро, ,..., р*] выпол-

Ро Рг ■•-Рк

няется неравенство

1Ъ- (ро0р?™--рг) < 1 Ьбзро1063^"1--^)-

4 ' г+1

Из полученных в главе 3 {результатов вытекает, что

а) если ро — 2, то для любого с > О существует конечное

подмножество М(с) множества (7[ро,р 1, ■ • ■ ,рк\ такое, что любое

число По -ггг мз Р1) • • •! Рк] порождается М(е) в клас-

Ро Р\ •••Рк се П и удовлетворяет неравенству

б) если ро ^ 3, то для любого е -> 0 существует конечное

подмножество Л/(с) множества <-г[ро, Я) - • • >Рк] такое, что любое

число п „"^-й;- из вГро, рг,... ,р*] порождается М(г) в клас-

Ро Р1 •••Рк се П и удовлетворяет неравенству

В параграфе 1 главы 4 устанавливается конечная порожден-ность множеств Сг[5] и О'[7] в более широких, чем класс П, классах вероятностных контактных сетей. Рассматриваются класс Ф, являющийся замыканием системы, состоящей из тривиальной сети и сетей, изображенных на рис. 1 и 2, и класс Г2, являющийся

эаиыкинием системы, состоящей иэ тривиальной сети и сетей, изображенных на рис. 1 и 3. Доказано, что множество С?[5] порождается подмножеством (7[(5, 7)] в классе Ф и множество <?[7] порождается подмножеством <3[(7,8)] в классе П. При этом получены верхние оценки сложности порождения чисел из <3[5] и С?[7] данными подмножествами.

В параграфе 2 главы 4 приведен пример множества чисел, не являющегося конечно порожденным в классе П, но конечно порожденного в более широком, чем П, классе вероятностных контактных сетей. В качестве такого множества берется множество всех рациональных чисел вида 0 < ^пх^п* 1> где (т,2п13па) = 1, П1 £ 'ЕЛ и пг £ N. Показано что это множество не является конечно порожденным в классе Л, но в то же время порождается некоторым своим конечным подмножеством в классе, представляющем собой замыкание системы, состоящей из тривиальной сети и сетей, изображенных на рис. 1 и 4.

Автор глубоко признателен профессору О.Б. Лупанову и доценту A.B. Угольникову за постановку задач и постоянное внимание к работе.

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

1. Колпаков Р. М. О порождении некоторых классов рациональных чисел вероятностными 7г-сетями//Вестн. Моск. ун-та. Сер. 1. Матем. Механ. 1991. iVa 2, 27-30.

2. Колпаков Р. М. О порождении рациональных чисел вероятностными контактными сетями//Вестн. Моск. ун-та. Сер. 1. Матем. Механ. 1992. Ni 5, 46-52.

3. Колпаков Р. М. Об оценках сложности порождения рациональных чисел вероятностными контактными 7Г-сетями//Вестн. Моск. ун-та. Сер. 1. Матем. Механ. 1992. Ni 6, 62-65.

4. Колпаков Р. М. О порождении рациональных чисел вероятностными контактными 7Г-сетями//Дискретная математика. 1994. Ni 3.

5. Колпаков Р. М. О сложности порождения рациональных чисел булевыми функциями//Методы и системы тех. диагностики (межвуз. сборник науч. трудов), вып. 18, Саратов, 1993. 88-89.