Расшифровка пороговых и близких к ним функций

• Автор: Золотых, Николай Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Нижний Новгород
• Количество страниц: 208 с. : ил.

Содержание

Список обозначений

Введение

Глава 1. Свойства пороговых и близких к ним функций

1.1. Определения исследуемых классов функций

1.2. Величина коэффициентов характеристической системы .

1.3. Число вершин в Ро(/) и Р(/)

1.4. Мощностные свойства исследуемых классов функций . .

1.5. Соотношение между классами Х(М) и Зо(-М) П 0ц(М) . .

1.6. Построение двойственного описания полиэдра

1.6.1. Введение

1.6.2. Определения и предварительные сведения
1.6.3. Метод двойного описания
1.6.4. Порядок добавления неравенств
1.6.5. Методы проверки смежности экстремальных лучей
1.6.6. Уменьшение количества рассматриваемых пар смежных лучей
1.6.7. Вычислительный эксперимент
Глава 2. Алгоритмы расшифровки пороговых и близких к ним функций
2.1. Постановка задачи
2.2. Безусловные тесты для пороговых функций
2.3. Расшифровка функций в классе ЗФ(Щ О
2.3.1. Оракульный алгоритм максимизация
линейной функции

2.3.2. Алгоритм расшифровки в классе ЗоОЮ П ^1 (М) .
2.4. Расшифровка пороговых функций
2.4.1. Расшифровка функций из класса Х+(М)
2.4.2. Расшифровка функций из класса %{М)
2.4.3. Модификация алгоритма
2.5. Расшифровка пороговых функций двух переменных
2.6. Расшифровка пороговых функций, заданных
расширенным оракулом
Глава 3. Нижние оценки сложности расшифровки
3.1. Введение
3.2. Свойства конуса разделяющих функционалов
3.3. Структура разрешающего множества пороговой функции
3.4. Оценки длины обучения в классе пороговых функций
3.5. Другая характеризация минимального разрешающего
множества пороговой функции
3.6. Верхняя оценка мощности минимального разрешающего множества для одного подкласса пороговых функций
3.7. Неприводимые целочисленные точки политопов
3.7.1. Неприводимые точки в параллелепипеде
3.7.2. Покрытие политопа параллелепипедами
3.7.3. Неприводимые точки в политопе
3.8. Верхние оценки длины обучения в классе пороговых
функций
3.9. Построение минимального разрешающего множества
пороговой функции
3.10. Минимальное разрешающее множество пороговой
функции двух переменных

3.10.1. Мощность разрешающего множества
3.10.2. Среднее значение мощности минимального разрешающего множества пороговой функции
двух переменных
3.10.3. Свойства специальных разбиений плоскости прямыми
3.11. Сложность расшифровки пороговых булевых функций . .
3.12. Оракульная сложность задачи о рюкзаке
Глава 4. Расшифровка пороговых функций и диофантовы
приближения
4.1. Диофантовы приближения вещественных чисел
4.2. Связь задачи расшифровки с задачей приближения
4.3. Диофантовы приближения алгебраических чисел
Заключение
Литература

Итак, если / 6 Зг,.(М), ту(/) = 1, то / € 5|_У(М), т^у{/) = 1 (у - 0,1). Обозначим Х(М) множество всех пороговых функций, заданных на М.
Утверждение 1.5. Условие
ад) п/>,оо = 0 (1-5)
является необходимым и достаточным для того, чтобы функция / из класса 7д. М) была пороговой.
Доказательство. Пусть / е Х(М), тогда для М,,(/) (у = 0,1) существуют описания в виде (1.3) и (1.4). Отсюда следует соотношение (1.5). Достаточность вытекает из теоремы о разделяющей гиперплоскости (см., например, [69]). I
1.2. Величина коэффициентов характеристической системы
С каждой функцией / 6 Х(М) в (п + 2)-мерном пространстве связан конус К(/') разделяющих функционалов, описываемый следующей системой линейных неравенств относительно переменных (ао, • • •, ап+)
п X а}х] < а0 7=1 для всех (х,,. .., х„) е М)(Я;
п X а]х} > йг0 + ап+, 7=1 для всех (х,,. • • >X/;) <Е
Оц+ -2 б.
Любое решение (оо,..., ап+,) этой системы при ап+ > 0 определяет некоторое пороговое неравенство (1.2) для функции /. Верно и обратное: коэффициенты (а0,... ,я„+,) любого порогового неравенства функции / 6 р'(Л//) удовлетворяют системе (1.6) при некотором положительном