Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойств тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Вороненко, Андрей Анатольевич

• Вороненко, Андрей Анатольевич
• доктор физико-математических наук
• 2007

Оглавление диссертации доктор физико-математических наук Вороненко, Андрей Анатольевич

ВВЕДЕНИЕ

Глава 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].

Список литературы диссертационного исследования доктор физико-математических наук Вороненко, Андрей Анатольевич, 2007 год

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