О мощности классов дискретных функций, удовлетворяющих конечиоточечным условиям. тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



Г

Московский Государственный Университет имени М.В.Ломоносова

» Факультет Вычислительной математики и кибернетики ^ ОО

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

Ворояенко Андрей Анатольевич

О мощности классов дискретных функций, удовлетворяющих конечноточечным условиям.

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1997

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

Научиый руководитель: доктор физико-математических наук профессор Алексеев В.Б.

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

Гашков С.В.

кандидат физико-математических наук Зуев Ю.А.

Ведущая организация: Институт Системного Программирования РАН

Защита диссертации состоится "28" ноября 1997 г. в II00

в ауд. 685 2-го уч. корпуса на заседании диссертационного совета Д 053.05.38 при факультете Вычислительной математики и кибернетики МГУ по адресу: 119899, ГСП, Воробьевы горы, МГУ, факультет ВМиК.

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

Автореферат разослан

«

октября 1997 г.

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

диссертационного совета,

профессор

Н.П.Трифонов

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

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

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

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

Наряду с отношением порядка часто рассматриваются и другие отношения. Paie оценивалась асимптотика логарифма для замкнутых классов булевых функций от-эсителыго различных операций (С.В.Яблонским, О.Б.Лупановым, Ю.В.Кузнецовым). .Б.Алексеев получил асимптотику логарифма для мощности всех предполных классов значной логики. Также изучалась задача о числе различных полиномов в при состав-зм к. С.Б.Гашков получил асимптотику функции Шеннона для приближения нелрерыв-ах функций на отрезке полиномами, а Г.Г.Аманжаев - для приближения дискретными ункциями, причем для получения нижней оценки в обоих случаях потребовалось найти :имптотику логарифма мощности соответствующих классов функций. Ряд работ был по->ящен изучению вопроса о существовании дискретных отображений, обладающих теми га иными свойствами. В настоящей работе рассматриваются вопросы оценки количества декретных функций, для которых близость наборов из области определения порождает шзость значений функции.

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

Научная новизна. Все основные результаты являются новыми. В диссертации получены следующие основные результаты:

1) разработаны методы проверки условия Ьй^. |/''п| ~ кп при п -> оо для классов функций к-значной логики, сохраняющих конечноместный предикат,

2) найдена асимптотика логарифма мощности для классов функций, сохраняющих предикаты, удовлетворяющие части аксиом монотонности;

3) построены методы оценки асимптотики логарифма мощности для классов метрических дискретных функций;

4) найдена асимптотика логарифма мощности для классов липшицевых дискретных функций при растущем числе переменных;

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

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

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

Апробация работы. Результаты работы докладывались на школе-семинаре (Мо сква,1995), на международной конференции по проблемам теоретической кибернетики (Ульяновск,1996), на семинарах по математическим вопросам кибернетики под руководством чл.-корр. РАН С.В.Яблонского, на других школах и семинарах.

Публикации. По теме диссертации имеется 2 публикации, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, трех глав и спискг литературы. Первая глава разбита на 4 параграфа, вторая - на 5 параграфов, третья -на 3. Объем работы 82 страницы. Список литературы содержит 34 наименования.

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

В первой главе описываются ситуации, когда по виду конечноместного предиката мож-> ответить па вопрос, верно ли, что

1°г* |Д.| ~ кп при п ~> оа (1.1)

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

Определение. Функция /(а^,.. .,г„) : —> Ек сохраняет предикат Я{у\,... ,ун), :ли для любых Й1 = (а;,.. ... = (а\,... ,а1), где все а] € Ек, справедлива чштакация

v¿л(ai,... ) лс/(5,),... ,нщ)) (1.2)

О первом параграфе доказывается ряд вспомогательных утверждений, которые затем ^пользуются во всех главах. Во втором параграфе доказывается несколько достаточных ;ловий (1). Приведем формулировки некоторых из них. Теорема 1.2.1. Признак верх-низ. Пусть Рп сохраняет предикат Я(у1,у2) тгикой, что

За <Е Ек Ус € £к -Д(с,а) (верх) (1.3)

36 € Ек Ус € Ек с) (низ) (1.4)

Тогда выполнено (1).

Этот результат можно обобщить на случай /¡-местных предикатов. Введем характери-■ическую функцию

