Авторефераты по всем темам >>
Авторефераты по разное
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова На правах рукописи
Вороненко Андрей Анатольевич
Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойств
Специальность: 01.01.09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
МОСКВА 2007
Работа выполнена в Московском государственном университете имени М. В. Ломоносова, на факультете ВМиК
Официальные оппоненты:
доктор физико-математических наук, профессор Гашков С. Б.;
доктор физико-математических наук, профессор Перязев Н. А.;
доктор физико-математических наук, профессор Шоломов Л. А.
Ведущая организация: Казанский государственный университет имени В. И. Ульянова-Ленина.
Защита состоится Ф Ф 2007 года в часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М. В. Ломоносова
С диссертацией можно ознакомиться в научной библиотеке МГУ.
Автореферат разослан " " 2007 г.
Ученый секретарь диссертационного совета, профессор Трифонов Н. П.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В связи с широким развитием цифровой техники проблема изучения дискретных функций становится все более актуальной. В нашей стране активное изучение дискретных функций было начато во второй половине 50-х годов прошлого века в работах С. В. Яблонского, О. Б. Лупанова, Ю. И. Журавлева и других авторов. За прошедшие годы широко развились такие разделы теории дискретных функций как функциональные системы, проблемы подсчета числа функций, сложность реализации функций, распознавание свойств функций, изучение специальных классов функций.
В диссертации изучаются три типа задач теории дискретных функций: проблема подсчета количества функций, проблема тестирования бесповторных функций и проблема распознавания свойств функций по вектор-столбцу. Основное внимание уделяется построению методов, позволяющих решить большое количество задач.
Задачи подсчета числа дискретных функций интенсивно изучались в течение длительного времени. Наиболее известной такой задачей является проблема Дедекинда [19] о количестве монотонных булевых функций. Эта задача активно исследуется последние сорок лет. Важнейший вклад в ее решение внесли В. К. Коробков [9], Ж. Ансель [20], Д. Клейтмен [21], А. Д. Коршунов [10] и А. А. Сапоженко [12]. С. В. Яблонский [18] исследовал задачу о количестве функций в инвариантных классах. В. Б. Алексеев [2,3] решил задачу нахождения асимптотики логарифма для числа k-значных монотонных функций и числа функций в предполных классах в Pk. Отметим задачу об оценке числа пороговых функций (асимптотика логарифма была установлена Ю. А. Зуевым [5]). Задача оценки количества дискретных функций решалась и для большого количества других классов. В диссертации изучаются задачи нахождения асимптотики логарифма количества дискретных функций для широкого класса семейств, задаваемых простыми естественными условиями.
Задача тестирования функций и схем впервые подробно описана в работе С. В. Яблонского и И. А. Чегис [16]. Различные задачи тестирования ставились для класса монотонных функций. Проблема расшифровки была решена Ж. Анселем [20]. Н. Н. Катериночкина [7, 8], Н. А. Соколов [14, 15] и А. А. Сапоженко [13] решали различные постановки задачи поиска верхнего нула монотонной функции. Большой интерес представляют функции, которые можно реализовать формулами без повторения переменных (бесповторные функции). Одним из первых утверждений теории бесповторных функций была теорема А. В. Кузнецова [11] о конечной полной системе тождеств для бесповторных формул. Задача тестирования бесповторных функций отличается тем, что в ней вырождается целый ряд постановок. В работе рассматривается задача построения проверяющего теста для бесповторной в заданном базисе функции на множестве всех бесповторных в этом базисе функций, не имеющих других существенных переменных, кроме существенных переменных тестируемой функции. Естественным образом ставится задача об оценке функции Шеннона и минимальной длины теста для отдельных функций и последовательностей функций.
Важной задачей для различных приложений (в частности, криптографических) является задача распознавания свойств дискретных функций при различных их заданиях.
Задача распознавания свойств функций, заданных вектор-столбцом, рассматривалась ранее в работах В. Б. Алексеева [1, 4]. Им разработан метод логических полуколец, основанный на использовании алгебраических характеристик распознаваемых свойств. Рассматриваемая задача является частным случаем другой проблемы: существует ли для задачи алгоритм проще (лучше) "естественного". Первый результат в этом направлении был получен А. А. Карацубой [6] для умножения чисел. Целое направление связано с результатом В. Штрассена [22] об умножении матриц. В работе делается строится рекурсивный алгоритм, строящий код функции в предположении, что она обладает исследуемым свойством, для распознавания наличия этого свойства у функции. Данный метод позволяет понизить сложность алгоритмов во многих задачах. Среди рассматриваемых задач выделим задачу распознавания монотонности, в которой получен результат лучше, чем достижимый методом логических полуколец, а также задачу распознавания бесповторности функции в произвольном базисе, связанную с гипотезой О. Б. Лупанова (доказанной недавно Д. Ю. Черухиным [17]) о том, что взаимная бесповторная выразимость является критерием сложностной формульной эквивалентности.
Цели исследований. Изучение свойств дискретных функций из ряда важных классов. Построение представлений функций для решения задач подсчета, тестирования и распознавания свойств.
Научная новизна. Все основные результаты работы являются новыми. Укажем наиболее важные из них.
В диссертации установлена асимптотика логарифма количества отображений вершин булева куба в вершины произвольного графа, переводящих смежные вершины в смежные или совпадающие. Для отображений декартовых степеней частичных порядков в себя, удовлетворяющих части аксиом замыкания, также найдена асимптотика логарифма количества. Для получения оценок количества дискретных функций предложен метод жирных точек, при помощи которого получена асимптотика логарифма количества дискретных функций в нескольких семействах классов функций, сохраняющих двуместные предикаты.
Исследована проблема тестирования бесповторных функций. Поставлена задача построения теста относительно бесповторной альтернативы. Для ее решения разработан метод квадратов существенности (для случая базиса всех функций двух переменных), который был обобщен на случай базисов, содержащих функции большего количества переменных. Получен порядок роста функций Шеннона длины теста в ряде базисов. Для элементарного базиса установлен линейный рост функции Шеннона. В базисе функций двух переменных построены последовательности функций с длиной проверяющего теста от линейной до квадратичной.
Разработан метод разложения для схемного распознавания принадлежности дискретных функций, задаваемых столбцом значений, наследственным классам. При помощи это го метода получены верхние оценки O(N log N log log N) для сложности распознавания монотонности, частичной монотонности и поляризуемости булевых функций (N длина вектор-столбца). Доказана линейность сложности задач распознавания свойств доопределимости до линейной функции и бесповторности в произвольном конечном базисе. Исследована задача построения схем, распознающих наличие у булевой функции растущего количества фиктивных переменных.
Методика исследований. В работе используются методы теории булевых и k-значных функций и комбинаторики.
Практическая и теоретическая ценность. Работа носит теоретический характер.
Ее результаты могут быть использованы в различных разделах теории дискретных функций, в том числе при решении задач оценки количества дискретных функций, при исследовании бесповторных функций в различных базисах и при оценке сложности распознавания свойств дискретных функций, задаваемых вектор-столбцом. Вместе с тем полученные результаты по тестированию бесповторных функций могут быть использованы при тестировании реальных схем, изготовленных по технологии FPGA.
Апробация. Результаты работы докладывались на VII Международной конференции "Дискретные модели в теории управляющих систем"(2006, Москва), на российской школесемирнаре "Синтаксис и семантика логических систем"(2006, Иркутск) пленарные доклады, на шестой молодежной научной школе по дискретной математике и ее приложениям (лекция, 2007, Москва), на 15 конференции IEEE Computational Complexity (2000, Флоренция), на Ломоносовских чтениях в МГУ, на II, IV, VI Международных конференциях "Дискретные модели в теории управляющих систем"(1997, 2000, 2004, Москва), на XI, XII, XIV Международных конференциях "Проблемы теоретической кибернетики"(1996, Ульяновск, 1999, Нижний Новгород, 2005, Пенза), на VI, VII Международном семинаре "Дискретная математика и ее приложения (1998, 2001, Москва), на конференции "Интеллектуализация обработки информации"(2000, Симферополь), на четвертой молодежной научной школе по дискретной математике и ее приложениям (2000, Москва), на Международной школе-семинаре "Дискретная математика и математическая кибернетика"(2001, Москва), на XIII Международной школе-семинаре "Синтез и сложность управляющих систем"(2002, Пенза), на семинаре С.В.Яблонского (с осени 1998 г. О.Б.Лупанова) "Математические вопросы кибернетики"и на научных и учебных семинарах факультета ВМиК МГУ.
Публикации. Основные результаты диссертации изложены в рецензируемых работах, список которых приведен в конце автореферата. Там же приводится список остальных работ по теме диссертации.
Структура диссертации. Диссертация состоит из введения, трех глав, состоящих в совокупности из 15 параграфов, и списка литературы. Полный объем диссертации 1страницы.
СОДЕРЖАНИЕ РАБОТЫ
Первая глава посвящена оценке количества дискретных функций. Пусть B = {0, 1}.
Через Bn обозначим множество всех n-мерных вектоpов с координатами из B. Весом набора x называется сумма его координат. Будем называть наборы x и y соседними тогда и только тогда, когда они отличаются ровно в одной координате.
Пусть H = (V, E) произвольный граф. Функции f : Bn - V (H), переводящие соседние наборы в совпадающие или смежные вершины графа H, будем называть метрическими и обозначать их множество через Fn(H).
Пусть u V (H). Тогда положим u = {u} {v | (u, v) E(H)}. Пусть A V (H).
Назовем псевдограницей A и обозначим через A множество A = u.
uA Теорема 1.1.1.
2n lim |Fn(H)| = max |A||A|.
n AV (H) Пусть S частично упорядоченное множество с элементами из Ek = {0,..., k - 1}.
Частично упорядоченное множество, не содержащее сравнимых элементов, называется вырожденным. Через Sn будем обозначать n-ю декартову степень частично упорядоченного множества S.
Замыканием [M] на множестве M называется отображение 2M в себя, удовлетворяющее трем условиям: 1) если A B, то [A] [B]; для всех A выполняется 2) A [A], 3) [[A]] = [A]. Если x вектор принадлежности элементов подмножества множеству M (характеристическая функция подмножества), а (x) вектор принадлежности элементов замыкания подмножества множеству M, то условия 1)Ц3) соответственно эквивалентны условиям:
xy x y = (x) (y) () (1.2.1) x (x) x () (1.2.2) x ((x)) = (x) () (1.2.3) Если учитывать кратные или нечеткие вхождения элементов, то возникает задача о подсчете многозначных отображений, удовлетворяющих соответствующим условиям. Через i Vn(S) будем обозначать множество отображений n-й декартовой степени частично упоряi,j доченного множества S в себя, удовлетворяющих условию i. Через Vn (S) будем обозначать множество отображений n-й декартовой степени частично упорядоченного множества S в себя, удовлетворяющих условиям i, j.
Рассмотрим i(x1,..., xn) - i-тые координаты отобpажения. Представим их как функции fi(x1,..., xi-1, xi+1,..., xn), отобpажающие набоp всех пеpеменных, отличных от xi, в k-значные вектоpа длины k c номеpами кооpдинат из S, определяемые равенством:
i(x1,..., xi-1, j, xi+1,..., xn) = fi(x1,..., xi-1, xi+1,..., xn)j.
Введем множество U всех k-меpных k-значных вектоpов e с координатами из множества S, удовлетворяющих условиям:
i ei i, (1.2.4) i, j (i j) = (ei ej). (1.2.5) На U введем частичный порядок S (u v) (i ui vi) 1,Теоpема 1.2.1. Отобpажение : Sn - Sn пpинадлежит Vn (S) тогда и только тогда, когда все функции fi монотонно отобpажают Sn-1 в U.
Назовем нижней гранью множества A такой элемент b, что b принадлежит A и c b для всех элементов c, принадлежащих A.
Теорема 1.2.2. Множество U состоит из единственного вектора тогда и только тогда, когда ни для какого элемента Ek не существует нижней грани множества всех бльших его в смысле порядка S элементов (порядок S необходимо замкнут). Если множество U состоит не менее чем из двух векторов, то оно содержит сравнимые вектора.
Теорема 1.2.3. Если для некоторого элемента S существует нижняя грань множества бльших его элементов, то logk d(S ) 1,logk |Vn (S)| kn-1 n n .
2D(S) Константы d и D определяются по частичному порядку в работе [2].
Обозначим через () число элементов из S таких, что . Будем считать равномерно распределенной на S случайной величиной. Символом E обозначается среднее значение (математическое ожидание дискретной величины).
2,Теорема 1.2.4. logk |Vn (S)| nknE logk при n .
Иными словами, добавление условия замкнутости не влияет на главный член асимптотики логарифма количества экстенсивных многомерных отображений.
kn n 1,3 Теорема 1.2.5. logk |Vn (S)| logk d logk |Vn (S)| при n .
2D Пусть {Fn} произвольная последовательность множеств функций n переменных.
Пусть {Hn} некоторая последовательность множеств. Пусть {n} последовательность произвольных всюду определенных отображений, действующих из Fn в Hn. Отметим, что однозначность отображений n не требуется. Последовательность множеств {Hn} логарифмически мала относительно {Fn}, если выполнено соотношение log |Hn| = (log |Fn|) n . (1.3.1) Назовем последовательность точек {n} жирной, если n Hn для любого n и справедливо асимптотическое равенство log max |-1()| log |-1(n)| n . (1.3.2) n Hn n Лемма 1.3.1 (Метод жирных точек). Пусть последовательность точек {n} является жирной для некоторой последовательности множеств {Fn}, образов Hn и функций n. Пусть последовательность множеств {Hn} логарифмически мала относительно {Fn}. Тогда log |Fn| log |-1(n)| n .
n Рассмотрим произвольный предикат R(x, y), удовлетворяющий условию транзитивности a, b, c (R(a, b)&R(b, c) = R(a, c)) и имеющий иррефлексивную точку, то есть aмR(a, a).
Через Irr обозначим множество всех иррефлексивных точек предиката R. Поскольку свойство транзитивности близко к частичному порядку, будем использовать обозначение a b вместо R(a, b) и a b вместо мR(a, b). Назовем константу m псевдомаксимумом (псевдоминимумом), если для любого x выполнено соотношение m x = x m (x m = m x).
Из транзитивности следует, что если m иррефлексивный псевдомаксимум (псевдоминимум), то не существует такого x, что m x (x m). Через Max обозначим множество псевдомаксимумов, через Min множество псевдоминимумов. Положим a = {x : a x}, a = {x : x a}, I(a, b) = {x : a x b}.
Теорема 1.3.1. Пусть {Fn} последовательность множеств k-значных функций n переменных, сохраняющих транзитивный предикат R, имеющий иррефлексивную точку.
Тогда 1. Если и множество псевдомаксимумов, и множество псевдоминимумов содержат иррефлексивные точки, то logk |Fn| kn n .
2. Если Max Irr = , а Min Irr = , то logk |Fn| kn logk max |a | n .
aMin 3. Если Max Irr = , а Min Irr = , то logk |Fn| kn logk max |a | n .
aMax 4. Если Max Irr = Min Irr = , то logk |Fn| kn logk max |I(a, b)| n .
aMin,bMax Теорема 1.3.2. Пусть Fn(R) класс функций n переменных, сохраняющих двухместный предикат R, удовлетворяющий условиям рефлексивности aR(a, a) и наличия симметричной пары a, b (a = b)&R(a, b)&R(b, a).
Пусть W (R) множество всех подмножеств Q Ek таких, что a, b Q R(a, b).
Тогда logk |Fn(R)| kn max logk |Q|. (1.3.5) QW (R) Обозначим через Rs двухместный предикат, определяемый соотношением:
Rs(a, b) = 0 (a = b)&(a < s).
Тогда справедлива следующая Теорема 1.3.3. Пусть 0 s k - 1. Тогда (k - s) logk(k - s) + s logk(k - s + 1) logk |Fn(Rs)| kn p n .
k Вторая глава посвящена исследованию функций, бесповторных в различных базисах.
Функция называется бесповторной в базисе B, если она представляется в нем формулой, в которую каждая переменная входит не более одного раза. Все рассматриваемые базисы мы будем считать наследственными, то есть содержащими вместе с функцией все остаточные подфункции. Через Bl обозначим базис всех функций l переменных. Бесповторные в Bl функции будем называть l-бесповторными. Функции, бесповторные в B2, будем просто называть бесповторными.
Представляет содержательный интерес следующая постановка задачи. Дана бесповторная в некотором базисе B функция f(x1,..., xn), существенно зависящая от всех своих переменных. Требуется построить проверяющий тест для f(x1,..., xn) на множестве всех бесповторных в этом базисе функций, зависящих от переменных x1,..., xn произвольным образом. Эту задачу назовем построением теста для f относительно бесповторной альтернативы.
Задача имеет следующую интерпретацию. Бесповторные функции и только они реализуются схемами из функциональных элементов без каких-либо ветвлений. Константные неисправности и нарушения работы элементов не приводят к потере свойства бесповторности. Если мы хотим проверить, реализует ли данная нам схема без ветвлений с множеством входов x1,..., xn, неизвестным конкретным внутренним строением и неизвестными неисправностями функцию f(x1,..., xn), то нам требуется решить рассматриваемую задачу.
Функция s переменных (s 3) называется собственной (или s-собственной), если она не является s - 1 бесповторной.
Дерево, соответствующее бесповторной формуле, называется правильным, если оно удовлетворяет следующим условиям:
1. Листья помечены попарно различными переменными.
2. Отрицания могут быть лишь вершинами, смежными с листьями.
3. Внутренние вершины помечены одним из следующих символов:
&, , , (вершины любой степени захода, которым соответствует конъюнкция, дизъюнкция, сумма по модулю 2 или ее отрицание) или символами, соответствующими s-собственным функциям (только для вершин степени захода s).
4. Смежные вершины не могут быть помечены одинаковыми символами из множества {&, , , }, а также символами и одновременно.
Пусть подфункция f(1,..., i-1, xi, i+1,..., j-1, xj, j+1,..., n) функции f(x1,..., xn) является существенной. Тогда множество наборов (1,..., i-1, 0, i+1,..., j-1, 0, j+1,..., n) (1,..., i-1, 0, i+1,..., j-1, 1, j+1,..., n) (1,..., i-1, 1, i+1,..., j-1, 0, j+1,..., n) (1,..., i-1, 1, i+1,..., j-1, 1, j+1,..., n) назовем квадратом существенности переменных xi и xj функции f. Множеством квадратов существенности функции назовем произвольное множество наборов, которое для любой пары существенных переменных содержит некоторый квадрат их существенности.
Теорема 2.2.1. Множество квадратов существенности произвольной бесповторной функции является проверяющим тестом относительно бесповторной альтернативы.
Из этой теоремы вытекает оценка функции Шеннона для длины теста:
n n TB (n) 4.
i i=Хребтом бесповторной функции назовем правильное дерево, из которого можно получить правильное дерево для соответствующей этой функции формулы навешиванием отрицаний на функции, реализуемые в некоторых вершинах.
Следующим важным понятием является таблица существенности. Таблица сущеn ственности l-бесповторной функции f(x1,..., xn) содержит три столбца и строк. В l первом столбце каждой строки содержится свой набор переменных xi,..., xi. Во втором 1 l столбце содержится набор n - l констант j для j {i1,..., il}. B третьем столбце содер/ жится подфункция, получаемая из f(x1,..., xn) подстановкой констант и существенно зависящая от всех своих переменных. Выбор констант из второго столбца при этом определяется произвольным образом. Если же такой выбор невозможен, то второй и третий столбцы содержат прочерки.
Теорема 2.3.1. По таблице существенности l-бесповторной функции f можно получить некоторый ее хребет.
емма 2.3.5. Таблица существенности l-бесповторной функции и произвольный ее хребет однозначно определяют бесповторную функцию.
Гиперкубом существенности l-бесповторной функции называется множество 2l наборов аргументов и значений функции на этих наборах, содержащее для некоторых l переменных все возможные поднаборы значений, совпадающих в оставшихся компонентах, и таких, что соответствующая остаточная функция существенно зависит от всех l переменных.
Множеством гиперкубов существенности l-бесповторной функции называется множество наборов аргументов и значений функции на этих наборах, содержащее для каждого набора l переменных, если это возможно, 2l наборов, совпадающих в оставшихся компонентах, и таких, что соответствующая остаточная функция существенно зависит от всех l переменных.
Булева функция d(x, y), существенно зависящая от своих аргументов, называется дискриминирующей, если при любом выборе констант остаточная подфункция d(, y) имеет фиктивную переменную. Для конкретной дискриминирующей функции могут, вообще говоря, существовать несколько способов разбиения переменных на множества x и y.
Теорема 2.3.2. Пусть произвольный хребет l-бесповторной функции n переменных не содержит дискриминирующих функций, зависящих от l-2 и менее переменных. Тогда длина минимального теста этой функции не превосходит 2l n.
l Из этой теоремы вытекает оценка функции Шеннона для длины теста в базисе всех функций трех переменных:
n n TB (n) i i=и в базисе функций четырех переменных:
Теорема 2.3.3.
n n TB (n) 16.
i i=Введем в рассмотрение каноническое дерево в базисе B3. Среди всех древесных представлений каноническое дерево должно удовлетворять следующим требованиям:
1. Отрицания могут быть лишь вершинами, смежными с листьями.
2. Внутренние вершины помечены одним из следующих символов:
&, , , (вершины любой степени захода, которым соответствует конъюнкция, дизъюнкция, сумма по модулю 2 или ее отрицание) или d, m, s3, s3, XOR3, XOR3, n, n (только для вершин степени захода 3, где f двой1 ственная функция).
3. Смежные вершины не могут быть помечены одинаковыми символами из множества {&, , , }, а также символами , одновременно.
4. Положительными считаются переменные без отрицаний,, , функции трех переменных, имеющие больше половины единиц, функция d и медиана с двумя или тремя положительными входами. Все входы вершин , , а также вход y вершины d(x, y, z) должны быть положительными.
Теорема 2.3.5. Для любой 3-бесповторной функции существует единственное каноническое дерево.
Рассмотрим теперь задачу построения теста относительно бесповторной альтернативы для заданной булевой функции, выразимой бесповторной формулой в базисе B0 = {0, 1, &, , м} и существенно зависящей от переменных x1,..., xn.
Теорема 2.4.1. n + 1 TB (n) < 3.5n.
Следующая теорема дает представление о возможных значениях длины минимального теста для конкретных функций, бесповторных в базисе B2.
Теорема 2.5.1. 1).Пусть функция (n) удовлетворяет условиям (n) (n) lim = и lim . Тогда существует последовательность функций {fn}, для n n2 n n которых выполняется соотношение T (fn) (n) при n .
2).Для любой неотрицательной константы существует последовательность бесповторных функций {fn(x1,..., xn)} такая, что n T (fn) ( + 3) n + O( n) при n .
Упоминаемые в теореме 2.5.1 последовательности функций в работе построены в явном виде.
Информация о значениях функции на множестве квадратов (гиперкубов) существенности зачастую является избыточной. При тестировании используется восстановление этой информации по имеющейся.
Третья глава посвящена решению задачи распознавания свойств дискретных функций, задаваемых вектор-столбцом, схемами из функциональных элементов. Мы представим общий метод распознавания принадлежности функций классам, замкнутым относительно подстановки констант, использующий разложение по переменной. Входом cхемы является вектор-столбец значений функции, а выходом бит, равный 1 для функций, обладающих заданным свойством, 0 - иначе.
Теорема 3.1.1 (основная). Пусть F произвольный класс булевых функций, замкнутый относительно подстановки констант на место переменных, и пусть для заданной последовательности {(m)} существуют кодирование функций, принадлежащих F, и последовательность схем {m}, m = 1, 2,..., обладающие следующими свойствами:
1. Cложность кодирования констант равна (0).
2. Если на вход произвольной схемы m подать коды подфункций f(x1,..., xm-1, 0) и f(x1,..., xm-1, 1), принадлежащих F, то выход схемы m содержит бит, распознающий принадлежность функции f(x1,..., xm) классу F.
3. Если функция f(x1,..., xm) принадлежит классу F, то выход схемы m содержит код функции f(x1,..., xm).
4. Сложность схемы m не превосходит (m).
Тогда существует схема Sn, распознающая принадлежность классу F произвольной функции n переменных, представленной в виде вектор-столбца значений, сложности не более n (2n - 2)L(x1&x2) + 2n-k (k), k=где L(x1&x2) сложность реализации конъюнкции двух переменных.
(k) Следствие. Если ряд сходится, то принадлежность инвариантному классу 2k k=распознается с линейной сложностью относительно 2n длины вектор-столбца булевой функции.
Теорема 3.2.1. Пусть N = 2n. Тогда существует схема из функциональных эле ментов Sn сложности O(N log N log log N), входом которой является вектор-столбец значений булевой функции n переменных, распознающая монотонность входной функции.
Теорема 3.2.2. Для множества функций f : {0,..., k - 1}n - {0,..., l - 1}, задаваемых вектором значений длины N = kn, частичного порядка R на {0,..., k - 1}, частичного порядка R1 на {0,..., l - 1} существует схема из конечнозначных функцио нальных элементов сложности O(N log N log log N), распознающая их монотонность.
Не всюду определенная булева функция называется частичной монотонной, если для нее существует монотонное доопределение. Каждое значение частичной булевой функции может быть закодировано двумя битами.
Теорема 3.3.1. Существует последовательность схем {Sn}, распознающих частичную монотонность произвольной функции n переменных, заданной векторно, сложно сти O(2n n log n).
n Пусть для функции f(x1,..., xn) существует вектор такой, что функция f(x,..., x ) 1 n монотонна. Тогда функция f(x1,..., xn) называется поляризуемой.
Теорема 3.4.1. Существует последовательность схем {Sn}, распознающих поляризуемость произвольной функции n переменных, заданной векторно, сложности O(2n n log n).
Теорема 3.5.1. Существует последовательность схем {Sn} сложности O(2n), распознающих доопределимость до линейной произвольной частичной булевой функции n переменных, заданной векторно.
Пусть (k) неубывающая функция, определенная на множестве целых неотрицательных чисел и принимающая целые неотрицательные значения. Рассмотрим класс F булевых функций, имеющих для любого k среди первых k переменных не менее (k) фиктивных.
Теорема 3.6.1.Существует последовательность схем {Sn}, распознающих принадлежность булевой функции f(x1,..., xn) классу F, сложности n-(k) ln k O 2n (3.6.1) 2(k) k=Следствие 1. Пусть в условиях теоремы (k) (1 + ) log2 k при всех k k0. Тогда схемы {Sn} имеют асимптотически линейную сложность по N.
Следствие 2. Пусть в условиях теоремы (k) (1 + ) log2 log2 k при всех k k0.
Тогда схемы {Sn} асимптотически имеют сложность (N log N).
Теорема 3.7.1. Для любого конечного наследственного базиса B существует последовательность схем {Sn}, распознающих бесповторность в базисе B булевых функций n переменных, заданных векторно, сложности O(2n).
Список литературы [1] Алексеев В.Б. Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та, Сер. 1. Матем. Механика. 1997. No 1. C. 22Ц29.
[2] Алексеев В.Б. О числе монотонных k-значных функций // Пробл. киберн. Вып. 28.
М.: Наука, 1974. C. 5Ц24.
[3] Алексеев В.Б. О числе функций в классах, задаваемых центральными предикатами // Матем. заметки. 1985. 37. Вып. 6. C. 880Ц885.
[4] Алексеев В.Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. матем. ин-та им. В.А.Стеклова. Т. 218. 1997.
C. 20Ц27.
[5] Зуев Ю.А. Комбинаторно- вероятностные и геометрические методы в пороговой логике // Дискр. матем. 1991. 3. Вып. 2. C. 47Ц57.
[6] Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // Докл. АН СССР. 1962. 145. No 2. C. 293Ц294.
[7] Катериночкина Н.Н. Поиск максимального верхнего нуля монотонной функции алгебры логики // Докл. АН СССР. 1975. 224. No 3. C. 557Ц560.
[8] Катериночкина Н.Н. Поиск максимального нуля для некоторых классов монотонных функций из классификации Поста // Журн. выч. матем. и матем. физики. 1988.
28. No 9. C. 1397Ц1406.
[9] Коробков В.К. К вопросу о числе монотонных функций алгебры логики // Дискр.
анализ. Вып. 1, Новосибирск, 1965. C. 24Ц27.
[10] Коршунов А.Д. О числе монотонных булевых функций // Пробл. киберн. Вып. 38.
М.: Наука, 1981. C. 5Ц108.
[11] Кузнецов А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр. матем. ин-та им. В.А.Стеклова. 1958. Т. 51. С. 186Ц225.
[12] Сапоженко А.А. Проблема Дедекинда и метод граничных функционалов // Матем.
вопр. киберн. Физматлит. Вып. 9, 2000. С. 161Ц220.
[13] Сапоженко А.А. О поиске максимального верхнего нуля монотонных функций на ранжированных множествах // Журн. выч. матем. и матем. физики. 1991. 31. No 12.
C. 1871Ц1884.
[14] Соколов Н.А. Поиск максимального верхнего нуля для одного класса монотонных дискретных функций // Докл. АН СССР. 1980. 251. No 5. C. 1077Ц1080.
[15] Соколов Н.А. О поиске максимального верхнего нуля для одного класса монотонных функций конечнозначной логики // Журн. выч. матем. и матем. физики. 1981. 21.
No 6. C. 1552Ц1565.
[16] Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Тр. матем. ин-та им. В.А.Стеклова. Том 51. 1958. C. 270Ц360.
[17] Черухин Д.Ю. Алгоритмический критерий сравнения булевых базисов // Матем.
вопр. киберн. Вып. 8. M: Физматлит, 1999. C. 77Ц122.
[18] Яблонский С.В. Об алгopитмических тpудностях синтеза минимальных контактных схем // Пpобл. кибеpн. Вып. 2. М.: Физматгиз, 1959. C. 75Ц121.
[19] Dedekind R. Uber Zerlegungen von Zahlen durch ihre grossten gemeinsamen Teilor, Festschrift Hoch. Braunschweig u. ges. Werke, II, 1887, S. 103Ц148.
[20] Hansel G. Sur le nombre des fonctions boolennes monotones de n variables // C. R. Acad Sci. Paris, 1966, 262, p. 1088Ц1090. ( Русский перевод: Ансель Ж. О числе монотонных булевых функций n переменных // Киберн. сб., изд-во Мир. Новая серия. Вып. 5, 1968.
C. 53Ц57).
[21] Kleitman D. On DedekindТs problem: the number of monotone Boolean functions // Proc. Amer. Math. Soc., 1969, 21, N 3, p. 677Ц682. (Русский перевод: Клейтмен Д. О проблеме Дедекинда: число монотонных булевых функций // Киберн. сб., изд-во Мир.
Новая серия. Вып. 7, 1970. C. 43Ц52).
[22] Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 13, H. 4, 1969, p. 354Ц356 (Русский перевод: Штрассен В. Алгоритм Гаусса не оптимален // Киберн. сб., изд-во Мир. Новая серия. Вып.7, 1970. C. 67Ц70).
Список основных публикаций автора по теме диссертации [23] Вороненко А.А. Бесповторность распознается схемами линейной сложности // Дискр. матем. 2005. 17. Вып. 4. C. 111Ц115.
[24] Вороненко А.А. О длине проверяющего теста для бесповторных функций в базисе {0, 1, &, , м} // Дискр. матем. 2005. 17. Вып. 2. С. 139Ц143.
[25] Вороненко А.А. О количестве замкнутых многомерных монотонных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2002. No 2. C. 41Ц45.
[26] Вороненко А.А. О количестве замкнутых экстенсивных отображений // Вестн.
Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2001. No 4. C. 46Ц48.
[27] Вороненко А. А. О количестве метрических дискретных функций n переменных // Матем. вопpосы кибеpнетики. М.: Физматлит, 1998. Вып. 7. C. 203Ц212.
[28] Вороненко А.А. О количестве метрических функций булева куба // Дискр. матем.
2001. 13. Вып. 4. C. 116Ц121.
[29] Вороненко А.А. О количестве многомерных монотонных экстенсивных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2001. No 1. C.37Ц40.
[30] Вороненко А.А. О методе разложения для распознавания принадлежности инвариантным классам // Дискр. матем. 2002. 14. Вып. 4. С. 110Ц116.
[31] Вороненко А.А. О проверяющих тестах для бесповторных функций // Матем. вопр.
киберн. Вып. 11. М.: Физматлит, 2002. С. 163Ц176.
[32] Вороненко А.А. О распознавании наличия растущего числа фиктивных переменных булевых функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2003. No 2. C. 45Ц46.
[33] Вороненко А.А. О росте количества дискретных липшицевых функций при растущей размерности области определения // Вестн. Моск. ун-та. Сер. 1. Математика и механика, 2000. No 2. C. 3Ц7.
[34] Вороненко А.А. О сложности распознавания монотонности // Матем. вопр. киберн.
Вып. 8. М.: Наука, 1999. C. 301Ц303.
[35] Вороненко А.А. О тестировании бесповторных функций // Вестн. Моск. ун-та. Сер.
15. Выч. матем. и киберн. 2006. No 2. C. 45Ц48.
[36] Вороненко А.А. Об одном подходе к задачам оценки количества дискретных функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2004. No 1. C. 42Ц47.
[37] Вороненко А.А. Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикл. матем. и информатика. 2003. 15. C. 85Ц97.
[38] Вороненко А.А. Об условиях полной асимптотики мощности классов функций kзначной логики, сохраняющих конечноместный предикат // Вестн. Моск. ун-та. Сер.
15. Выч. матем. и киберн. 1997. No 3. C. 44Ц47.
[39] Вороненко А.А. Распознавание бесповторности в произвольном базисе // Прикл.
матем. и информатика. 2006. 23. С. 67Ц84.
Список остальных публикаций автора по теме диссертации [40] Вороненко А.А. О мощности некоторых классов дискретных функций // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики. Ульяновск, 1996. С. 36Ц37.
[41] Вороненко А.А. Асимптотика логарифма мощности классов функций k-значной логики, удовлетворяющих части аксиом монотонности // Труды II Международной конференции "Дискретные модели в теории управляющих Систем". М.: Диалог-МГУ, 1997.
С. 14Ц15.
[42] Вороненко А.А. О росте количества нерастягивающих отображений декартовых степеней графов // Математические методы и приложения. Труды шестых математических чтений МГСУ. М: Изд-во МГСУ "Союз 1999. С. 51Ц54.
[43] Вороненко А.А. О распознавании монотонности // Пpоблемы теоpетической кибеpнетики. Тезисы докладов XII Междунаpодной конфеpенции. Н. Новгоpод, 1999 г. М.:
Изд-во мех-мат ф-та МГУ, 1999. Часть I. С. 42.
[44] Вороненко А.А. О количестве замкнутых экстенсивных монотонных отображений // Tруды IV Международной конференции "Дискретные модели в теории управляющих систем". М.: МАКС Пресс, 2000. С.19Ц21.
[45] Вороненко А.А. О количестве некоторых отображений, связанных с базами данных и знаний // Интеллектуализация обработки информации ИОИТ2000. Тезисы докладов.
Симферополь, 2000. С. 21.
[46] Вороненко А.А. On the Complexity of the Monotonicity Verification // Proceedings 15th Annual IEEE Conference on Computational Complexity. 2000, p. 235Ц238.
[47] Вороненко А.А. О количестве многомерных отображений, удовлетворяющих части аксиом замыкания // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. М.: Изд-во механико-математического ф-та МГУ, 2000.
С. 26Ц27.
[48] Вороненко А.А. Раскраски и нижние оценки количества функций, сохраняющих близость // Материалы VII Международного семинаpа "Дискpетная математика и ее пpиложения."М: Изд-во механико-математического ф-та МГУ. Часть II. 2001. С. 212 - 215.
[49] Вороненко А. А. Об уточненных нижних оценках количества метрических функций // Матем. вопp. кибеpн. Вып. 10. М.: Физматлит, 2001. C. 247Ц251.
[50] Вороненко А.А. О количестве функций, сохраняющих предикат, истинный на разнозначных наборах // Материалы XIII Международной школы-семинара "Синтез и сложность управляющих систем". (Пенза, 14-20 октября 2002 г.) М: Изд-во центра прикладных исследований при механико-математическом ф-те МГУ. Часть I. 2002. С. 66Ц68.
[51] Вороненко А.А. Бесповторность распознается схемами линейной сложности // Труды VI Международной конференции "Дискретные модели в теории управляющих систем". М.: Макс Пресс, 2004. С. 25Ц26.
[52] Вороненко А.А. Оценки длины проверяющих тестов для бесповторных функций в основных базисах // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции. (Пенза, 2005 г.). М.: Изд-во центра прикладных исследований при мех-мат ф-те МГУ, 2005. С. 32.
[53] Вороненко А.А. Метод разложения для распознавания наследственных свойств // Синтаксис и семантика логических систем: Материалы российской школы-семинара.
Иркутск, Изд-во ГОУ ВПО "Иркутский государственный педагогический университет 2006. С. 20Ц26.
[54] Вороненко А.А. Метод разложения для распознавания принадлежности инвариантным классам // М.: Макс Пресс, 2005.
[55] Вороненко А.А. Бесповторные булевы функции // М.: Макс Пресс, 2006.
[56] Вороненко А.А. Оценки количества дискретных функций // М.: Макс Пресс, 2006.