Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Вороненко, Андрей Анатольевич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2007
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова
На правах рукописи
Вороненко Андрей Анатольевич
Методы представления дискретных функций в задачах подсчета, тестирования и распознавания свойств
Специальность 01 01 09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
МОСКВА 2007
003065327
Работа выполнена в Московском государственном университете имени М В Ломоносова, на факультете ВМиК
Официальные оппоненты:
доктор физико-математических наук,
профессор Гашков С Б ,
доктор физико-математических наук,
профессор Перязев Н А ,
доктор физико-математических наук,
профессор Шоломов Л А
Ведущая организация: Казанский государственный университет
имени В И Ульянова-Ленина
Защита состоится "43 " n^Shâ. 2007 года в 4/ часов на заседании диссертационного совета Д 501 001 44 при Московском государственном университете им M В Ломоносова
С диссертацией можно ознакомиться в научной библиотеке МГУ Автореферат разослан " J "é&b/xJfy 2007 г
Ученый секретарь диссертационного совета,
профессор ^ j^y 7 у Трифонов H П
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы В связи с широким развитием цифровой техники проблема изучения дискретных функций становится все более актуальной В нашей стране активное изучение дискретных функций было начато во второй половине 50-х годов прошлого века в работах С В Яблонского, О Б Лупанова, Ю И Журавлева и других авторов За прошедшие годы широко развились такие разделы теории дискретных функций как функциональные системы, проблемы подсчета числа функций, сложность реализации функций, распознавание свойств функций, изучение специальных классов функций В диссертации изучаются три типа задач теории дискретных функций проблема подсчета количества функций, проблема тестирования бесповторных функций и проблема распознавания свойств функций по вектор-столбцу Основное внимание уделяется построению методов, позволяющих решить большое количество задач
Задачи подсчета числа дискретных функций интенсивно изучались в течение длительного времени Наиболее известной такой задачей является проблема Дедекинда [19] о количестве монотонных булевых функций Эта задача активно исследуется последние сорок лет Важнейший вклад в ее решение внесли В К Коробков [9], Ж Ансель [20], Д Клейт-мен [21], А Д Коршунов [10] и А А Сапоженко [12] С В Яблонский [18] исследовал задачу о количестве функций в инвариантных классах В Б Алексеев [2,3] решил задачу нахождения асимптотики логарифма для числа &-значных монотонных функций и числа функций в предпочных классах в Ль Отметим задачу об оценке числа пороговых функций (асимптотика логарифма была установлена Ю А Зуевым [5]) Задача оценки количества дискретных функций решалась и для большого количества других классов В диссертации изучаются задачи нахождения асимптотики логарифма количества дискретных функций для широкого класса семейств, задаваемых простыми естественными условиями
Задача тестирования функций и схем впервые подробно описана в работе С В Яблонского и И А Чегис [16] Различные задачи тестирования ставились для класса монотонных функций Проблема расшифровки была решена Ж Анселем [20] Н Н Катериноч-кина [7,8], Н А Соколов [14,15] и А А Сапоженко [13] решали различные постановки задачи поиска верхнего нула монотонной функции Большой интерес представляют функ-
ции, которые можно реализовать формулами без повторения переменных (бесповторные функции) Одним из первых утверждений теории бесповторных функций была теорема А В Кузнецова [11] о конечной полной системе тождеств для бесповторных формул Задача тестирования бесповторных функций отличается тем, что в ней вырождается целый ряд постановок В работе рассматривается задача построения проверяющего теста для бесповторной в заданном базисе функции на множестве всех бесповторных в этом базисе функций, не имеющих других существенных переменных, кроме существенных переменных тестируемой функции Естественным образом ставится задача об оценке функции Шеннона и минимальной длины теста для отдельных функций и пос ледовательностей функций
Важной задачей для различных приложений (в частности, криптографических) является задача распознавания свойств дискретных функций при различных их заданиях Задача распознавания свойств функций, заданных вектор-столбцом, рассматривалась ра^ нее в работах В Б Алексеева [1,4] Им разработан метод логических полуколец, основанный на использовании алгебраических характеристик распознаваемых свойств Рассматриваемая задача является частным случаем другой проблемы существует ли для задачи алгоритм проще (лучше) "естественного" Первый результат в этом направлении был получен А А Карацубой [6] для умножения чисел Целое направление связано с результатом В Штрассена [22] об умножении матриц В работе делается строится рекурсивный алгоритм, строящий код функции в предположении, что она обладает исследуемым свойством, для распознавания наличия этого свойства у функции Данный метод позволяет понизить сложность алгоритмов во многих задачах Среди рассматриваемых задач выделим задачу распознавания монотонности, в которой получен результат лучше, чем достижимый методом логических полуколец, а также задачу распознавания бесповторно-сти функции в произвольном базисе, связанную с гипотезой О Б Лупанова (доказанной недавно Д Ю Черухиным [17]) о том, что взаимная бесповторная выразимость является критерием сложностной формульной эквивалентности
Цели исследований Изучение свойств дискретных функций из ряда важных классов Построение представлений функций для решения задач подсчета, тестирования и
распознавания свойств
Научная новизна Все основные результаты работы являются новыми Укажем наиболее важные из них
В диссертации установлена асимптотика логарифма количества отображений вершин булева куба в вершины произвольного графа, переводящих смежные вершины в смежные или совпадающие Для отображений декартовых степеней частичных порядков в себя, удовлетворяющих части аксиом замыкания, также найдена асимптотика логарифма количества Для получения оценок количества дискретных функций предложен метод жирных точек, при помощи которого получена асимптотика логарифма количества дискретных функций в нескольких семействах классов функций, сохраняющих двуместные предикаты
Исследована проблема тестирования бесповторных функций Поставлена задача построения теста относительно бесповторной альтернативы Для ее решения разработан метод квадратов существенности (для случая базиса всех функций двух переменных), который был обобщен на случай базисов, содержащих функции большего количества переменных Получен порядок роста функций Шеннона длины теста в ряде базисов Для элементарного базиса установлен линейный рост функции Шеннона В базисе функций двух переменных построены последовательности функций с длиной проверяющего те ста от линейной до квадратичной
Разработан метод разложения для схемного распознавания принадлежности дискретных функций, задаваемых столбцом значений, наследственным классам При помощи этого метода получены верхние оценки 0(iV\/bg N log log N) для сложности распознавания монотонности, частичной монотонности и поляризуемости булевых функций (N — длина вектор-столбпа) Доказана линейность сложности задач распознавания свойств доопре-делимости до линейной функции и бесповторности в произвольном конечном базисе Исследована задача построения схем, распознающих наличие у булевой функции растущего количества фиктивных переменных
Методика исследований. В работе используются методы теории булевых и &-значных функций и комбинаторики
Практическая и теоретическая ценность Работа носит теоретический характер Ее результаты могут быть использованы в различных разделах теории дискретных функций, в том числе при решении задач оценки количества дискретных функций, при исследовании бесповторных функций в различных базисах и при оценке сложности распознавания свойств дискретных функций, задаваемых вектор-столбцом Вместе с тем полученные результаты по тестированию бесповторных функций могут быть использованы при тестировании реальных схем, изготовленных по технологии 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 параграфов, и списка литературы Полный объем диссертации — 154
страницы
СОДЕРЖАНИЕ РАБОТЫ Первая глава посвящена оценке количества дискретных функций Пусть В = {0,1} Через Вп обозначим множество всех п-мерных векторов с координатами из В Весом набора х называется сумма его координат Будем называть наборы х и у соседними тогда и только тогда, когда они отличаются ровно в одной координате
Пусть Н — (V, Е) — произвольный граф Функции / Вп —» У(Н), переводящие соседние наборы в совпадающие или смежные вершины графа Н, будем называть метрическими и обозначать их множество через Рп(Н)
Пусть и € У{Н) Тогда положим ди = {и} и {у | (и, у) € Е(Я)} Пусть Л С У(Я) Назовем псевдограницей А и обозначим через дА множество
дА= 0 ди
иеА
Теорема 1 1.1
1ш1 тах^АН-М
Пусть 5 — частично упорядоченное множество с элементами из Е^ — {0, — 1} Частично упорядоченное множество, не содержащее сравнимых элементов, называется вырожденным Через будем обозначать п-ю декартову степень частично упорядоченного множества 5
Замыканием [М] на множестве М называется отображение 2м в себя, удовлетворяющее трем условиям 1) если Л С В, то [А] С [В], для всех А выполняется 2) А С [А], 3) [[А]] — [А] Если х — вектор принадлежности элементов подмножества множеству М (характеристическая функция подмножества), а ф(х)~ вектор принад лежности элементов замыкания подмножества множеству М, то условия 1)-3) соответственно эквивалентны условиям
УхУу х > у => ф(х) > ф(у) () (1 2 1)
Ух ¿(х) > х 0 (1 2 2)
Ух = 0 (12 3)
Если учитывать кратные или нечеткие вхождения элементов, то возникает задача о подсчете многозначных отображений, удовлетворяющих соответствующим условиям Через ^(й) будем обозначать множество отображений п-й декартовой степени частично упорядоченного множества в в себя, удовлетворяющих условию » Через У^1 (£>) будем обозначать множество отображений п-й декартовой степени частично упорядоченного множества 5 в себя, удовлетворяющих условиям г, з
Рассмотрим фг(х 1, ,хп) - 1-тые координаты отображения Представим их как функции /,{хх, , , ж„), отображающие набор всех переменных, отличных от х„ в &-значные вектора длины к с номерами координат из 3, определяемые равенством
Введем множество и всех ¿-мерных &-значных векторов е с координатами из множества 3, удовлетворяющих условиям
Уг е, > г, (12 4)
(г>])^(.ег>е3) (12 5)
На и введем частичный порядок 5'
(и >' V) -Ф=>- (Уг иг > Уг)
Теорема 1.2.1. Отображение ф 5" —> 8п принадлежит тогда и только
тогда, когда все функции /г монотонно отображают б1"-1 в II
Назовем нижней гранью множества А такой элемент Ъ, что Ъ принадлежит А и с > Ъ для всех элементов с, принадлежащих А
Теорема 12 2 Множество и состоит из единственного вектора тогда и только тогда, когда ни для какого элемента Еь не существует нижней грани множества всех блъших его в смысле порядка в элементов (порядок 3 необходимо замкнут) Если множество и состоит не менее чем из двух векторов, то оно содержит сравнимые, вектора
Теорема 12 3 Если для некоторого элемента S существует нижняя грань множества блъших его элементов, то
log, |УЛ5)| - П - °о
а/2тг D{S)
Константы d и D определяются по частичному порядку в работе [2] Обозначим через £(сг) число элементов г из S таких, что т > а Будем считать а равномерно распределенной на S случайной величиной Символом Е обозначается среднее значение (математическое ожидание дискретной величины) Теорема 12 4 log* ~ пкяЕlogk$ прип-» оо
Иньши словами, добавление условия замкнутости не влияет на главный член асимптотики логарифма количества экстенсивных многомерных отображений Теорема 1 2 5 log* |t£8(S)| ~ gg log, d ~ log, щи. n - oo
Пусть {Fn} — произвольная последовательность множеств функций п переменных Пусть {Я„} — некоторая последовательность множеств Пусть {фп} — последовательность произвольных всюду определенных отображений, действующих из Fn в Нп Отметим, что однозначность отображений фп не требуется Последовательность множеств {Нп} логарифмически мала относительно если выполнено соотношение
log \Яп\ = o(log\F„\) n-^oo (13 1)
Назовем последовательность точек {хп} жирной, если Хп 6 Нп для любого п и справедливо асимптотическое равенство
logmaxlfc1^)! -logl^xJI оо (13 2)
Лемма 13 1 (Метод жирных точек) Пусть последовательность точек {хп} является жирной для некоторой последовательности множеств {F„}, образов Нп и функций фп Пусть последовательность множеств {Нп} логарифмически мала относительно {Fn} Тогда
log |F„| ~ log W^iXn)] п -> оо
Рассмотрим произвольный предикат R(x,y), удовлетворяющий условию транзитивности
Va, Ъ, с (Л(а, b)kR(b, с) ==> Л(о, с)) и имеющий иррефлексивную точку, то есть
3a-iB(o, а)
Через Irr обозначим множество всех иррефлексивных точек предиката R Поскольку свойство транзитивности близко к частичному порядку, будем использовать обозначение а<Ь вместо R(a,b) и а -fib вместо -iR(а, Ь) Назовем константу т псевдомаксимумом (псевдоминимумом), если для любого х выполнено соотношение
m -< х =Ф- х <т (х -< т =Ф- т -< х)
Из транзитивности следует, что если т — иррефлексивный псевдомаксимум (псевдоминимум), то не существует такого х, что m -< х (х -< т.) Через Мах обозначим множество псевдомаксимумов, через Мт — множество псевдоминимумов Положим
а Т= {х а -< х}, а 1= {х х-< а}, 1(а, Ь) = {х a~ix -<b}
Теорема 13 1 Пусть {Fn\ — последовательность множеств k-значных функций п переменных, сохраняющих транзитивный предикат R, имеющий иррефлексивную точку Тогда
1 Если и множество псевдомаксимумов, и множество псевдоминимумов содержат иррефлексивные точки, то
п-*оо
2 Если Мах П Irr ф 0, а Мт П Irr = 0, то
log*. ~ kn logk шах (о t I n oo
3 Если Мах П Irr = 0, a Mm П Irr ф %, то
lo& ¡fill ~ кп log/, max ¡a j | п-> оо
аьмах
4 Если Мах П Irr — Mm П Irr = 0, mo
log, ~ log, ^max.^ |/(о, Ь)| rc —> oo
Теорема 13 2 Пусть Fn(R) — класс функций n переменных, сохраняющих двухместный предикат R, удовлетворяющий условиям рефлексивности
MaR(a, а)
и наличия симметричной пары
3а,Ъ (а ф b)icR(a, b)kR(b, а) Пусть W(R) — множество всех подмножеств Q С таких, что
У а, b £ Q R(a,b)
Тогда
logk\Fn(R)\~kn дтахд)1о§,М (13 5)
Обозначим через Rs двухместный предикат, определяемый соотношением
Rs(a, Ь) = О -4=Ф- (о = Ь)&(а < s)
Тогда справедлива следующая
Теорема 13 3 Пусть 0 < s < к — 1 Тогда
log, ~ Г'[к~ S) ' S) + 'Sl0gk{k -S + 1) p »-co
к
Вторая глава посвящена исследованию функций, бесповторных в различных базисах Функция называется бесповторной в базисе В, если она представляется в нем формулой, в
которую каждая переменная входит не более одного раза Все рассматриваемые базисы мы будем считать наследственными, то есть содержащими вместе с функцией все остаточные подфункции Через Д обозначим базис всех функций I переменных Бесловторные в В{ функции будем называть 2-бесповторными Функции, бесповторные в В2, будем просто называть бесповторными
Представляет содержательный интерес следующая постановка задачи Дана бесповторная в некотором базисе В функция /(жь ,хп), существенно зависящая от всех своих переменных Требуется построить проверяющий тест для }{х\, ,хп) на множестве всех бесповторных в этом базисе функций, зависящих от переменных ,х„ произвольным образом Эту задачу назовем построением теста для / относительно бесповторной альтернативы
Задача имеет следующую интерпретацию Бесповторные функции и только они реализуются схемами из функциональных элементов без каких-либо ветвлений Константные неисправности и нарушения работы элементов не приводят к потере свойства бесповторно-сти Бели мы хотим проверить, реализует ли данная нам схема без ветвлений с множеством входов ,хп, неизвестным конкретным внутренним строением и неизвестными неисправностями функцию /(аг1, ,хп), то нам требуется решить рассматриваемую задачу
Функция а переменных (в > 3) называется собственной (или «-собственной), если она не является а — 1—бесповторной
Дерево, соответствующее бесповторной формуле, называется правильным, если оно удовлетворяет следующим условиям
1 Листья помечены попарно различными переменными
2 Отрицания могут быть лишь вершинами, смежными с листьями
3 Внутренние вершины помечены одним из следующих символов
к, V, ф, © (вершины любой степени захода, которым соответствует конъюнкция, дизъюнкция, сумма по модулю 2 или ее отрицание) или символами, соответствующими «-собственным функциям (только для вершин степени захода в)
4 Смежные вершины не могут быть помечены одинаковыми символами из множества
{&, V, ф, ©} а также символами фиф одновременно
Пусть подфункция/(7Ь , 7!-1>ж1>7и-ь ,7п) функции }{хи ,хп)
является существенной Тогда множество наборов
назовем квадратом существенности переменных х% и х3 функции / Множеством квадратов существенности функции назовем произвольное множество наборов, которое для любой пары существенных переменных содержит некоторый квадрат их существенности Теорема 2 2 1 Множество квадратов существенности произвольной бесповторной функции является проверяющим тестом относительно бесповторной альтернативы Из этой теоремы вытекает оценка функции Шеннона для длины теста
Хребтом бесповторной функции назовем правильное дерево, из которого можно получить правильное дерево для соответствующей этой функции формулы навешиванием отрицаний на функции, реализуемые в некоторых вершинах
Следующим важным понятием является таблица существенности Таблица суще-
первом столбце каждой строки содержится свой набор переменных хч, , хч Во втором столбце содержится набор п — I констант а3 для {11, В третьем столбце содер-
жится подфункция, получаемая из /(хд, ,хп) подстановкой констант а и существенно зависящая от всех своих переменных Выбор констант из второго столбца при этом определяется произвольным образом Если же такой выбор невозможен, то второй и третий столбцы содержат прочерки
Теорема 2 3 1 По таблице существенности 1-бесповгпорной функции / можно получить некоторый ее хребет
(71. >7г-1>°>7«+1. ,7з-1>°,7з+1> ,7п)
(71. .7»-1.0,7>+1. ,73-1.1.73+1. .7п)
(71. . 71-1.1.7>+1> . 7з-1.0.7?+1> .7»)
(71. > 7>-1.1.7«+1. ,7з-ь 1.7з+1. .7«)
ственности ¿-бесповторной функции ¡{х\, ,хп) содержит три столбца и (") строк В
Лемма 2 3 5 Таблица существенности 1-бесповторной функции и произвольный ее хребет однозначно определяют бесповторную функцию
Гиперкубом существенности ¿-бесповторной функции называется множество 2г наборов аргументов и значений функции на этих наборах, содержащее для некоторых I переменных все возможные поднаборы значений, совпадающих в оставшихся компонентах, и таких, что соответствующая остаточная функция существенно зависит от всех I переменных
Множеством гиперкубов существенности ¿-бесповторной функции называется множество наборов аргументов и значений функции на этих наборах, содержащее для каждого набора I переменных, если это возможно, 2' наборов, совпадающих в оставшихся компонентах, и таких, что соответствующая остаточная функция существенно зависит от всех I переменных
Булева функция <2(х, у), существенно зависящая от своих аргументов, называется дискриминирующей, если при любом выборе констант а остаточная подфункция ё(а, у) имеет фиктивную переменную Для конкретной дискриминирующей функции могут, вообще говоря, существовать несколько способов разбиения переменных на множества х и у
Теорема 2 3 2 Пусть произвольный хребет 1-бесповторной функции п переменных не содержит дискриминирующих функций, зависящих от 1—2 и менее переменных Тогда длина минимального теста этой функции не превосходит 21 ф
Из этой теоремы вытекает оценка функции Шеннона для длины теста в базисе всех функций трех переменных
Введем в рассмотрение каноническое дерево в базисе Вз Среди всех древесных представлений каноническое дерево должно удовлетворять следующим требованиям
1 Отрицания могут быть лишь вершинами, смежными с листьями
и в базисе функций четырех переменных Теорема 2.3 3
2 Внутренние вершины помечены одним из следующих символов
V, ф, © (вершины любой степени захода, которым соответствует конъюнкция, дизъюнкция, сумма по модулю 2 или ее отрицание) или
d, m, sf, sf*, XORs, ХОЩ, n, n* (только для вершин степени захода 3, где /* — двойственная функция)
3 Смежные вершины не могут быть помечены одинаковыми символами из множества {&, V, ©, в}, а также символами ©, © одновременно
4 Положительными считаются переменные без отрицаний,V, ©, функции трех переменных, имеющие больше половины единиц, функция d и медиана с двумя или тремя положительными входами Все входы вершин ©, ф, а также вход у вершины d(x, у, z) должны быть положительными
Теорема 2 3 5 Для любой 3-бесповторной функции существует единственное каноническое дерево
Рассмотрим теперь задачу построения теста относительно бесповторной альтернативы для заданной булевой функции, выразимой бесповторной формулой в базисе Во = {0,1, &, V, -i} и существенно зависящей от переменных х\, ,х„ Теорема 2.4 1. п + 1 < ТВо(п) < 3 Ьп
Следующая теорема дает представление о возможных значениях длины минимального теста для конкретных функций, бесповторных в базисе Вч
Теорема 2.5 1 1) Пусть функция £(п) удовлетворяет условиям lim ^^ = оо и lim ^^ < i Тогда существует последовательность функций {fn}, для
п—»00 п п—'СО ^ J/
которых выполняется соотношение T(fn) ~ £(п) при п —> оо
2) Для любой неотрицательной константы ip существует последовательность бесповторных функций {fn(xi, , s>i)} такая, что
Ф п< Т(/„) <{ф + 3) п + O(Vn)
при п —♦ оо
Упоминаемые в теореме 2 5 1 последовательности функций в работе построены в явном виде
Информация о значениях функции на множестве квадратов (гиперкубов) существенности зачастую является избыточной При тестировании используется восстановление этой информации по имеющейся
Третья глава посвящена решению задачи распознавания свойств дискретных функций, задаваемых вектор-столбцом, схемами из функциональных элементов Мы представим общий метод распознавания принадлежности функций классам, замкнутым относительно подстановки констант, использующий разложение по переменной Входом схемы является вектор-столбец значений функции, а выходом — бит, равный 1 для функций, обладающих заданным свойством, 0 - иначе
Теорема 3 11 (основная) Пусть Р — произвольный класс булевых функций, замкнутый относительно подстановки констант на место переменных, и п^стга> для заданной последовательности {/3(т)} существуют кодирование функций, принадлежащих .К, и последовательность схем {£т}, го = 1,2, , обладающие следующими свойствами
1 Сложность кодирования констант равна /3(0)
2 Если на вход произвольной схемы Ет подать коды подфункций
/(Ж1, ,2?т-1,0) и }(х\, ,жт_1,1), принадлежащих Р, то выход схемы Ет содержит бит, распознающий принадлежность функции /(ж1, ,хт) классу Р
3 Если функция /(#1, ,хш) принадлежит классу Р, то выход схемы Зто содержит код функции /(жь ,хт)
4 Сложность схемы £т не превосходит р(т)
Тогда существует схема распознающая принадлежность классу Р произвольной функции п переменных, представленной в виде вектор-столбца значений, сложности не более
(2п - 2Щх&х!) + £ 2"~к р{к),
к=О
где Ь{х1&1хг) — сложность реализации конъюнкции двух переменных
Следствие Если ряд £ сходится, то принадлежность инвариантному классу к=о
распознается с линейной сложностью относительно 2™ — длины вектор-столбца булевой функции
Теорема 3 2 1 Пусть N — 2" Тогда существует схема из функциональные элементов Sn сложности 0(N^/logNloglogN), входом которой является вектор-столбец значений булевой функции п переменных, распознающая монотонность входной функции
Теорема 3 2 2 Для множества функций f {0, ,k - 1}" —> {0, ,1-1}, задаваемых вектором значений длины N = кп, частичного порядка R на {0, ,k — 1}, частичного порядка Rj на {О, ,1 — 1} существует схема из конечнозначных функциональных элементов сложности О (JVy'log JV log log N), распознающая их монотонность Не всюду определенная булева функция называется частичной монотонной, если для нее существует монотонное доопределение Каждое значение частичной булевой функции может быть закодировано двумя битами
Теорема 3.3 1 Существует последовательность схем {5ге}, распознающих частичную монотонность произвольной функции п переменных, заданной векторно, сложности 0(2"y/nlogn)
Пусть для функции/(®i, ,хп) существует вектор /3 такой, что функция/(sj1, монотонна Тогда функция /(жi, ,хп) называется поляризуемой
Теорема 3 4 1 Существует последовательность схем {5П}, распознающих поляризуемость произвольной функции п переменных, заданной векторно, сложности
Теорема 3.5 1. Существует последовательность схем {5П} сложности 0(2"), распознающих доопределимость до линейной произвольной частичной булевой функции п переменных, заданной векторно
Пусть ф(к) — неубывающая функция, определенная на множестве целых неотрицательных чисел и принимающая целые неотрицательные значения Рассмотрим класс Рф булевых функций, имеющих для любого к среди первых к переменных не менее ф(к) фиктивных
Теорема 3 6 1 Существует последовательность схем {£»}, распознающих принадлежность булевой функции {{х^, ,хп) классу Рф, сложности
0(2"VSlogn)
(3 6 1)
Следствие 1 Пусть в условиях теоремы ф(к) > (1 + е) 1с®2 к при всех к > ко Тогда схемы {¿У имеют асимптотически линейную сложность по N
Следствие 2 Пусть в условиях теоремы ф(к) > (1 + е) к при всех к > кц
Тогда схемы {5П} асимптотически имеют сложность ${N10% Щ
Теорема 3.7 1. Для любого конечного наследственного базиса В существует последовательность схем {¿У, распознающих бесповторность в базисе В булевых функций п переменных, заданных векторно, сложности 0(2")
Список литературы
[1] Алексеев В Б Логические полукольца и их использование для построения быстрых алгоритмов / / Вестн Моек ун-та, Сер 1 Матем Механика 1997 N0 1 С 22-29
[2] алексеев В Б О числе монотонных й-значных функций // Пробл киберн Вып 28 М Наука, 1974 С 5-24
[3] Алексеев В Б О числе функций в классах, задаваемых центральными предикатами // Матем заметки 1985 37 Вып 6 С 880-885
¡4] Алексеев В Б От метода Карацубы для быстрого умножения чис ел к быстрым алгоритмам для дискретных функций // Тр матем ин-та им В А Стеклова Т 218 1997 С 20-27
[5] Зуев Ю А Комбинаторно- вероятностные и геометрические методы в пороговой логике // Дискр матем 1991 3 Вып 2 С 47-57
[6] карацуба А А , ОфМАН Ю П Умножение многозначных чисел на автоматах // Докл АН СССР 1962 145 хЧо 2 С 293-294
[7] катериночкина Н Н Поиск максимального верхнего нуля монотонной функции алгебры логики // Докл АН СССР 1975 224 N0 3 С 557-560
[8] Катериночкина Н Н Поиск максимального нуля для некоторых классов монотонных функций из классификации Поста // Журн выч матем и матем физики 1988 28 No 9 С 1397-1406
¡9) КОРОБКОВ В К К вопросу о числе монотонных функций алгебры логики // Дискр анализ Вып 1, Новосибирск, 1965 С 24-27
[10] КОРШУНОВ А Д О числе монотонных булевых функций / / Пробл киберн Вып 38 М Наука, 1981 С 5-108
[11] Кузнецов ABO бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр матем ин-та им В А Стеклова 1958 Т 51 С 186-225
[12] Сапоженко А А Проблема Дедекинда и метод граничных функционалов // Матем вопр киберн Физматлит Вып 9, 2000 С 161-220
[13] Сапоженко А А О поиске максимального верхнего нуля монотонных функций на ранжированных множествах // Журн выч матем и матем физики 1991 31 No 12 С 1871-1884
[14] Соколов Н А Поиск максимального верхнего нуля для одного класса монотонных дискретных функций // Докл АН СССР 1980 251 No 5 С 1077-1080
[15] Соколов н А О поиске максимального верхнего нуля для одного класса монотонных функций конечнозначной логики // Журн выч матем и матем физики 1981 21 No 6 С 1552-1565
[16] чегис й А , яблонский С В Логические способы контроля работы электрических схем // Тр матем ин-та им В А Стеклова Том 51 1958 С 270-360
[17] ЧерухИН Д Ю Алгоритмический критерий сравнения булевых базисов // Матем вопр киберн Вып 8 М Физматлит, 1999 С 77-122
[18] яблонский с В Об алгоритмических трудностях синтеза минимальных контактных схем // Пробл киберн Вып 2 М Физматгиз, 1959 С 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 booléennes monotones den variables //С R. Acad Sa Paris, 1966, 262, p 1088-1090 ( Русский перевод Апсель Ж О числе монотонных булевых функций п переменных // Киберн сб , изд-во Мир Новая серия Вьш 5,1968 С 53-57)
[21] Kleitman D On Dedekmd's problem the number of monotone Boolean functions // Proc Amer Math Soc , 1969, 21, N 3, p 677-682 (Русский перевод Клейтмен Д О проблеме Дедекинда число монотонных булевых функций // Киберн сб , изд-во Мир Новая серия Вып 7, 1970 С 43-52).
[22] strassen v Gaussian elimination is not optimal // Numerische Mathematik, 13, h 4, 1969, p 354-356 (Русский перевод штрассен В Алгоритм Гаусса не оптимален // Киберн сб , изд-во Мир Новая серия Вып 7, 1970 С 67-70)
Список основных публикаций автора по теме диссертации
[23] ВОРОНЕНКО А А Бесповторность распознается схемами линейной сложности // Дискр матем 2005 17 Вып 4 С 111-115
[24] Вороненко А А О длине проверяющего теста для бесповторных функций в базисе {0,1, &, V, ->} // Дискр матем 2005 17 Вып 2 С 139-143
[25] Вороненко А А О количестве замкнутых многомерных монотонных отображений // Вестн Моек ун-та Сер 15 Выч матем и киберн 2002 No 2 С 41-45
[26] вороненко А А О количестве замкнутых экстенсивных отображений // Вестн Моек ун-та Сер 15 Выч матем и киберн 2001 No 4 С 46-48
[27] Вороненко А А О количестве метрических дискретных функций п переменных // Матем вопросы кибернетики M Физматлит, 1998 Вып 7 С 203-212
[28] ВОРОНЕНКО А А О количестве метрических функций булева куба // Дискр матем 2001 13 Вып 4 С 116-121
[29] Вороненко А А О количестве многомерных монотонных экстенсивных отображений // Вестн Моек ун-та Сер 15 Выч матем и киберн 2001 N0 1 С 37-40
[30] ВОРОНЕНКО А А О методе разложения для распознавания принадлежности инвариантным классам // Дискр матем 2002 14 Вып 4 С 110-116
[31] ВОРОНЕНКО А А О проверяющих тестах для бесповторных функций //Матем вопр киберн Выл 11 М Физматлит, 2002 С 163-176
[32] ВОРОНЕНКО А А О распознавании наличия растущего числа фиктивных переменных булевых функций // Вестн Моек ун-та Сер 15 Выч матем и киберн 2003 N0 2 С 45-46
[33] Вороненко А А О росте количества дискретных липшицевых функций при растущей размерности области определения // Вестн Моек ун-та Сер 1 Математика и механика, 2000 N0 2 С 3-7
[34] вороненко А А О сложности распознавания монотонности // Матем вопр киберн Вып 8 М Наука, 1999 С 301-303
[35] ВОРОНЕНКО А А О тестировании бесповторных функций // Вестн Моек ун-та Сер 15 Выч матем и киберн 2006 N0 2 0 45-48
[36] Вороненко А А Об одном подходе к задачам оценки количества дискретных функций // Вестн Моек ун-та Сер 15 Выч матем и киберн 2004 N0 1 С 42-47
[37] ВОРОНЕНКО А А Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикл матем и информатика 2003 15 С 85-97
[38] вороненко А А Об условиях полной асимптотики мощности классов функций к-значной логики, сохраняющих конечноместный предикат // Вестн Моек ун-та Сер 15 Выч матем и киберн 1997 N0 3 С 44-47
[39] ВОРОНЕНКО А А Распознавание бесповторности в произвольном базисе // Прикл матем и информатика 2006 23 С 67-84
Список остальных публикаций автора по теме диссертации
[40] Вороненко А А О мощности некоторых классов дискретных функций // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики Ульяновск, 1996 С 36-37
[41] ВОРОНЕНКО А А Асимптотика логарифма мощности классов функций k-зяачной логики, удовлетворяющих части аксиом монотонности // Труды II Международной конференции "Дискретные модели в теории управляющих Систем" М Диалог^МГУ, 1997 С 14-15
[42] вороненко А А О росте количества нерастягивающих отображений декартовых степеней графов // Математические методы и приложения Труды шестых математических чтений МГСУ М Изд-во МГСУ "Союз 1999 С 51-54
[43] ВОРОНЕНКО А А О распознавании монотонности // Проблемы теоретической кибернетики Тезисы докладов XII Международной конференции Н Новгород, 1999 г М Изд-во мех-мат ф-та МГУ, 1999 Часть I С 42
[44] ВОРОНЕНКО А А О количестве замкнутых экстенсивных монотонных отображений // Труды IV Международной конференции "Дискретные модели в теории управляющих систем" М МАКС Пресс, 2000 С 19-21
[45] ВОРОНЕНКО А А О количестве некоторых отображений, связанных с базами данных и знаний // Интеллектуализация обработки информации ИОИ'2000 Тезисы докладов Симферополь, 2000 С 21
[46] Bopohehko A A On the Complexity of the Monotomcity Verification // Proceedings 15th Annual IEEE Conference on Computational Complexity 2000, p 235-238
[47[ Bopohehko А А О количестве многомерных отображений, удовлетворяющих части аксиом замыкания // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям М Изд-во механико-математического ф-та МГУ, 2000 С 26-27
[48] Bopohehko А А Раскраски и нижние оценки количества функций, сохраняющих близость // Материалы VII Международного семинара "Дискретная математика и ее
приложения "М Изд-во механико-математического ф-та МГУ Часть II 2001 С 212215
[49] Воронбнко А А Об уточненных нижних оценках количества метрических функций // Матем вопр киберн Вып 10 М Физматлит, 2001 С 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
Напечатано с готового оригинал-макета
Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 29 08 2007 г Формат 60x90 1/16 Услпечл 1,5 Тираж 100 экз Заказ 401
119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к Тел 939-3890,939-3891 Тел /Факс 939-3891
ВВЕДЕНИЕ
Глава 1. ОЦЕНКИ КОЛИЧЕСТВА ДИСКРЕТНЫХ ФУНКЦИЙ
§1.1. О КОЛИЧЕСТВЕ МЕТРИЧЕСКИХ ФУНКЦИЙ БУЛЕВА КУБА
§1.2. АСИМПТОТИКА ЛОГАРИФМА КОЛИЧЕСТВА ОТОБРАЖЕНИЙ, УДОВЛЕТВОРЯЮЩИХ ЧАСТИ АКСИОМ ЗАМЫКАНИЯ
§1.3. ОБ ОДНОМ ПОДХОДЕ К ЗАДАЧАМ ОЦЕНКИ КОЛИЧЕСТВА ДИСКРЕТНЫХ ФУНКЦИЙ
Глава 2. ТЕСТИРОВАНИЕ БЕСПОВТОРНЫХ ФУНКЦИЙ
§2.1. ОСНОВНЫЕ ПОНЯТИЯ И ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ
§2.2. БЕСПОВТОРНЫЕ ФУНКЦИИ В БАЗИСЕ ВСЕХ ФУНКЦИЙ ДВУХ ПЕРЕМЕННЫХ
§2.3. ТЕСТИРОВАНИЕ В БОЛЫПЙХ БАЗИСАХ
§2.4. ТЕСТИРОВАНИЕ В ЭЛЕМЕНТАРНОМ БАЗИСЕ
§2.5. ПОСТРОЕНИЕ БЕСПОВТОРНЫХ ФУНКЦИЙ С РАЗЛИЧНОЙ ДЛИНОЙ ПРОВЕРЯЮЩЕГО ТЕСТА
Глава 3. МЕТОД РАЗЛОЖЕНИЯ ДЛЯ РАСПОЗНАВАНИЯ НАСЛЕДСТВЕННЫХ СВОЙСТВ
§3.1. ОСНОВНАЯ ТЕОРЕМА
§3.2. О СЛОЖНОСТИ РАСПОЗНАВАНИЯ МОНОТОННОСТИ
§3.3. ЧАСТИЧНЫЕ МОНОТОННЫЕ ФУНКЦИИ
§3.4. ПОЛЯРИЗУЕМЫЕ ФУНКЦИИ
§3.5. ЧАСТИЧНЫЕ ЛИНЕЙНЫЕ ФУНКЦИИ
Диссертация посвящена исследованию трех типов задач теории дискретных функций: проблемы подсчета количества функций, проблемы тестирования бесповторных функций и проблемы распознавания свойств дискретных функций по вектор-столбцу. Эти задачи рассматриваются для классических объектов: монотонных функций, бесповторных функций, функций, сохраняющих конечноместные предикаты, и других. При решении всех этих задач наибольшая трудность состоит в построении удачных представлений функций.
В первой главе рассматриваются задачи оценки количества функций п переменных и многомерных отображений, обладающих различными свойствами, на уровне асимптотики логарифма.
Среди задач о подсчете числа функций наиболее интенсивно исследовалась проблема Дедекинда [155] — оценка количества монотонных булевых функций. В работе В. К. Коробкова [98], а также в работе Ж. Анселя [160] был найден порядок логарифма количества монотонных булевых функций. Д. Клейтмен [162] установил асимптотику логарифма количества монотонных булевых, а В. Б. Алексеев [6] — /г-значных функций. Позднее А. Д. Коршуновым в [102] была найдена асимптотика мощности для класса монотонных булевых функций. Наиболее компактно этот результат изложен в работе [116]. Цикл работ А. А. Сапоженко [ИТ]—[120], посвящен оценке количества монотонных функций на расширителях. Из последних работ по данной тематике отметим [34], [91], [139]. Подробный обзор современного состояния исследований монотонных булевых функций сделан
А. Д. Коршуновым [100].
Один из первых результатов по оценке количества дискретных функций содержится в работе С. В. Яблонского [150], посвященной инвариантным классам. Совсем недавно в этой области появилась работа О. М. Касим-Заде [93]. В. Б. Алексеевым в работе [9] получена асимптотика логарифма мощности предполных классов в Pk- Также в цикле работ Г. Г. Аманжаева изучались дискретные аналоги гладких функций (см. [23]—[33]). Из близких к рассматриваемой следует отметить задачу о нахождении асмпто-тики логарифма числа пороговых функций, решенную Ю. А. Зуевым (см. [83, 84]). Позднее эта проблема изучалась в работах [86]—[88] и [109]. Близкими по формулировке вопросами — изучением наследственных классов графов занимался В. Б. Алексеев вместе с учениками [17]—[21], [129]. Проблемы, близкие к рассматриваемым задачам по постановкам, рассматривались в работах [89, 90], [136], [137, 138]. Отметим ряд других работ, в которых оценивается (или фактически оценивается) число дискретных функций п переменных или отображений со специальными свойствами: [79, 101, 103, 104, 94, И, 82].
В §1.1 рассматриваются функции, отображающие соседние вершины булева куба в соседние или совпадающие вершины произвольного графа Н. Для последовательности классов таких функций Fn(H) найден предел Jim 2^\Fn{H)\ (теорема 1.1.1), что эквивалентно нахождению асимптотики логарифма мощности. Для доказательства используется метод жирных точек (см. ниже) и вариант теоремы о том, что функция в некоторой точке принимает значение не больше среднего.
Пусть задан частичный порядок 5. Для его декартовой степени 8п в §1.2 рассматриваются отображения £п в себя, удовлетворяющих двум из трех аксиом замыкания:
УхУу х > у ==>■ ф(х) > ф{у) (монотонность) (1.2.1)
Ух ф(х) > х (экстенсивность) (1.2.2)
Ух ф(ф(х)) = ф(х) (замкнутость) (1.2.3)
В [8, 153, 156] была изучена связь между задачами о числе монотонных булевых функций, о числе систем подмножеств, замкнутых относительно пересечений, и рядом задач, связанных с моделями зависимости для баз данных. Получение асимптотики логарифма для отображений, удовлетворяющих ровно одной из аксиом, тривиально. В диссертации сначала доказываются свойства экстенсивных монотонных отображений (теоремы 1.2.1 и 1.2.2) — задача сводится к оценке количества некоторых многомерных монотонных отображений и отдельно рассматривается вырожденный случай. Далее находится асимптотика логарифма (теорема 1.2.3). Теорема 1.2.4 утверждает, что добавление условия замкнутости не уменьшает главный член асимптотики логарифма числа экстенсивных многомерных отображений. Теорема 1.2.5 утверждает, что добавление условия замкнутости не уменьшает главный член асимптотики логарифма числа монотонных многомерных отображений. Основную сложность представляют анализ вырожденного случая (теорема 1.2.2 — необходимо замкнутые порядки) и получение нижних оценок для монотонных замкнутых многомерных отображений (теорема 1.2.5).
В §1.3 рассматриваются классы /г-значных функций, сохраняющих двуместные предикаты. Многие замкнутые классы в (см. [151]) являются классами сохранения конечноместного предиката. Для оценки количества функций в классах предложен следующий подход.
Пусть {Fn} — произвольная последовательность множеств функций тг переменных. Пусть {Нп} — некоторая последовательность множеств. Пусть {фп} — последовательность произвольных всюду определенных отображений, действующих из Fn в Нп. Отметим, что однозначность отображений фп не требуется. Последовательность множеств {Нп} логарифмически мала относительно {Fn}, если выполнено соотношение log\Нп\ = о (log |F„|) при п оо. (1.3.1)
Назовем последовательность точек {%„} жирной, если Хп £ Нп для любого п и справедливо асимптотическое равенство log max К1 Ml ~ log |<^~1(Хтг)| при п оо. (1.3.2)
Xt-Пп
Лемма 1.3.1 (Метод жирных точек). Пусть последовательность точек {хп} является жирной для некоторой последовательности множеств {Fn}, образов Нп и функций фп. Пусть последовательность множеств {Нп} логарифмически мала относительно {Fn}. Тогда log |F„| ~ log |ф~1{Хп)\ при п -> оо.
Суть метода жирных точек состоит в том, чтобы связать с каждой из функций из оцениваемого множества некоторую характеристику так, чтобы различных характеристик было мало и можно было хорошо оценить наибольшую по всем характеристикам мощность прообраза. Тогда ее логарифм асимптотически совпадет с логарифмом количества функций в исходном множестве. В §1.3 получена (теоремы 1.3.1 и 1.3.2) асимптотика логарифма количества /с-значных функций, сохраняющих двуместные предикаты, сходные с теми, которые сохраняют монотонные функции: транзитивные при наличии иррефлексивной точки и рефлексивные при наличии симметричной пары. Кроме этого, была получена асимптотика логарифма количества функций, сохраняющих двуместный предикат, истинный на всех неравных парах (теорема 1.3.3).
Заметим, что почти все результаты §1.1 и §1.2 фактически получены при помощи метода жирных точек.
Вторая глава посвящена исследованию бесповторных булевых функций. Одним из первых утверждений теории бесповторных функций была теоре- ' ма А. В. Кузнецова (см., напр., [106]) о конечной полной системе тождеств для бесповторных формул. О применении бесповторных функций можно прочесть в монографии [146], а также в работе [158]. Задача тестирования была впервые подробно описана в работе С. В. Яблонского и И. А. Чегис [140], один из последних обзоров по этой тематике содержится в работе [105]. Очень похожая по формулировке, но существенно отличающаяся по содержанию задача диагностирующего тестирования контактных схем решалась в работе [107]. Ранее активно изучались различные постановки задачи тестирования для монотонных функций. Проблема расшифровки была решена в [160]. Далее развивалось направление расшифровки монотонных многозначных функций [12,123,124]. Н. Н. Катериночкина [95, 96] решила ряд задач поиска верхнего нуля. В вероятностной постановке эта задача была решена А. А. Сапоженко [121]. Задачам расшифровки и поиска верхнего нуля монотонных функций посвящен цикл работ Н. А. Соколова [125]—[128]. Отметим также работы [97, 81].
Вначале ставится задача построения проверяющего теста относительно бесповторной альтернативы (на множестве всех бесповторных в данном базисе функций, зависящих лишь от существенных переменных тестируемой функции) и описывается вырождение ряда других естественных постановок. Первый параграф посвящен доказательству вспомогательных лемм. В частности, получена нижняя оценка для функции Шеннона длины теста для базиса всех функций I переменных Д вида 0(пг).
В §2.2 решается задача тестирования для бесповторных функций в базисе 1?2 всех функций двух переменных. Для решения этой задачи был предложен метод квадратов существенности. Метод заключается в том, что для каждой пары переменных тестируемой функции рассматриваются произвольные четыре набора аргументов, совпадающие в остальных компонентах и различающиеся в рассматриваемых двух. Если остаточная функция, определенная на этих наборах, существенно зависит от обеих переменных, то такое множество называется квадратом существенности. Множеством квадратов существенности называется множество наборов, содержащее квадраты существенности для всех пар переменных. Было предложено однозначное представление бесповторных функций в виде канонических деревьев. Автором был построен метод восстановления каионического дерева (а, следовательно, и самой функции) по множеству квадратов существенности (теорема 2.2.1). Таким образом, была получена верхняя оценка функции Шеннона Тв2{п) < 4(2). Заметим, что информация о квадратах существенности является зачастую избыточной. Однако то, что функция определяется множеством квадратов существенности, позволяет восстанавливать ее по меньшей информации, восстанавливая по ней и бесповторности множество квадратов существенности (см. теоремы 2.4.1 и 2.5.1). Однозначные бесповторные представления в базисе {&,\/,-|} получались ранее В. А. Гурвичем [78, 77]. Древесное бинарное представление было получено одновременно с каноническим деревом автора в работе [82]. Эти представления использовались для решения других задач, тогда как само по себе однозначное представление в В2 не является трудной проблемой. Цикл работ А. В. Черемушкина посвящен классификации дискретных функций с близкими, но более сильными операциями [141]—[143].
В §2.3 метод квадратов существенности обобщается на классы функций, бесповторных в больших базисах. По аналогии вводится понятие гиперкуба существенности и множества гиперкубов существенности. Главной трудностью на пути обобщения становится наличие в базисах дискриминирующих функций типа ¿(х, у, х) = ху V ух. Например, для функции £3, Х4) невозможно подставить константу на место переменной Ж3 так, чтобы переменные х\,х2,х^ остались существенными. Новым понятием является таблица существенности, содержащая наряду с информацией о значениях на гиперкубах существенности прочерки для тех наборов переменных, для которых соответствующий гиперкуб отсутствует. По таблице существенности функция восстанавливается однозначно (теорема 2.3.1 и лемма 2.3.5). В случае, если представление функции не содержит дискриминирующих функций I — 2 аргументов, она восстанавливается по множеству гиперкубов существенности, и ее тест имеет длину не более 2/(") (теорема 2.3.2). Из этого утверждения вытекает оценка ТВз(п) < 8(") и оценка ТВ4{п) < 16(2) (теоРема 2.3.3). С помощью теоремы 2.3.3 существенно легче тестировать бесповторные схемы из функциональных элементов в базисе В4. Такие схемы могут быть построены в рамках ЕРСА (см. [161] и обзор работы [1]). Для работы с базисом В4 полезно использовать работу [76]. Удалось также построить каноническое представление для базиса всех функций трех переменных (теорема 2.3.4).
В §2.4 доказана линейность функции Шеннона для тестирования в элементарном базисе Во = {&, V, 0,1}. Получена оценка п + 1 < Тв0{п) < 3.5п (теорема 2.4.1).
В §2.5 для базиса В2 построены примеры последовательности бесповторных функций с длинами тестов, растущими с произвольной скоростью от линейной до квадратичной (теорема 2.5.1).
Третья глава посвящена применению метода разложения (теорема 3.1.1 и §3.1) для решения задач проверки принадлежности булевых функций, задаваемых вектор-столбцом, наследственным классам. Ранее в этой области был известен подход В. Б. Алексеева, основанный на использовании алгебраических характеристик распознаваемых свойств (см. [3,14,13, 15,
16, 80]). Некоторые задачи распознавания свойств по вектор-столбцу на несколько другом языке фактически ставятся в работе [75]. Рассматриваемая задача является частным случаем другой проблемы: существует ли для задачи алгоритм лучше (проще) "естественного". Первый результат в этом направлении был получен А. А. Карацубой [92] для умножения чисел. Другое широко развивающееся направление связано с результатом В. Штрассена об умножении матриц [163]. Суть метода разложения состоит в построении кода функций по кодам подфункций, заведомо обладающих распознаваемым свойством. При помощи этого метода получены все результаты третьей главы.
В §3.2 при помощи метода разложения получена последовательность схем {Sn} сложности О(Ny/log N log log N), распознающих монотонность булевых функций тг переменных, заданных вектор-столбцом длины N = 2п (теорема 3.2.1). Этот результат обобщен на случай большей значности областей определения и значений дискретных функций (теорема 3.2.2).
В §3.3 рассматривается свойство не всюду определенных булевых функций быть доопределимыми до монотонных (частичная монотонность). Также получена оценка сложности соответствующей последовательности схем 0(Ny/hgNlog log N) (теорема 3.3.1).
В §3.4 рассматривается свойство поляризуемости функций — возможность получения из них монотонных заменой некоторых переменных на отрицания. Также доказана оценка сложности соответствующей последовательности схем 0(Ny/\ogN log log N).
В §3.5 строится последовательность схем линейной сложности, распознающих доопределимость входной частично определенной функции до линейной (теорема 3.5.1).
В. Б. Алексеев предложил метод логических полуколец (см. [3]), с помощью которого удалось понизить верхние оценки сложности для большого числа задач. Нижняя оценка для этого метода связана с возможностью получения удачного алгебраического представления исследуемого свойства. В частности, для схемного распознавания монотонных функций сложность распознавания методом логических полуколец равняется fi(iVlogiV). Основным препятствием для удачного применения основной теоремы 3.1.1 является длина кода и, следовательно, мощность класса функций. Если бы при решении задачи распознавания монотонности удалось применить кодировку Ж. Анселя, а не кодировать каждую цепочку количеством нулей, то полученные схемы имели бы сложность e{Ny/\ogN). Однако полученная оценка (теорема 3.2.1) ближе к этой, чем стандартная O(iVIogiV), получаемая сравнением значений на всех соседних наборах. Для класса частичных линейных функций это препятствие удалось обойти, используя неоднозначно декодируемую кодировку. Класс частичных линейных функций интересен еще и тем, что к нему [10] сходится сверху счетная цепочка замкнутых классов частичной логики, и, следовательно, он не описывается как класс сохранения конечноместного предиката.
Проблема построения схем сложности меньшей, чем O(iVlogiV), для распознавания наличия определенного числа фиктивных переменных рассматривается в §3.6 (теорема 3.6.1 и следствия из нее). Получена последовательность соответствующих схем и описаны условия на рост количества фиктивных переменных, при котором ее сложность линейна, а также условия, при которых она растет как o(N log N).
В §3.7. для произвольного конечного базиса В строится последовательность схем, распознающих бесповторность функции, заданной вектор-столбцом, в этом базисе. Интерес к проверке свойства бесповтор-ности был связан с гипотезой О. Б. Лупанова о том, что критерием эквивалентности формульной сложности для двух базисов является их взаимная бесповторная выразимость. Работы по этой теме [133], [108], [130], [131], [132] увенчались доказательством этой гипотезы Д. Ю. Черухиным [144]. Последние работы [147], [148], [111], [145] по бесповторным функциям посвящены в основном бесповторности в базисах, близких к элементарному. Н. А. Перязев фактически получил [110] алгоритм (последовательность схем сложности 0(N\ogN)) для задачи распознавания бесповторности функций в базисе В^, задаваемых вектор-столбцом. В §3.7 доказана линейность этой задачи для любого базиса (теорема 3.7.1). При помощи представлений работы [77] в статье [159] был получен полиномиальный алгоритм преобразования произвольной формулы для бесповторной в базисе {&, V, -i} функции к бесповторной. Это доказывает, в частности, NP-полноту задачи формульного распознавания бесповторности. А. Н. Гетманов [74] получил почти линейную верхнюю оценку сложности распознавания контактной бесповторности булевых функций. При помощи основной теоремы 3.1.1 ее удалось довести до линейной.
Отметим, что результаты третьей главы не могут быть получены из результатов работы [113], в которой строятся верхние оценки сложности функций, использующие лишь малость числа ее единиц.
Результаты диссертации опубликованы в рецензируемых работах [38]-[55], а также в работах [56]—[71].
1. АЛЕКСЕЕВ В.Б. Лекции по дискретной математике. М.: МАКС Пресс. 2004. 76 с.
2. АЛЕКСЕЕВ В.Б. Логические полукольца и их использование для по- строения быстрых алгоритмов // Вестн. Моск. ун-та, Сер. 1. Матем.Механика. 1997. No 1. 22-29.
3. АЛЕКСЕЕВ В.Б. Метод искусственных ограничений для оценки числа дискретных функций // Матем. вонросы киберн. Вып. 8. М.: Наука,1999. 123-134.
4. АЛЕКСЕЕВ В.Б. О сложности распознавания полноты в /г-значной ло- гике // Труды III Международной конференции "Дискретные моделив теории управляющих систем" (22-27 июня 1998 г.) М.: Диалог-МГУ,1998. 6-8.
5. АЛЕКСЕЕВ В.Б. О числе монотонных /г-значных функций // Пробл. киберн. Вып. 28. М.: Наука, 1974. 5-24.
6. АЛЕКСЕЕВ В.Б. О числе отображений тина замыкания // Дискр. ма- тем. 2004. 16. Вып. 2. 85-97.134
7. АЛЕКСЕЕВ В.Б. О числе семейств подмножеств, замкнутых относи- тельно пересечения // Дискр. матем. 1989. 1. Вып. 2. 129-136.
8. АЛЕКСЕЕВ В.Б. О числе функпий в классах, задаваемых пентральны- ми предикатами // Матем. заметки. 1985. 37. Вып. 6. 880-885.
9. АЛЕКСЕЕВ В.Б. О расшифровке некоторых классов монотонных мно- гозначных функпий // Журн. выч. матем. и матем. физики. 1976. 16.No 1. 189-198.
10. АЛЕКСЕЕВ В.Б. От метода Карапубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функпий // Тр. матем. ин-таим. В.А.Стеклова. Т. 218. 1997. 20-27.
11. АЛЕКСЕЕВ В.Б. О некоторых алгебрах связанных с быстрыми алго- ритмами // Дискр. матем. 1996. 8. Вып. 1. 52-64.
12. АЛЕКСЕЕВ В.Б., КРИВЕНКО М . М . О сложности распознавапия пол- ноты систем функпий в классе Р^ // Вестн. Моск. ун-та. Сер. 1. 1997.No 3. 6-9.
13. АЛЕКСЕЕВ В.В., ЕМЕЛЬЯНОВ Н . Р . Метод построения быстрых ал- горитмов в к-значной логике // Матем. заметки. 38. Вып. 1. 148-156.135
14. АЛЕКСЕЕВ В . Е , СОРОЧАН С В . Об энтропии наследственных классов ориентированных графов // Дискр. анализ и иссл. операций. Сер. 1.2000. 7. No 4. 20-28.
15. АЛЕКСЕЕВ В.Е. О нижних ярусах решетки наследственных классов графов // Дискр. анализ и иссл. операций Сер.1. 1997. 4. No 1. 3-12.
16. АЛЕКСЕЕВ В.Е. Наследственные классы и кодирование графов // Пробл. киберн. Вып. 39. М.: Наука, 1982. 151-164.
17. АЛЕКСЕЕВ В.Е., КОРОБИЦИН Д.В. О сложности некоторых задач на наследственных классах графов // Дискр. матем. 1992. 4. Вып. 4. 34-40.
18. АЛЕКСЕЕВ В.Е., СОРОЧАН В. Об энтропии наследственных клас- сов цветных графов // Дискр. матем. 2000. 12. Вып. 2. 99-102.
19. АЛЕКСЕЕВ В.Е. Область значений энтропии наследственных классов графов // Дискр. матем. 1992. 4. Вып. 2. 148-157.
20. АмАНЖАЕВ г . г . Дискретные функции с заданным модулем непре- рывности // Вестн. Моск. ун-та. Сер. 1. Матем. Механика. 1992. No 5.С. 86-89.
21. АмАНЖАЕВ г . г . О сложности табулирования бесконечно дифферен- цируемых функций и функций, заданных условием Гельдера на произ-водные // Докл. РАН 1999. 364. No 3. 295-298.
22. АмАНЖАЕВ г . г . о классификации дискретных функций различной гладкости // Докл. РАН 1999. 364. No 4. 439-441.136
23. АмАНЖАЕВ Г.Г. о дискретных аналогах аналитических и других бесконечно гладких функций // Вестн. Моск. ун-та. Сер. 1. Матем.Механика. 1995. No 5. 18-23.
24. АмАНЖАЕВ г . г . о дискретных аналогах классов функций, задавае- мых модулем ненрерывной п-й производной // Вестн. Моск. ун-та. Сер.
25. Матем. Механика. 1996. No 2. 3-8.
26. АмАНЖАЕВ г . г . о дискретных аналогах функций дробной гладкос- ти // Вестн. Моск. ун-та. Сер. 1. Матем. Механика. 1996. No 4. 3-7.
27. АмАНЖАЕВ Г.Г. Эффективная конструкция дискретного аналога функций с ограниченной второй производной // Вестн. Моск. ун-та.Сер. 1. Матем. Механика. 1997. No 2. 18-22.
28. АмАНЖАЕВ г . г . Дискретные аналоги бесконечно гладких функций // Дискр. анализ и иссл. операций. 1996. 3. No 3. 3-39.
29. АмАНЖАЕВ Г.Г. Об е-энтропии и дискретных аналогах классов це- лых аналитических функций // Дискр. анализ и иссл. операций. 1996.
31. АмАНЖАЕВ г . г . о дискретных приближениях непрерывных функ- ций с ограниченной второй производной // Дискр. анализ и иссл. опе-раций. 1995. 2. No 2. 5-15.
32. АмАНЖАЕВ г. г . о дискретных аналогах выпуклых функций // Ма- тем. вопр. киберн. Вып. 7. М.; Физматлит, 1998. 54-66.137
33. АНДРЕЕВА Т.В. Развитие метода граничных функционалов и его нри- ложение к комбинаторным задачам // Матем. вопр. киберн. Вып. 13.М.: Физматлит, 2004. 147-222.
34. ВАРЗДИНЬ Я . М . СЛОЖНОСТЬ распознавания симметрии на машинах Тьюринга // Пробл. кибернетики. Вып. 15. М.: Наука, 1965. 245-248.
35. БОРОВКОВ А.А. Теория вероятностей // М.: Наука, 1976. 352 с.
36. БУБНОВ С . Е . Некоторые свойства бесповторных функций // Сб. луч- ших дипломных работ 2006 года. М: Изд. отдел ф-та ВМиК МГУ. 2006.С. 65-66.
37. ВОРОНЕНКО А.А. Бесповторность распознается схемами линейной сложности // Дискр. матем. 2005. 17. Вып. 4. 111-115.
38. ВоРОНЕНКО А.А. О длине проверяющего теста для бесповторных функций в базисе {0,1, к, V, ->} // Дискр. матем. 2005. 17. Вып. 2. 139-143.
39. ВОРОНЕНКО А.А. О количестве замкнутых многомерных монотон- ных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн.2002. No 2. 41-45.
40. ВОРОНЕНКО А.А. О количестве замкнутых экстенсивных отображе- ний // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2001. No 4.С. 46-48.138
41. ВОРОНЕНКО А. А. о количестве метрических дискретных функций п переменных // Матем. вонросы кибернетики. М.: Физматлит, 1998.Вып. 7. 203-212.
42. ВОРОНЕНКО А.А. О количестве метрических функций булева куба // Дискр. матем. 2001. 13. Вып. 4. 116-121.
43. ВОРОНЕНКО А. А. О количестве многомерных монотонных экстенсив- ных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн.2001. No 1. 37-40.
44. ВОРОНЕНКО А.А. О методе разложения для распознавания принад- лежности инвариантным классам // Дискр. матем. 2002. 14. Вып. 4. 110-116.
45. ВОРОНЕНКО А. А. О проверяющих тестах для бесповторных функций // Матем. вопр. киберн. Вып. И. М.: Физматлит, 2002. 163-176.
46. ВОРОНЕНКО А.А. О распознавании наличия растущего числа фик- тивных переменных булевых функций // Вестн. Моск. ун-та. Сер. 15.Выч. матем. и киберн. 2003. No 2. 45-46.
47. ВОРОНЕНКО А.А. О росте количества дискретных липшицевых функций при растущей размерности области определения // Вестн.Моск. ун-та. Сер. 1. Математика и механика, 2000. No 2. 3-7.
48. ВОРОНЕНКО А.А. О сложности распознавания монотонности // Ма- тем. вопр. киберн. Вып. 8. М.: Наука, 1999. 301-303.139
49. ВОРОНЕНКО А.А. О тестировании бесповторных функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2006. No 2, 45-48.
50. ВоРОНЕНКО А.А. Об одном подходе к задачам оценки количества дискретных функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. икиберн. 2004. No 1. 42-47.
51. ВоронЕНКО А.А. Об оценке длины проверяющего теста для некото- рых бесповторных функций // Прикл. матем. и информатика. 2003. 15.С. 85-97.
52. ВоРОНЕНКО А. А. Об уточненных нижних оценках количества мет- рических функций // Матем. вопр. киберн. Вып. 10. М.: Физматлит,2001. 247-251.
53. ВоРОНЕНКО А.А. Об условиях полной асимптотики мощности клас- сов функций /с-значной логики, сохраняющих конечноместный предикат// Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 1997. No 3. 44-47.
54. ВОРОНЕНКО А.А. Распознавание бесповторности в произвольном ба- зисе // Прикл. матем. и информатика. 2006. 23. 67-84.
55. ВОРОНЕНКО А.А. О мощности некоторых классов дискретных функ- ций // Тезисы докладов на XI Международной конференции по пробле-мам теоретической кибернетики. Ульяновск, 1996. 36-37.
56. ВОРОНЕНКО А.А. Асимптотика логарифма мощности классов функ- пий к-значной логики, удовлетворяющих части аксиом монотонности //140Труды II Международной конференции "Дискретные модели в теорииуправляющих Систем". М.: Диалог-МГУ, 1997. 14-15.
57. ВОРОНЕНКО А.А. О росте количества нерастягивающих отображе- ний декартовых степеней графов // Математические методы и при-ложения. Труды шестых математических чтений МГСУ. М: Изд-воМГСУ "Союз", 1999. 51-54.
58. ВоРОНЕНКО А.А. О распознавании монотонности // Проблемы теоретической кибернетики. Тезисы докладов XII Международной кон-ференции. Н. Новгород, 1999 г. М.: Изд-во мех-мат ф-та МГУ, 1999.Часть I. 42.
59. ВоРОНЕНКО А.А. О количестве замкнутых экстенсивных монотон- ных отображений // Труды IV Международной конференции "Дискрет-ные модели в теории управляющих систем". М.: МАКС Пресс, 2000.С.19-21.
60. ВОРОНЕНКО А.А. О количестве некоторых отображений, связанных с базами данных и знаний // Интеллектуализация обработки информа-ции ИОИ'2000. Тезисы докладов. Симферополь, 2000. 21.
61. ВОРОНЕНКО А.А. On the Complexity of the Monotonicity Verification // Proceedings 15th Annual IEEE Conference on ComputationalComplexity. 2000, p. 235-238.
62. BOPOHEHKO A.A. 0 количестве многомерных отображений, удовле- творяющих части аксиом замыкания // Материалы четвертой моло-141дежной научной школы по дискретной математике и ее приложениям.М.: Изд-во механико-математического ф-та МГУ, 2000. 26-27.
63. ВОРОНЕНКО А.А. Раскраски и нижние оценки количества функ- ций, сохраняющих близость // Материалы VII Международного семи-нара "Дискретная математика и ее приложения." М: Изд-во механико-математического ф-та МГУ. Часть П. 2001. 212-215.
64. ВоронЕНКО А.А. Весповторность распознается схемами линейной сложности // Труды VI Международной конференции "Дискретные мо-дели в теории управляющих систем". М.: Макс Пресс, 2004. 25-26.
65. ВОРОНЕНКО А.А. Метод разложения для распознавания принадлеж- ности инвариантным классам // М.: Макс Пресс, 2005.
66. ВОРОНЕНКО А.А. Бесповторные булевы функции // М.: Макс Пресс, 2006.
67. ВОРОНЕНКО А.А. Оценки количества дискретных функций // М.: Макс Пресс, 2006.
68. ГАВРИЛОВ Г . П . , САПОЖЕНКО А.А. Сборник задач по дискретной математике. М.: Паука, 1992. 408 с.
69. ГАЛЬПЕРИН Г.А., ТОЛНЫГО А.К. Московские математические олим- пиады. М.: Просвещение, 1986. 303 с.
70. ГОТМАНОВ А.Н. Распознавание бесповторности булевых функций для некоторых классов схем // Сб. лучших дипломных работ 2005 года.М: Изд. отдел ф-та ВМиК МГУ, 2005. 66-67.
71. ГОРШКОВ С П . О сложности распознавания мультиаффинности, би- юнктивности, слабой положительности и слабой отрицательности буле-вой функции // Обозрение прикл. и промышленной матем. Сер. Дискр.матем. 1997. 4. Вып. 2. 216-237.
72. ГРИНЧУК М . И . СЛОЖНОСТЬ реализации 4-х местных булевых функций схемами в базисе из всех 2-х местных функций // Матем. вопр. киберн.Вып.6. М.: Паука, 1996. 339-342.143
73. ГУРВИЧ В.А. Критерий бесповторности функций алгебры логики // Докл. АН СССР. 1991. 318. No 3. 532-537.
74. ГУРВИЧ В.А. О бесповторных булевых функциях // Успехи матем. наук. 1977. 32. No 1. 183-184.
75. ДЕНИСОВ О.В. Асимптотическая формула для числа корелляционно- иммунных порядка к булевых функций // Дискр. матем. 1991. 3. Вып.
76. ЕМЕЛЬЯНОВ Н . Р . Об одном подходе к построению эффективных ал- горитмов распознавания полноты в многозначных логиках // Матем.заметки. 1986. 39. Вып. 5. 766-775.
77. Золотых Н.Ю., ШЕВЧЕНКО В . Н . Расшифровка пороговых функций к-значной логики // Дискр. анализ и иссл. операций. 1995. 2. No 3. 18-23.
78. ЗУБКОВ О.В. О числе бесповторных булевых функций в базисе l&jV,-!} // Дискр. анализ и иссл. операций. Сер.1. 2003. 10. No 1. 41-60.
79. ЗУЕВ Ю . А . Комбинаторно- вероятностные и геометрические методы в пороговой логике // Дискр. матем. 1991. 3. Вып. 2. 47-57.
80. ЗУЕВ Ю.А. Пороговые функции и пороговые представления булевых функций // Матем. вопросы киберн. Вып. 5. М.: Физматлит, 1994. 5-62.144
81. Избранные вопросы теории булевых функ- ций. Под ред. В.Винокурова и Н.А.Перязева. М.: Физматлит, 2001.192 с.
82. ИРМАТОВ А.А. О числе пороговых функций // Дискр. матем. 1993.
84. ИРМАТОВ А.А. Оценки числа пороговых функций // Дискр. матем. 1996. 8. Вып. 4. 92-107.
85. ИРМАТОВ А.А., Ковиянич Ж.Д. Об асимптотике логарифма числа пороговых функций к-значной логики // Дискр. матем. 1998. 10. Вып.3, 35-56.
86. КАБАТЯНСКИЙ Г.А., ПАНЧЕНКО А.И. Упаковки и покрытия хэммин- гова пространства единичными шарами // Докл. АН СССР. 1988. 303.No 3, 550-552.
87. КАБАТЯНСКИЙ Г.А., ПАНЧЕНКО П.И. Упаковки и покрытия про- странства Хэмминга шарами единичного радиуса // Пробл. передачиинформации. 1988. 24. Вып. 4. 3-16.
88. КАЛИБАРДА Г., ИОВОВИЧ В. О числе монотонных булевых функций с фиксированным числом нижних единиц // Интеллектуальные системы.2003. 7. Вып. 1-4. 299-322.
89. КАРАЦУБА А.А., ОФМАН Ю . П . Умножение многозначных чисел на автоматах // Докл. АП СССР. 1962. 145. No 2. 293-294.145
90. КАСИМ-ЗАДЕ О . М . О метрических свойствах обобщенных инвари- антных классов // Матем. вонр. киберн. Физматлит. Вып. 15, 2006. 9-34.
91. КАТЕРИНОЧКИНА Н . Н . О множествах, содержащих наибольшее чис- ло понарно не сравнимых п-мерных к-ичаых наборов // Матем. замет-ки. 1978. 24. Вып. 3. 367-374.
92. КАТЕРИНОЧКИНА Н.Н. Поиск максимального верхнего нуля монотон- ной функции алгебры логики // Докл. АН СССР. 1975. 224. No 3. 557-560.
93. КАТЕРИНОЧКИНА Н.Н. Ноиск максимального нуля для некоторых классов монотонных функций из классификации Носта // Журн. выч.матем. и матем. физики. 1988. 28. No 9. 1397-1406.
94. КитАЕВ А.Ю. о приближенном вычислении высоты максимального верхнего нуля монотонной булевой функции // Матем. заметки. 1991.
96. КОРОБКОВ В.К. К вопросу о числе монотонных функций алгебры логики // Дискр. анализ. Вып. 1, Новосибирск, 1965. 24-27.
97. КОРОБКОВ В.К. Некоторые обобщения задачи "расшифровки" мо- нотонных функций алгебры логики // Дискр. анализ. Вьш. 5. Новоси-бирск, 1965. 19-25.
98. КОРШУНОВ А.Д. Монотонные булевы функции // Успехи матем. наук. 2003. 58. Вып. 5. 89-162.146
99. КОРШУНОВ А.Д. О мощности и структуре некоторых замкнутых классах Поста (семейств подмножеств конечного множества) // Докл.АН СССР. 1987. 295. No 3. 533-537.
100. КОРШУНОВ А.Д. О числе монотонных булевых функций // Пробл. киберн. Вын. 38. М.: Наука, 1981. 5-108.
101. КОРШУНОВ А.Д. О числе к-неразделенных семейств нодмножеств п-элементного множества (/ -^неразделенных булевых функций от п пе-ременных) // Докл. РАН. 2004. 397. No 5. 593-595.
102. КОРШУНОВ А.Д., САПОЖЕНКО А.А. О числе двоичных кодов с рас- стоянием 2 // Нробл. киберн. Вып. 40. М.: Наука, 1983. 111-130.
103. КУДРЯВЦЕВ В.Б. Теория тестового распознавания // Дискр. матем. 2006. 18. Вып. 3. 3-34.
104. КУЗНЕЦОВ А.В. О бесповторных контактных схемах и бесповтор- ных суперпозипиях функций алгебры логики // Тр. матем. ин-та им.В.А.Стеклова. 1958. Т. 51. 186-225.
105. МАДАТЯН Х.А. ПОЛНЫЙ тест для бесповторных контактных схем // Нробл. киберн. Вып. 23. М.: Наука, 1970. 103-118.
106. МУЧНИК Б.А. Об одном критерии сравнимости базисов при реали- зации функций алгебры логики формулами // Матем. заметки. 1967. 1.Вып. 5. 515-524.
107. Носов М.В. К вопросу о числе пороговых функций // Интеллекту- альные системы. 2003. 7. Вып. 1-4. 381-384.147
108. ПЕРЯЗЕВ Н.А. Реализация булевых функций бесцовторными фор- мулами // Дискр. матем. 1995. 7. Вып. 3. 61-68.
109. ПЕРЯЗЕВ Н.А., ШАРАНХАЕВ И.К. Критерии бесповторности буле- вых функций в предэлементарных базисах ранга 3 // Дискр. матем.2005. 17. Вып. 2. 127-138.
110. РЕДЬКИН Н . П . Надежность и диагностика схем. М.: Изд-во Моск. ун-та, 1992. 192 с.
111. РЕДЬКИН Н.П. О сложности булевых функций с малым числом еди- ниц // Дискр. матем. 2004. 16. Вып. 4. 20-31.
112. РяБЕЦ Л.В. о сложности проверяющих тестов для бесповторных булевых функций // Синтез и семантика логических систем. Материа-лы российской школы-семинара. Иркутск. Изд-во ГОУ ВПО "Иркутс-кий государственный педагогический университет", 2006. 85-87.
113. САПОЖЕНКО А . А . О числе трехзначных функций, удовлетворяю- щих условию Липщица // Труды П Международной конференции "Дис-кретные модели в теории унравляющих систем". М: Диалог-МГУ, 1997.С. 50-51.
114. САПОЖЕНКО А.А. Проблема Дедекинда и метод граничных функ- ционалов // Матем. вопр. киберн. Физматлит. Вып. 9, 2000. 161-220.
115. САПОЖЕНКО А.А. О числе антицецей в ранжированных частично- упорядоченных множествах // Дискр. матем. 1989. 1. Вып. 1. 74-93.148
116. САПОЖЕНКО А.А. О числе антицепей в многослойных ранжирован- ных множествах // Дискр. матем. 1989. 1. Вып. 2. 110-128.
117. САПОЖЕНКО А.А. О числе независимых множеств в расширителях // Дискр. матем. 2001. 13. Вып. 1. 56-62.
118. САПОЖЕНКО А. А. Оценка числа связных множеств в графе и струк- тура компонент случайных подмножеств // Докл. РАН. 1999. 365. No
119. САПОЖЕПКО А.А. О поиске максимального верхнего нуля монотон- ных функций на ранжированных множествах // Журн. выч. матем. иматем. физики. 1991. 31. No 12. 1871-1884.
120. СЕЛЕЗНЕВА С . Н . О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина // Дискр.матем. 1997. 9. Вып. 4. 24-31.
121. СЕРЖАНТОВ А.В. Оптимальный алгоритм расшифровки некоторых классов монотонных функций // Журн. выч. матем. и матем. физики.1983. 23. No 1. 206-212.
122. СЕРЖАНТОВ А.В. Об онтимальном алгоритме расшифровки неко- торых монотонных функций конечнозначной логики // Матем. вопр.киберн. Вып. 1. М: Наука, 1988. 223-233.
123. Соколов Н.А. Поиск максимального верхнего нуля для одного класса монотонных дискретных функций // Докл. АН СССР. 1980. 251.No 5. 1077-1080.149
124. Соколов Н.А. Оптимальная расшифровка монотонных булевых функций // Журн. выч. матем. и матем. физики. 1987. 27. No 12. 1878-1887.
125. Соколов Н.А. Частичная расшифровка монотонных булевых функ- ций // Журн. выч. матем. и матем. физики. 1983. 23. No 5. 1267-1271.
126. Соколов Н.А. О ноиске максимального верхнего нуля для одно- го класса монотонных функций конечнозначной логики // Журн. выч.матем. и матем. физики. 1981. 21. No 6. 1552-1565.
127. СОРОЧАН С В . Об энтронии композиций наследственных классов цветных графов // Дискр. анализ и иссл. операций. Сер. 1. 2002. 9. No
128. СтЕЦЕНКО в.А. О предплохих базисах в Рг // Матем. вопр. киберн. Вып. 4. М: Наука, 1992. 139-177.
129. СтЕЦЕНКО В.А. Об одном необходимом признаке для предмакси- мальных базисов Рг // Докл. АН СССР. 1990. 315. Вып. 6. 1304-1307.
130. СтЕЦЕНКО в.А. О сравнении булевых базисов // Известия вузов. Матем. 1988. No 7. 72-79.
131. СУВБОТОВСКАЯ Б . А . О сравнении базисов при реализации функций алгебры логики формулами // Докл. АН СССР. 1963.149. No 4. 784-787.150
132. Сэвидж Д ж . Э. Сложность вычислений, М.: Факториал, 1998. 368 с.
133. ТРАХТЕНБРОТ Б.А. Сложность алгоритмов и вычислений. Спец- курс для студентов НГУ // НГУ. Новосибирск, 1967.
134. ФЕДОРОВ А. Об одном подходе к оцениванию меры и мощности шаров в двоичных пространствах Хэмминга // Докл. АН СССР. 1984.
136. ФЕДОРЯЕВА Т . И . Операции и изометрические вложения графов, связанные со свойством продолжения метрики // Дискр. анализ и иссл.операций. 1995. 2. No 3. 49-67.
137. ФЕДОРЯЕВА Т.И. Усиленные продолжения метрики // Методы дис- кр. анализа в теории графов и сложности. Вып. 52, 1992. 112-118.
138. ХовРАТОВИЧ Д.В. О мопщости некоторых подклассов монотонных функций // Дискр. матем. 2005. 17. Вып. 4. 81-97.
139. ЧЕГИС И . А . , ЯВЛОНСКИЙ С В . Логические способы контроля рабо- ты электрических схем // Тр. матем. ин-та им. В.А.Стеклова. Том 51.1958. 270-360.
140. ЧЕРЕМУШКИН А . В . Бесповторная декомпозиция сильно зависимых функций // Дискр. матем. 2004. 16. Вып. 3. 3-42.
141. ЧЕРЕМУШКИН А.В. Линейная и аффинная классификация дискрет- ных функций (обзор публикаций) // Матем. вопр. киберн. Вып. 14. М:Физматлит, 2005. 261-280.151
142. ЧЕРЕМУШКИН А . В . Методы аффинной и линейной классификации двоичных функций // Тр. по дискр. матем. 2001. Том 4. 273-314.
143. ЧЕРУХИН Д . Ю . Алгоритмический критерий сравнения булевых ба- зисов // Матем. вонр. киберн. Вын. 8. М: Физматлит, 1999. 77-122.
144. ЧЕРУХИН Д.Ю. О сложностной иерархии булевых базисов // Вестн. Моск. ун-та. Сер. 1. Матем. Механика. 2000. No 3. 48-50.
145. ШАЛЫТО А.А. Логическое управление. Методы аппаратной и про- граммной реализации алгоритмов. СПб. Наука. 2000. 780 с.
146. ШАРАНХАЕВ И . К . О слабо повторных булевых функциях в одном предэлементарном базисе // Дискр. анализ и иссл. операций. Сер. 1.2003. 10. No 2. 79-101.
147. ШАРАНХАЕВ И.К. О булевых базисах второго яруса // Известия вузов. Матем. 2004. No 3. 81-82.
148. ЯБЛОНСКИЙ В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
149. ЯВЛОНСКИЙ В. Об алгоритмических трудностях синтеза мини- мальных контактных схем // Нробл. киберн. Вып. 2. М.: Физматгиз,1959. 75-121.
150. ЯБЛОНСКИЙ С В . Строение верхней окрестности для предикатно- описуемых классов в Pk // Докл. АН СССР. 1974. 218. No 2. 304-307.152
151. ЯБЛОНСКИЙ СВ., ГАВРИЛОВ Г.П., НАБЕВИН А.А. Анализ и синтез схем в многозначных логиках. Часть I. М.: Изд-во МЭИ, 1989. 118 с.
152. BuROSCH G., DEMETROVICS J . , KATONA G.O.H., SAPOZHENKO A.A. On the number of databases and closure operations // MathematicalInstitute of the Hungarian Academy of Sciences. Preprint N 4/1988, 33
153. CHIMEV K. Structural properties of the functions // 7-th International Conference on Discrete Mathematics and Applications. June 17-20, 2004,Bansco, Bulgaria. P. 3-4.
154. DEDEKIND R. Uber Zerlegungen von Zahlen durch ihre grossten gemeinsamen Teilor, Festschrift Hoch. Braunschweig u. ges. Werke, II, 1887,S. 103-148.
156. GOLDREICH 0., GOLDWASSER S., LEHMAN E., RON D. Testing monotonicity // Proceedings of the Annual Symposium on Foundationsof Computer Science. IEEE Computer Society, November 1998, 426-435.
157. GOLDSMITH J., SLOAN R. H., SZORENYI В., TURAN G. Theory revision with queries: horn, read-once, and parity formulas // ArtificialIntelligence. 2004. V. 156. N 2. P. 139-176.153
158. GOLUMBic М. С , MINTS А., ROTICS U . Read-once functions revisted and the readability number of a Boolean function // Electronic Notes inDisctrete Mathematics. 2005. 22. 357-361.
159. STRASSEN V. Gaussian elimination is not optimal // Numerische Mathematik, 13, H. 4, 1969, p. 354-356 (Русский перевод: ШтРАССЕНВ. Алгоритм Гаусса не оптимален // Киберн. сб., изд-во Мир. Новаясерия. Вып.7, 1970. 67-70).154