ХЩу!.....ул) : Ек —1 2{1......

?йствующую по правилу:

г 6 х(а) <=> Зол,... .,аК Я(аи... ,0(_ьа, ...

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

Теорема 1.2.2. Пусть Fn - класс функций, сохраняющих предикат Щу''), и пусть

k-i

П ХЖш.....ыО') = 0-

j=0

Тогда \ogk |Р„| ~ кп при п —> оо.

Теорема 1.2.4. Пусть Fn - класс функций, сохраняющих предикат R(yh), и пусть

к-1

П хя(У1.....у„)(Л = Q,

J=0

причем

3aVah в <£ Q а{ = а ä(q, ,..., аА))

Тогда logk | ~ кп при п —► оо.

Замечание. Q - мпожество позиций, при любом значении которых предикат R може) быть истинным .

Теорема 1.2.6. Пусть F„ - класс функций, сохраняющих предикат ft(yh), и nycri существует Q С £V,|<3| > (1 — такое, что если не менее р координат вектора (fei,. -., Ьл принадлежат Q, то -^(bj.,... ,6д). Пусть при этом существует а 6 Ек такое, что если н< менее h — р 4- 1 координат вектора (Ai,..., b/,) равны а, то R(bi,..., Ъь). Тогда logt |F„| ~ кп при п —► со.

В §1.3 получены необходимые условия (1). Сформулируем основной результат. Обозначим через П(&) множество всех перестановок вектора (0,1,..., к — 1). Теорема 1.3.1. Пусть Fn - класс функций, сохраняющих предикат R(yh). Для тоге чтобы logfc I^Fnl ~ к" при п —t оо, необходимо

V/': П(к) —* Ек Bf € Fh Vz е П(Аг) f{x) = /'(*)■

В четвертом параграфе рассматриваются функции, удовлетворяющие части аксио) монотонности. Монотонные функции fc-значной логики можно определить как сохраняю щие двуместный предикат -ß(t/i, г/г)> удовлетворяющий следующим трем аксиомам:

Vai£(a,a) (рефлексивность) (1.5

Va ф b -<(R(a,b)$zR(b,a)) (асимметричность) (Ii

Va,b, с (R(a,b)LR(b,c) => R(a,c)) (транзитивность) (l.'i

орема 1.4.1. Пусть Fn - класс функций, сохраняющих предикат R(yk), такой, что R(a, ...,а). Пусть q> 2 - максимальная мощность множества

QCEk\\/bu...,bheQ i?(bi,...A).

Тогда logt ltf.1 ~ kn l°gkq при n -* oo.

Для двуместных предикатов этот результат формулируется следующим образом: Следствие. Пусть Fn - класс функций, сохраняющих рефлексивный (5) предикат fb Уз)I Для которого не выполнено (6) (есть симметричная пара). Пусть q - максимадь-1 мощность множества Q С Ек такого, что V6b 62 € Q Ä(&i, ¡>2). Тогда logfc |F„| ~ кп logt q при п —> оо.

Теорема 1.4.2. Пусть F„ - класс функций, сохраняющих предикат У2), обла-ощий свойством транзитивности (7), и не обладающий свойством рефлексивности (5). ложим

— max : i?(v,a)|; hi = max |и:Л(а,г)|

a-Ji(a.a) a:R(a,a)

h = max |t> : R(a, v)kR(v, i>)|

Тогда 1) если выполнено (3) и (4), то logt |F„| ~ кп при п —> оо;

2) если выполнено (3) и не выполнено (4), то log^F,,! ~ kn\ogkhu при п оо; если полнено (4) и не выполнено (3), го logt |F„| ~ кп logfc hj при п —» оо;

3) если не выполнено ни (3), ни (4), то logt |F„| ~ h при n —> 00.

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

Для строгого определения возьмем последовательность функций {*/>«} и набор свойств. Через /¿+ будем обозначать множество, состоящее из всех неотрицательных чисел и бесконечности ( со ).

0) Уп фя:ТГ+—> Д+,

причем

^„(!>1,..., Ь„) = оо Вг Ь,- = оо.

В дальнейшем будет использоваться лишь следующее свойство бесконечности: Для любого действительного х

х < оо и -1 (оо < х).

1) Инвариантность:

Уп > 1 АМЬ,- ■ ■. Ьп, 0) = ..., Ь„);^(Ь) = 6.

2) Симметричность: пусть 7г - произвольная перестановка на множестве п координат. Тогда

