Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Золотых, Николай Юрьевич
01.01.09
Докторская
2013
Нижний Новгород
208 с. : ил.
Стоимость:
499 руб.
Содержание
Список обозначений
Введение
Глава 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) при некотором положительном
Название работы | Автор | Дата защиты |
---|---|---|
О сложности перестройки формальных нейронов | Соколов, Андрей Павлович | 2013 |
Строение младших граней и (P, Q)-раскраски плоских графов | Неустроева, Татьяна Кимовна | 2007 |
Совершенные раскраски бесконечной прямоугольной решетки | Пузынина, Светлана Александровна | 2008 |