Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойств

• Автор: Вороненко, Андрей Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 154 с.

Глава 1. ОЦЕНКИ КОЛИЧЕСТВА ДИСКРЕТНЫХ ФУНКЦИЙ
§1.1. О КОЛИЧЕСТВЕ МЕТРИЧЕСКИХ ФУНКЦИЙ БУЛЕВА КУБА

§1.2. АСИМПТОТИКА ЛОГАРИФМА КОЛИЧЕСТВА ОТОБРАЖЕНИЙ, УДОВЛЕТВОРЯЮЩИХ ЧАСТИ АКСИОМ ЗАМЫКАНИЯ 23 §1.3. ОБ ОДНОМ ПОДХОДЕ К ЗАДАЧАМ ОЦЕНКИ КОЛИЧЕСТВА ДИСКРЕТНЫХ ФУНКЦИЙ
Глава 2. ТЕСТИРОВАНИЕ БЕСПОВТОРНЫХ ФУНКЦИЙ 52 §2.1. ОСНОВНЫЕ ПОНЯТИЯ И ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ
§2.2. БЕСПОВТОРНЫЕ ФУНКЦИИ В БАЗИСЕ ВСЕХ ФУНКЦИЙ ДВУХ ПЕРЕМЕННЫХ
§2.3. ТЕСТИРОВАНИЕ В БОЛЬШИХ БАЗИСАХ
§2.4. ТЕСТИРОВАНИЕ В ЭЛЕМЕНТАРНОМ БАЗИСЕ
§2.5. ПОСТРОЕНИЕ БЕСПОВТОРНЫХ ФУНКЦИЙ С РАЗЛИЧНОЙ ДЛИНОЙ ПРОВЕРЯЮЩЕГО ТЕСТА
Глава 3. МЕТОД РАЗЛОЖЕНИЯ ДЛЯ РАСПОЗНАВАНИЯ НАСЛЕДСТВЕННЫХ СВОЙСТВ
§3.1. ОСНОВНАЯ ТЕОРЕМА
§3.2. О СЛОЖНОСТИ РАСПОЗНАВАНИЯ МОНОТОННОСТИ 110 §3.3. ЧАСТИЧНЫЕ МОНОТОННЫЕ ФУНКЦИИ
§3.4. ПОЛЯРИЗУЕМЫЕ ФУНКЦИИ
§3.5. ЧАСТИЧНЫЕ ЛИНЕЙНЫЕ ФУНКЦИИ
§3.6. О РАСПОЗНАВАНИИ НАЛИЧИЯ РАСТУЩЕГО ЧИСЛА ФИКТИВНЫХ ПЕРЕМЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
§3.7. РАСПОЗНАВАНИЕ БЕСПОВТОРНОСТИ
ЛИТЕРАТУРА

Диссертация посвящена исследованию трех типов задач теории дискретных функций: проблемы подсчета количества функций, проблемы тестирования бесповторных функций и проблемы распознавания свойств дискретных функций по вектор-столбцу. Эти задачи рассматриваются для классических объектов: монотонных функций, бесповторных функций, функций, сохраняющих конечноместные предикаты, и других. При решении всех этих задач наибольшая трудность состоит в построении удачных представлений функций.
В первой главе рассматриваются задачи оценки количества функций п переменных и многомерных отображений, обладающих различными свойствами, на уровне асимптотики логарифма.
Среди задач о подсчете числа функций наиболее интенсивно исследовалась проблема Дедекинда [155] — оценка количества монотонных булевых функций. В работе В. К. Коробкова [98], а также в работе Ж. Анселя [160] был найден порядок логарифма количества монотонных булевых функций. Д. Клейтмен [162] установил асимптотику логарифма количества монотонных булевых, а В. Б. Алексеев [6] — к-значных функций. Позднее
А. Д. Коршуновым в [102] была найдена асимптотика мощности для класса монотонных булевых функций. Наиболее компактно этот результат изложен в работе [116]. Цикл работ А. А. Сапоженко [117]—[120], посвящен оценке количества монотонных функций на расширителях. Из последних работ по данной тематике отметим [34], [91], [139]. Подробный обзор современного состояния исследований монотонных булевых функций сделан
Лемма 1.3.3.
log* та*ф~Лх) ~ - + 1 {13Щ
х^нп k
Доказательство. Пусть задан набор функций %. Обозначим
Хі = {х | Хі(Ф(х)) = 0},
где ф(х) определяется по правилу (1.3.6). Все множество наборов из {0 к — 1}п можно разбить на /г”-1 подмножеств из к наборов вида
(#1)..., 0), (жі 4" 1 хп~і 1,1) (х -f- к 1 хп— -f- к 1, к 1)
(сложение по модулю к). Рассмотрим произвольное г. Для двух наборов Xі, X2 ИЗ ОДНОГО подмножества невозможно соотношение Хг(^(хх)) = Хг(г/>(х2)) = 0. Поэтому max Хі < кп~~1. Следовательно, при і < s для люХЄ#„
бого набора функций х функция /, принадлежащая ф~г(х), может принимать значение і на некотором множестве, содержащем не более кп~1 точек. Наибольший прообраз Фф1(х) возможен в случае, когда все s множеств наборов Х{ максимальны и не пересекаются. Этот случай реализуется для набора функций х, задаваемого соотношением
Уг (х<(^(х)) = 0 «ф=ф хі = г).
Прообразом х являются все функции /(х), принимающие значения і для г < s только на наборах с х — і. Подсчет логарифма количества таких функций дает в точности правую часть оценки (1.3.10). Лемма 1.3.3 доказана.
Логарифм общего числа различных наборов функций в Нп не превосходит числа s-мерных наборов функций, монотонно отображающих Sn в