УпУтг фп{тс о Ьп) = фл(Ьп).

3) Монотонность:

V* = 17Н Ь; > С, > 0 ==> ^„(6") > </>п(с")

Замечание. Последовательности функций

,=1 \1=1 ) то есть наиболее известных норм, удовлетворяют всем свойствам 0)-3).

Пусть задан граф £ с к вершинами с номерами 0,..., к—1. Обозначим через ра метрику кратчайшего пути на Ек, для которой граф С? является графом единичных расстояний, При этом, если вершины е, и су принадлежат различным компонентам связности графа О, положим />с(>,./) — оо. Определим

ра.фЛ^1,^) = Фп(рв(х11у1),...,рв{хп,Уп)). (2-1]

)пределение. Пусть граф О имеет к вершин, граф С> -1 вершин. Функция / : —> _Е( азывается метрической с параметрами фп,0,а > 1,<3,/? > 1, если

У*", ¡Г 6 0") < а => МЛ?1), ЯЛ) < /9- (2.2)

Оказывается, что при оценке количества функций можно избавиться от некоторых араметров. Рассмотрим граф <Э', имеющий, как и граф С}, { вершин. Ребро

гсловие (2) эквивалентно условию

УУ.у» 6 Е! Р0.*.(ЗГ,Г) < о => лЯД^). ДЛ) < 1- (2.3)

'аким образом, заменой графа на <5' всегда можно добиться /3 — 1. Будем обозначать п(Фт С?,<», Я) множество всех метрических функций с параметрами б, л, <3,1, завися-Ц1Х от п фиксированных перемеаных. В дальнейшем мы будем использовать обозначение

= (ра{хиУ1),...,рв{хп,уп)).

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

Теорема 2.2.1. Пусть последовательность {фп} обладает свойствами 0)и 1), граф (? меет к вершин, граф <3 - 1 вершин, и каждый из графов Си ф имеет хотя бы одно ребро, 'огда существует константа 2 < с < 1 такая, что

бозначим

Оказывается, что константы с{{фп},С, а,<2) можно сравнивать при фиксированных фп}, а, <3 и различных С?. Теорема 2.2.2. О сравнении с булевым кубом.

Пусть последовательность {фп} обладает свойствами 0), 1) и 2), граф <3 имеет к вер-ип, граф 0-1 вершин, и каждый из графов в ж имеет хотя бы одво ребро. Тогда

с(Ш,С,а,<Э) < с{{фп},В2,а,<Э). 7

Замечание 1. Отметим, что мы не требовали свойства монотонности последовательности {ф„}.

Замечание 2. Эту лемму можно применять следующим образом: если некая нижняя оценка для c({^>„},G,a, Q) является верхней для с({фп},В2,ато она является точным значением этих констант.

Теорема 2.2.3. Пусть последовательность {фп} обладает свойствами 0),1) и 2). Пусть граф (?„ имеет кп вершин и мощность максимального паросочетания в графе Gn равна р„. Пусть при этом

г Рп

lim — п = оо.

Тогда

< bg2 с(Ш,В2,а,Я).

(М

Для случая а > фз{1,1) задачу нахождения асимптотики логарифма удалось решить полностью.

Теорема 2.2.4. Пусть последовательность {у,,} обладает свойствами 0), 1) и 2), q > 2 - максимальная мощность клики в графе Q, а граф G имеет хотя бы одно ребро. Пусть

*>Ы 1,1).

Тогда с({1^п}, Q) —

При дополнительном требовании монотонности 3) оставшиеся задачи сводятся к случаю а = 1.

Лемма 2.2.1. Пусть последовательность {фп} удовлетворяет свойствам 0)-3), пусть числа bi,..., Ъ, неотрицательны и хотя бы два из них не меньше 1. Тогда

Следствие. Пусть последовательность {фп} удовлетворяет свойствам 0)-3). Пусть а < tf>2(l,l). Тогда

c(m>G,a,Q)=c({j:p,}!G\l,Q), •=1

где граф G' имеет то же множество вершин, что и граф G, а ребро

(е,, tj) Ф\{ра{ьj)) < а.

Обозначим

Fn{G,Q)=Fn(£Pi,G,l,Q). (2.5)

Будем обозначать

^<7,«) = *"—(2-6)

Для графов введем бинарное отношение квазипорядка <

