Введение
Глава 1. Свойства пороговых и близких к ним функций 32
1.1. Определения исследуемых классов функций 32
1.2. Величина коэффициентов характеристической системы . 35
1.3. Число вершин в P0(f) и P1(f) 38
1.4. Мощностные свойства исследуемых классов функций . 44
1.5. Соотношение между классами T(M) и F0(M) F1(M) . 47
1.6. Построение двойственного описания полиэдра 53
1.6.1. Введение 54
1.6.2. Определения и предварительные сведения . 58
1.6.3. Метод двойного описания 60
1.6.4. Порядок добавления неравенств 62
1.6.5. Методы проверки смежности экстремальных лучей 64
1.6.6. Уменьшение количества рассматриваемых пар смежных лучей 68
1.6.7. Вычислительный эксперимент 69
Глава 2. Алгоритмы расшифровки пороговых и близких к ним функций 74
2.1. Постановка задачи 74
2.2. Безусловные тесты для пороговых функций 78
2.3. Расшифровка функций в классе F0(M) F1(M) 79
2.3.1. Оракульный алгоритм максимизация линейной функции 80
2.3.2. Алгоритм расшифровки в классе F0(M) F1(M) . 83
2.4. Расшифровка пороговых функций 87
2.4.1. Расшифровка функций из класса T+(M) 88
2.4.2. Расшифровка функций из класса T(M) 95
2.4.3. Модификация алгоритма 97
2.5. Расшифровка пороговых функций двух переменных . 99
2.6. Расшифровка пороговых функций, заданных расширенным оракулом 107
Глава 3. Нижние оценки сложности расшифровки 113
3.1. Введение 113
3.2. Свойства конуса разделяющих функционалов 117
3.3. Структура разрешающего множества пороговой функции 120
3.4. Оценки длины обучения в классе пороговых функций . 125
3.5. Другая характеризация минимального разрешающего множества пороговой функции 131
3.6. Верхняя оценка мощности минимального разрешающего множества для одного подкласса пороговых функций . 136
3.7. Неприводимые целочисленные точки политопов 140
3.7.1. Неприводимые точки в параллелепипеде 141
3.7.2. Покрытие политопа параллелепипедами 144
3.7.3. Неприводимые точки в политопе 148
3.8. Верхние оценки длины обучения в классе пороговых функций 150
3.9. Построение минимального разрешающего множества пороговой функции 153
3.10. Минимальное разрешающее множество пороговой функции двух переменных 156
3.10.1. Мощность разрешающего множества 157
3.10.2. Среднее значение мощности минимального разрешающего множества пороговой функции
двух переменных 162
3.10.3. Свойства специальных разбиений плоскости
прямыми 167
3.11. Сложность расшифровки пороговых булевых функций 170
3.12. Оракульная сложность задачи о рюкзаке 171
Глава 4. Расшифровка пороговых функций и диофантовы приближения 174
4.1. Диофантовы приближения вещественных чисел 174
4.2. Связь задачи расшифровки с задачей приближения . 177
4.3. Диофантовы приближения алгебраических чисел 182
Заключение 184
Литература
