Вопросы комитетной полиэдральной отделимости конечных множеств

• Автор: Поберий, Мария Ивановна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Екатеринбург
• Количество страниц: 122 с. : ил.

Содержание
Введение
1 Комитетные решения несовместных систем ограничений
1.1 Понятие комитетного решения и условия его существования
1.2 Разделяющие комитетные конструкции
1.3 Элементы теории вычислительной сложности алгоритмов
1.3.1 Классы Р и NP
1.3.2 Понятие TVP-полноты
1.3.3 Класс NP-трудных задач
1.3.4 Приближенные алгоритмы
1.3.5 L-редукция и класс задач MAX-SNP
1.4 Постановка задачи о минимальном аффинном разделяющем комитете
(MASC) и связанные с ней задачи комбинаторной оптимизации
1.5 Вычислительная сложность и аппроксимируемость задачи о минимальном
аффинном разделяющем комитете (MASC)
2 Задача о минимальном аффинном разделяющем комитете (MASC)
в пространствах фиксированной размерности
2.1 Трудношаемость задачи MASC в пространствах фиксированной размерности
2.2 Трудношаемость задачи MASC: случай общего положения
2.3 Приближенный алгоритм решения задачи MASC-GP(n)
2.4 MAX-SNP-трудность задач MIN-PC и MASC-GP(n)
2.4.1 Схема сведения задачи MAX-3SAT(i) к задаче MIN-PC
2.4.2 MAX-SNP-TpyppocTb задачи MASC-GP(n)
3 Задача обучения распознаванию образов в классе аффинных коми-гетных решающих правил
3.1 Основы сложностной теории обучения распознаванию образов
3.2 Емкость класса аффинных комитетных решающих правил с ограниченным
числом элементов
Заключение
Литература

Введение
При построении математических моделей в экономике, технике, биологии, медицине и других трудноформализуемых областях знания зачастую приходится иметь дело с плохо формализованными или противоречивыми ограничениями. Особенность плохо формализуемых задач состоит в недоопределенности их условий и отсутствии формализованного понятия решения, поэтому возникает необходимость уточнения условий и рассмотрения нескольких вариантов решений для таких задач. При этом построенная модель может оказаться противоречивой.
Несовместные системы ограничений (уравнений или неравенств), возникающие при решении задач принятия решений, оптимизации и классификации, математического программирования и распознавания образов, экономической и медицинской диагностики, приводят к необходимости обобщения классического понятия решения. Традиционным является подход, восходящий к работам П.Л. Чебышева, основанный на непрерывной аппроксимации и заключающийся в ослаблении ограничений исходной задачи, при котором достигается их совокупная непротиворечивость [15]-[20], [52]-[54]. Тогда в качестве обобщенного решения рассматривается решение скорректированной задачи. Однако такой вид обобщения обладает существенным недостатком: строящееся точное решение скорректированной задачи может не удовлетворять ни одному из условий исходной.
Второй подход к коррекции несовместных систем ограничений — дискретный, при котором привычное, сосредоточенное в одном элементе решение заменяется коллективом "квазирешений", каждое из которых удовлетворяет достаточно большой доле условий исследуемой задачи, являясь, по сути, решением некоторой непротиворечивой подсистемы исходной системы ограничений. Одной из математических формализаций дискретного подхода является теория комитетных решений.

Введение
Понятие комитета впервые появилось в работах по распознаванию образов: в совместной статье Эйблоу и Кейлора [77] было введено понятие комитетного решения для системы строгих однородных линейных неравенств
[с^х) > 0 0'еМт). (1)
Конечная последовательность (а?!,..., хд) С Мп называется комитетом системы (2), если всякому неравенству удовлетворяет более половины ее элементов. В работе тех же авторов [78] сформулировано без доказательства достаточное условие существования комитета системы (2) и приведено его геометрическое обоснование.
В более общем виде различные виды обобщения понятия решения на случай несовместных систем были введены в екатеринбургской школе распознавания. Современная теория комитетных конструкций опирается на результаты, полученные Вл.Д. Мазуровым [29]-[32]. Им было доказано необходимое и достаточное условие существования комитета несовместной системы линейных неравенств, получены первые оценки числа членов минимального комитета; введены обобщения понятия комитета (р-комитет, (г,р)-комитет, я-решение и т.д.) и получены условия существования этих конструкций для систем линейных неравенств и некоторых более общих систем включений; предложены и обоснованы вычислительные схемы для построения р-комитетов, в том числе минимальных.
Каждой комитетной конструкции соответствует понятие разделяющей комитетной конструкции и алгоритм распознавания. Согласно [30], разделяющим комитетом (большинства) для конечных множеств А, В из Кп называется последовательность функций
<Э = (/ь/г, • • •,/9), принадлежащих заданному параметрическому семейству Р = {/(•;с) : с€С}с{»"-эК},
таких, что соответствующая данным функциям последовательность значений параметров
(С1,С2, • • •, сч)
является комитетным решением системы неравенств
( /(а; с) > 0 (а £ А)
1 ДЬ;с)< 0 (ЪеВ).
1.3. Элементы теории вычислительной сложности алгоритмов

Следующий важный класс задач распознавания свойств, по-видимому, более широкий, чем Р — это класс ЫР. Исторически, для его определения используется недетерминированная одноленточная машина Тьюринга. Структура недетерминированной машины Тьюринга аналогична структуре детерминированной машины с той лишь разницей, что недетерминированная машина дополнена угадывающим модулем со своей пишущей головкой.
Работа недетерминированной машины, в отличие от детерминированной, имеет две стадии. На первой стадии происходит "угадывание": угадывающая головка записывает на ленте слово-догадку (в ячейках с номерами —1, —2,...), после чего останавливается, угадывающий модуль переходит в пассивное состояние, а управляющее устройство переходит в состояние до- Далее начинается вторая стадия — стадия проверки, которая в точности повторяет работу детерминированной машины. При этом на стадии проверки слово-догадка просматривается читающей/пишущей головкой управляющего устройства. Вычисления заканчиваются, когда управляющее устройство переходит в заключительное состояние: ду или Чы-
Поскольку недетерминированная машина Тьюринга М может иметь бесконечное число возможных вычислений для данного входа (по одному для каждого входа-догадки), то говорят, что машина М принимает входное слово в0, если по крайней мере одно из ее вычислений на входе в0 является принимающим, то есть заканчивается в состоянии ду. Как и ранее, язык, распознаваемый М, состоит из всех слов 5 6 Б*, принимаемых недетерминированной машиной М.
Вычислительная сложность Тм(гг) — это максимальное число тактов, производимых машиной М до останова в состоянии ду на входах длины п. Если же не существует ни одного входа длины п, принимаемого машиной М, то полагаем Тм(п) — 1. Тогда можно определить класс NР как множество всех языков Ь, для которых существует недетерминированная машина Тыоринга М с полиномиальным временем работы такая, что Ь — Ьм• При этом задача распознавания П принадлежит классу ИР, если существует схема кодирования е, при которой Т(П, е) € NP.
Заметим, что можно дать и более современное определение класса ИР, не использующее понятие недетерминированной машины Тыоринга, а опирающееся на определение 1.3.4 класса Р.