Н <G Зг : G изоморфен подграфу графа 1Г. (2.7)

Справедливы следующие Утверждения о квазипорядке < .

1) Пусть граф G имеет хотя бы одно ребро. Тогда G < В2-

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

2) В2 < Вк.

3) £?2 < Cat, где Cik - произвольный цикл четной длины.

4) В^ < D, где D - произвольное дерево.

Отношение квазипорядка < позволяет сравнивать константы c(G, Q) при фиксирован->м Q.

Теорема 2.2.5. Пусть каждый из графов Gj.,Gn,Q имеет хотя бы одно ребро, и Gx < 2 в смысле определения (7). Тогда

c{Gi,Q)<c{G*,Q).

В одном важном случае формула теоремы 2.4. справедлива и при а = 1. Рассмотрим •ображения /: —-> Ei такие, что

Vi,У € ЕЦ ф |х, - < 1 |т - №\ < г) . (2-8)

№ г - некоторое натуральное число. Эти функции логично называть дискретными лип-ицевыми. Обозначим через В\ Т граф с I вершинами и ребрами: (е{,е}) е В,,г \i — jl < г.

Теорема 2.3.1. V/ > г > 1 с(В2,Ви) = г + 1.

Это утверждение является наиболее технически трудным. Его доказательству посвящен третий параграф второй главы. В §2.4 и §2.5 изучаются свойства квазипорядка < и получаются нижние оценки для конставт с(С?, (}).

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

Рассмотрим случай, когда при фиксированной размерности растет значность, то ест; функции / : —» такие, что

У5*,5*е <1=ЧДг) -/(й|<г). (зл;

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

Теорема 3.1.1. При I > г, последовательность и„ — имеет предел, причеи

Введем обозначение

¿(к, I, г) = ^

Теорема 3.1.2. Константа ¿{к, I, г) при / > г является строго возрастающей функцие! аргумента то есть

ё{к,1 + 1,г) >с1{к,1,г).

Определение. Через Я„(А;, оо,г) и через Рь(п, со, г) будем обозначать множество все. функций /, отображающих Е* в множество целых чисел, таких, что

/(бк) = 0 & Ух,у^|х.--я|<1=4.|/(г)-/(Й1<г). (3.2

Лемма 3.2.5.

los, 00, r)| = r

n-»oo l-—too bJ V '

Обозначим

Теорема 3.2.1. Неравенство пространства,

d(k + l,oo, г) < d(k,2r + 1,г).

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

t определепия, так и области значений.

Определения.

Пусть на области определения задана метрика pD{n)(ß,y), а на области значений „)(й, и) и пусть задана функция 5(т): Vi 0 < ¿(i) < t. Тогда отображение / : D{n) —> п) называется нерастягивающим с параметром-функцией 5(т), если

W,ffeD(n) PEM(f(Z)J(y))<¿(pD(n)(S,y))- (3-4)

означим Vn(D(n),E(n),6) множество всех нерастягивающих отображений D(n) —> п) с параметром-функцией S.

Теорема 3.3.1. Пусть \/к S{2k) > 2, S(2k + 1) > 1. Тогда припчоо

'°§2 |Ki(ß"5 log2 п.

Теорема 3.3.2. Пусть Vk S(k) > 1, 3Í S(2l) = 1. Тогда при п -» оо

bg2|V„(ß?1J3J,5)|~Z".

Теорема 3.3.3. Пусть граф G имеет к вершин и d компонент связности. Пусть граф имеет хотя бы одно ребро, pD(n),PE(n) - метрики кратчайшего пути. Пусть

¿(1) = 1; Vm > 2 6(т) > 2,

ф(п) —» со при п —» оо,

Тогда предел

dПф(п)

—-— -»0 при п * со.

к log2 ф(п)

lim НгШ^^З

fc"logj ф(п)

равен пределу отношения мощности максимальной антиклики графа G" к кп при п —» ос

Список литературы.

1. Вороненко A.A. О мощности некоторых классов дискретных функций.// Тезис] докладов на XI Международной конференции по проблемам теоретической кибеу нетшш. Ульяновск, 1996, с. 36-37.

2. Вороненко A.A. Об условиях полной асимптотики мощности классов функций к значной логики, сохраняющих конечноместный предикат.// Вестник МГУ. Выч! слительная математика и кибернетика, 1997, N 3, с.44-47.