Вопросы комитетной полиэдральной отделимости конечных множеств тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Поберий, Мария Ивановна

• Поберий, Мария Ивановна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Поберий, Мария Ивановна

Введение

1 Комитетные решения несовместных систем ограничений

1.1 Понятие комитетного решения и условия его существования

1.2 Разделяющие комитетные конструкции.

1.3 Элементы теории вычислительной сложности алгоритмов.

1.3.1 Классы Р и NP.

1.3.2 Понятие iVP-полноты.

1.3.3 Класс А^Р-трудных задач.

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(í) к задаче MIN-PC.

2.4.2 MAX-SNP-TpyflfiocTb задачи MASC-GP(n).

3 Задача обучения распознаванию образов в классе аффинных коми-тетных решающих правил

3.1 Основы сложностной теории обучения распознаванию образов.

3.2 Емкость класса аффинных комитетных решающих правил с ограниченным числом элементов.

Введение диссертации (часть автореферата) на тему «Вопросы комитетной полиэдральной отделимости конечных множеств»

При построении математических моделей в экономике, технике, биологии, медицине и других трудноформализуемых областях знания зачастую приходится иметь дело с плохо формализованными или противоречивыми ограничениями. Особенность плохо формализуемых задач состоит в недоопределенности их условий и отсутствии формализованного понятия решения, поэтому возникает необходимость уточнения условий и рассмотрения нескольких вариантов решений для таких задач. При этом построенная модель может оказаться противоречивой.

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

Второй подход к коррекции несовместных систем ограничений — дискретный, при котором привычное, сосредоточенное в одном элементе решение заменяется коллективом "квазирешений", каждое из которых удовлетворяет достаточно большой доле условий исследуемой задачи, являясь, но сути, решением некоторой непротиворечивой подсистемы исходной системы ограничений. Одной из математических формализации дискретного подхода является теория комитетных решений.

Понятие комитета впервые появилось в работах по распознаванию образов: в совместной статье Эйблоу и Кейлора [77] было введено понятие комитетного решения для системы строгих однородных линейных неравенств ц,х)>о С?еМт). (1)

Конечная последовательность (х\,. ,хд) С Мп называется комитетом системы (2), если всякому неравенству удовлетворяет более половины ее элементов. В работе тех же авторов [78] сформулировано без доказательства достаточное условие существования комитета системы (2) и приведено его геометрическое обоснование.

В более общем виде различные виды обобщения понятия решения на случай несовместных систем были введены в екатеринбургской школе распознавания. Современная теория комитетных конструкций опирается на результаты, полученные Вл.Д. Мазуровым [29]-[32]. Им было доказано необходимое и достаточное условие существования комитета несовместной системы линейных неравенств, получены первые оценки числа членов минимального комитета; введены обобщения понятия комитета (р-комитет, (г,р)-комитет, г-решение и т.д.) и получены условия существования этих конструкций для систем линейных неравенств и некоторых более общих систем включений; предложены и обоснованы вычислительные схемы для построения р-комитетов, в том числе минимальных.

Каждой комитетной конструкции соответствует понятие разделяющей комитетной конструкции и алгоритм распознавания. Согласно [30], разделяющим комитетом (большинства) для конечных множеств А, В из Мп называется последовательность функций

Э=(/ь/2,.,/в), принадлежащих заданному параметрическому семейству = {/(-;с) : с € С} С {М™ —> Ж}, таких, что соответствующая данным функциям последовательность значений параметров с1,с2, • • • ,Сд) является комитетным решением системы неравенств а; с) > 0 (а <Е А) ДЬ;с)< 0 (ЬеВ).

Тогда в каждой точке множества А более половины функций последовательности $ принимает положительное значение, а в каждой точке множества В, напротив, отрицательное, то есть г е N. : Ма) > 0}| > | (о € А), г<ЕМ9: /4(Ь)<0}| > | (ЬеВ).

При этом комитетный алгоритм распознавания (решающее правило) подразумевает принятие решения об отнесении объекта к одному из двух классов на основе значения не одной функции из класса Р, а последовательности функций (3 С Р. Для произвольного объекта в 6 <5 с результатом измерений х(з) £ Мп вычисляется q значений € ^ = {0,1} ио правилу | если > 0

1 0, если /г(ж) < О, после чего объект относится к первому классу, если большинство чисел принимает значение 1, и ко второму классу — в противном случае, то есть решение принимается по правилу простого большинства. Заметим, что каждая из функций рассматриваемая в отдельности, порождает алгоритм распознавания, который, в свою очередь, может оказаться некорректным, в то время как построенный из этих функций комитетный алгоритм распознавания безошибочно классифицирует множество объектов с результатами измерений из множества А и В, то есть является корректным на этом множестве.

Кроме комитетных алгоритмов распознавания, основанных на логике болыпинаства, в ряде работ рассматривались алгоритмы, основанные на других логиках: старшинства, единогласия и т.д. [33, 107]. Однако сведение задачи построения разделяющих комитетов с такими логиками к задаче построения комитета системы неравенств (включений) не столь очевидно, как в случае логики большинства. Исследованием вопроса о разделяющих возможностях комитетов с различными логиками при решении задач дискриминантного анализа и при реализации геометрических предикатов занимался Н.Г. Белецкий (см., например, [1]).

Известный алгебраический подход к решению задач распознавания образов опирается на фундаментальные результаты Ю.И. Журавлева. В середине 70-х годов ХХ-го века был опубликован цикл его работ, в которых важное место занимает проблема построения корректных алгоритмов распознавания над множествами некорректных [22, 23]. Им также были введены методы расширения класса алгоритмов при помощи алгебраических операций, позволяющие строить полное семейство алгоритмов, то ссть такое, в котором есть корректный алгоритм. Развитие алгебраического подхода к синтезу корректных алгоритмов распознавания было продолжено в работах К.В. Рудакова [47, 48], В.В. Рязанова [50, 51], Е.В. Дюковой [13, 14], К.В. Воронцова [4]-[6] и др.

Ю.А. Зуев предложил метод повышения надежности классификации путем объединения нескольких различных алгоритмов распознавания в комитет. В работах [24, 25] описан байесовский подход к построению корректора, принимающего решение о выборе класса, при котором работа алгоритма описывается вероятностным законом, и на основе обучающей информации оцениваются вероятности принадлежности объекта к одному из нескольких классов. /

Для теории комитетов и, в частности, для задачи построения минимального комитета большую роль играет метод фундаментального свертывания, развитый и обоснованный С.Н. Черниковым [75, 76]. Этот метод позволяет находить максимальные по включению совместные подсистемы (МСП) для исходной несовместной системы линейных неравенств. В работе Вл.Д. Мазурова [31] показано, что из существования ко-митетиой конструкции для несовместной системы линейных неравенств следует существование соответствующего решения, составленного из решений МСП исходной системы. Это позволяет ограничиться исследованием комитетов, составленных из решений МСП, и объясняет значимость метода фундаментального свертывания для теории комитетных решений.

Условия комитетной разрешимости системы несовместных включений удобно формулировать в терминах теории графов. В работе [55] было введено понятие графа МСП для системы строгих однородных линейных неравенств, а в [7, 8] данное понятие было распространено на системы ограничений более общего вида и изучены свойства графа МСП.

Позднее понятие графа МСП было обобщено в работах М.Ю. Хачая [56, 57, 85, 91], а именно, введено понятие гиперграфа МСП, на основе анализа свойств которого удалось получить более тонкие условия существования комитета. В частности, был доказан критерий существования комитетного решения с заданным числом элементов для системы абстрактных включений и проведена классификация минимальных ко-митетных решений на основе изоморфизма соответствующих им подги-перграфов гиперграфа МСП.

С 80-х годов прошлого века у исследователей возник интерес к изучению вычислительной сложности комбинаторных задач, связанных с процедурой обучения распознаванию образов. Приведем общую постановку задачи обучения распознаванию образов, для чего зафиксируем измеримое пространство (X х f2, Л, Р), где X — множество результатов измерений, Г) = {0,1} — множество названий образов (классов), Р — вероятностная мера, и зададимся множеством

Т — {/(•,се) решающих правил, причем

Sa = {{х,ои) : f(x, а) ф uj} G Л {a G Л), то есть является событием.

Задачей обучения распознаванию образов называется оптимизационная задача minP(o;)=mm / (f(x,a)—ca)2dP(x,uj), (2) абЛ а€Л J

ХхП где вероятностная мера Р считается неизвестной и заданной с точностью до конечной выборки a:i,wi), ■ • ■, {xi, toi).

Для аппроксимации неполностью формализованной задачи (2) традиционно рассматривается задача минимизации эмпирического риска:

1 ' пшаМа) = у - Я**' о))2}- (3) 1

Как известно [2], точность аппроксимации (обобщающая способность результирующего решающего правила /* = f(-,a*), где а* = arg min(3), монотонно убывает с ростом емкости УСО{Т') класса решающих правил Т.

Напомним, что емкостью УСО{Т) класса решающих правил Т называется наибольшее Н Е М, для которого существует такой набор х{Ь) — (жь . . . ,Хн), Хг е X, что для произвольного ш(1г) = . . . , Ш}г), и>1 Е О, найдется а (Е А, для которого я?,-, К].

В рамках алгебраического подхода к решению задач распознавания исследуются классы Т, содержащие корректные на выборке

Ж1,0>1),., (Х1,Ш1) решающие правила, то есть такие функции /(•, а) Е Т^ для которых

О;, а) = е М/. ,

Для таких классов оптимальное значение задачи (3) равно нулю, и повы-'" шение качества обучения может быть связано с минимизацией емкости класса, то есть с решением задачи тт{УСО{Т') : шт{г/(а) : / € Т'} = О, Т' С Г}. (4)

Исследуемая в работе задача о минимальном аффинном разделяющем комитете (МАЭС) является частным случаем задачи (4), в котором класс Т является классом комитетных кусочно-линейных решающих правил.

Задача "Минимальный аффинный разделяющий комитет" (МАЭС).

Заданы конечные множества А, В О (0>п, А = {ах,., ат1} и В — {61,., Ьт2}. Требуется указать аффинный комитет с наименьшим числом, элементов, разделяющий множества А и В.

Вычислительная сложность задачи о минимальном по числу элементов комитете впервые была исследована М.Ю. Хачаем. Им доказана труднорешаемость задачи в общем случае и основных ее специальных случаев [60, 73]: задачи о минимальном комитете системы конечных множеств (MCFS), задачи о минимальном комитете системы линейных неравенств (MCLE) и тесно связанной с ней задачи о минимальном аффинном разделяющем комитете (MASC), занимающей центральное место в настоящей работе. Ряд работ посвящен изучению вопроса эффективной аппроксимируемости обозначенных выше задач: получена оценка порога аппроксимируемости для задач MCFS [71] и MASC [95], разработаны и обоснованы полиномиальные приближенные алгоритмы решения задач MCLE [68], MASC [74] и некоторых их частных случаев.

Как было отмечено выше, задача о минимальном аффинном разделяющем комитете (MASC) в общем случае является труднорешаемой. Также известно (см., напр., [104]), что задача MASC, заданная в одномерном пространстве может быть решена за полиномиальное время. До недавнего времени открытым оставался вопрос о вычислительной сложности задачи MASC в пространствах фиксированной размерности, большей единицы. В работе [95] показано, что задача MASC остается iVP-труд-ной, будучи сформулированной в пространстве фиксированной размерности п > 1 — задача MASC(n). Однако при получении всех этих результатов, касающихся труднорешаемости задачи MASC, существенно использовалась вырожденность разделяемых множеств: рассматриваемые при доказательстве частные случаи задачи MASC были построены таким образом, что разделяемые множества находились не в общем положении. В связи с этим естественно возникает вопрос о вычислительной сложности задачи MASC, если исключить из рассмотрения подобные ее частные случаи. Ответ на него содержится во второй главе настоящей работы, в которой доказано, что задача о минимальном аффинном разделяющем комитете, сформулированная в пространстве фиксированной размерности, большей единицы, при условии общности положения разделяемых множеств (MASC-GP(n)) остается труднорешаемой. Условие общности положения разделяемых множеств заключается в том, что каждое подмножество из п+ 1 элемента множества Ли В, определяющего частную постановку задачи MASC, аффинно независимо.

Традиционный для теории вычислительной сложности подход [10, 11, 27, 28, 86, 108, 112] к исследованию NP-трудных задач комбинаторной оптимизации предполагает анализ аппроксимационных свойств задачи, разработку и обоснование приближенных алгоритмов для ее решения. В общем случае задача MASC является трудноаппроксимируемой [95]. В настоящей работе был дан ответ на вопрос об аппроксимируемости задачи MASC в пространстве фиксированной размерности п > 1 при дополнительном условии общности положения разделяемых множеств (MASC-GP(n)). Предложен новый полиномиальный приближенный алгоритм для решения задачи MASC-GP(n), обладающий, при некотором естественном предположении, точностью аппроксимации O(logm). Таким образом, алгоритм позволил сократить разрыв между полученной ранее границей аппроксимируемости для задачи о минимальном аффинном разделяющем комитете для конечных множеств O(logloglogm) [95] и лучшей точностью аппроксимации 0(т) известного полиномиального аппроксимационного алгоритма [74], где т — \А U В\ — мощность множества, определяющего частную задачу MASC.

Следующий круг вопросов, рассмотренный в работе, посвящен классу задач MAX-SNP. Этот класс был впервые определен в совместной работе X. Пападимитриу и М. Яннакакиса [109] и состоит из оптимизационных задач, обладающих приближенными алгоритмами с постоянной точностью. Во второй главе диссертации доказано, что задачи о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-PC) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности п > 1 при условии общности положения разделяемых множеств (MASC-GP(n)) МАХ-.!?./VP-трудны. Это позволило сделать вывод о невозможности построения для задач MIN-PC и MASC-GP(n) аппроксимационной схемы, в предположении P^NP.

Третий круг вопросов', изученный в настоящей работе, посвящен задаче обучения распознаванию образов в классе аффинных комитетных решающих правил с ограниченным числом элементов и оценке емкости VCD данного класса.

Методы исследования. В работе использован математический аппарат теории вычислительной сложности и, в частности, подход, базирующийся на полиномиальной сводимости; математический аппарат теории линейных неравенств, линейного программирования и теории графов; элементы вычислительной геометрии.

На защиту выносятся следующие результаты.

1. Доказано, что задача об аффинном разделяющем комитете на плоскости для множеств в общем положении, сформулированная в виде задачи распознавания свойства, - задача PASC-GP является -/VP-полной в сильном смысле. Обоснована труднорешаемость (в сильном смысле) задачи о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности, большей единицы, при условии общности положения разделяемых множеств (MASC-GP(n))

2. Разработан и обоснован приближенный алгоритм решения задачи MASC-GP(n), обладающий в общем случае точностью 0(т/п), а при справедливости некоторого дополнительного предположения — точностью O(logm).

3. Доказана МЛХ-й'ЛГР-трудность задач о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-РС) и о минимальном аффинном разделяющем комитете в пространстве фиксированной размерности при условии общности положения разделяемых множеств (MASC-GP(n)) и, следовательно, невозможность построения для этих задач полиномиальной аппроксимацион-ной схемы, если Р ф N Р.

4. Получены верхняя и нижняя оценки емкости VCD{Tq) класса Tq аффинных комитетных решающих правил, состоящих из не более чем q функций, обоснована точность нижней оценки.

Публикации. Представленные в диссертации результаты опубликованы в работах [38], [40]-[45], [58], [59], [96], [97], [110].

Апробация работы. Результаты работы докладывались на международных и всероссийских конференциях:

- XIII Всероссийская конференция "Математическое программирование и приложения", 26.02.2007 - 02.03.2007, Екатеринбург.

- 38 Молодежная Школа-конференция "Проблемы теоретической и прикладной математики". 29.01.2007- 02.02.2007, Екатеринбург.

- 20-th EURO Mini-Conference "Continuous Optimization and Knowledge-Based Technologies" (EurOPT-2008), May 20-23, 2008, Neringa, Lithuania.

- 7-ая Международная конференция "Интеллектуализация обработки информации" (ИОИ-2008), 9-14 июня 2008 г., Алушта, Украина.

- 39 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 28.01.2008 - 01.02.2008, Екатеринбург.

- 40 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 26.01.2009 - 30.01.2009, Екатеринбург.

- 41 Всероссийская Молодежная конференция "Проблемы теоретической и прикладной математики". 01.02.2010 - 05.02.2010, Екатеринбург.

- Весенняя конференция молодых ученых ИММ УрО РАН 2010 года, 01.06.2010 - 03.06.2010, Екатеринбург.

- 10-я Международная конференция "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-10-2010). 5.12.2010-12.12.2010, Санкт-Петербург.

- XIV Всероссийская конференция "Математическое программирование и приложения", 28.02.2011 - 04.03.2011, Екатеринбург.

Структура работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Объем работы составляет 130 страниц.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Поберий, Мария Ивановна

Заключение —----

Список литературы диссертационного исследования кандидат физико-математических наук Поберий, Мария Ивановна, 2011 год

1. Белецкий Н.Г. Разделяющие возможности комитетов с различными логиками. - Свердловск: УНЦ АН СССР, 1984. 23 с.

2. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М.: Наука, 1974. 416 с.

3. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.

4. Воронцов К.В. Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. 1995. т. 35, № 10. С. 1565-1575.

5. Воронцов К.В. О проблемно-ориентированной оптимизации базисов задач распознавания // ЖВМ и МФ. 1998. т. 38, № 5. С. 870-880.

6. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. 2000. т. 40, № 1. С. 166-176.

7. Гайнанов Д.Н. О графах максимальных совместных подсистем несовместных систем линейных неравенств. -Москва, 1981. 46 с. Деп.ВИНИТИ, № 229-81.

8. Гайнанов Д.Н., Новокшенов В.А., Тягунов Л.И. О графах, порождаемых несовместными системами линейных неравенств // Мат. заметки. 1983. -Т. 33, вып. 2., С. 293-300.

9. Гейл Д. Соседние вершины на выпуклом многогрпннике. Линейные неравенства и смео!сиые вопросы, сборник статей под редакцией Г. У. Кун а и А.У.Таккера, Москва, 1959 рр. 355 362.

10. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб. "Проблемы кибернетики", вып. 31. М.: Наука, 1975. С. 35-42.

11. Гимади Э.Х. Асимптотически точный алгоритм отыскания одного и двух реберно непересекающихся маршрутов коммивояжера максимального веса в евклидовом пространстве / / Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 23-32.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачу. М.: Мир, 1982. 416 с.

13. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // ЖВМ и МФ. 1987. т. 27, № 1. С. 114-127.

14. Дюкова Е.В., Журавлев Ю.И., Рудаков К.В. Об алгебро-ло-гическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // ЖВМ и МФ. 1996. т. 36, № 8. С. 215223.

15. Евтушенко Ю.Г., Голиков А.И. Новый метод решения систем линейных равенств и неравенств. Доклады Академии Наук, 2001. т. 381, № 4, С. 444-447.

16. Евтушенко Ю.Г., Голиков А.И. Двойственный подход к решению систем линейных равенств и неравенств. Труды XII Байкальской международной конференции. Пленарные доклады, 2001. С. 91-99.

17. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.

18. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. 288 с.

19. Еремин И.И.Противоречивые модели оптимального планирования- Москва: Наука. 1988. 160 с.

20. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. 248 с.

21. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: «У-Фактория», 2000. 280 с.

22. Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов. I-III // Кибернетика. 1977, №4, С. 14-21; 1977, №6, С. 21-27; 1978, №2, С. 35-43.

23. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, вып. 33, 1978. С. 5-68.

24. Зуев Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонностиЦЖВМ и МФ, 1981. т.21. №1. С.157-167.

25. Зуев Ю.А. Вероятностная модель комитета классификаторов// ЖВМ и МФ, 1986. т.26. №2. С.276-292.

26. Качалков A.B., Рыбин А.И., Хачай М.Ю. Технология создания вычислительного сайта «Квазар-Онлайн» // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-6-2002». Новгород: НовГУ, 2002. С. 258-262.

27. Кельманов A.B., Пяткин A.B. О сложности одного из вариантов задачи выбора подмножества похожих векторов // ДАН. 2008. т. 421, №5. С. 590-592.

28. Кельманов A.B. О сложности некоторых задач анализа данных // ЖВМ и МФ. 2010. т. 50, № 11. С. 2045-2051.

29. Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика, 1967. №2. С. 56-59.

30. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 1971. №3. С. 140-146.

31. Мазуров Вл.Д. Несовместные системы неравенств в задачах распознавания // Метод комитетов в распознавании образов. Свердловск: УНЦ АН СССР, 1974. С. 3-9.

32. Мазуров Вл.Д., Тягунов Л.И. Метод комитетов в распознавании образов // Метод комитетов в распознавании образов. -Свердловск: УНЦ АН СССР, 1974. С.10-40.

33. Мазуров Вл.Д. Теория и приложения комитетных конструкций // Методы для нестационарных задач математического программирования. Свердловск: УНЦ АН СССР, 1979. С.31-63.

34. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации- М.: Наука, 1990. 248 с.

35. Мазуров Вл.Д., Хачай М.Ю. Комитетные конструкции // Известия УрГУ, 1999, вып. 14. С. 76-108.

36. Мазуров Вл.Д., Хачай М.Ю. Комитетные конструкции как обобщение решений противоречивых задач исследования операций // Дискретный анализ и исследование операций. 2003. Т. 10, Сер. 2, №2. С. 56-66.

37. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств /¡Автоматика и телемеханика, 2004. вып. 2, С. 43-54.

38. Мазуров Вл.Д., Хачай М.Ю., Поберий М.И. Задачи комбинаторной оптимизации, связанные с полиэдральной комитетной отделимостью конечных множеств / / Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 89102.

39. Пападимитриу К., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.

40. Поберий М.И. Оценки емкости класса аффинных разделяющих комитетов с ограниченным числом элементов / / Труды 38 Молодеоюной Школы-конференции "Проблемы теоретической и прикладной математики". -Екатеринбург: УрО РАН. 2007. С. 111-115.

41. Поберий М.И. О труднорешаемости задачи о минимальном аффинном разделяющем комитете на плоскости / / Труды 39 Всероссийской Молодежной конференции "Проблемы теоретической и прикладной математики". -Екатеринбург: УрО РАН. 2008. С. 337-342.

42. Поберий М.И. О принадлежности классу МАХ-вЫР задач МШ-РС и МА8С-СР(7г) //Труды 41 Всероссийской Молодеэ/сной конференции "Проблемы теоретической и прикладной математики". -Екатеринбург: УрО РАН. 2010. С. 390-395.

43. Поберий М.И. О принадлежности классу МАХ-вИР-трудных задач МШ-РС и МАЗС-СР(п) // Труды Института математики и механики УрО РАН, 2010. т. 16, №3, С. 210-215.

44. Рудаков К.В. О некоторых классах алгоритмов распознавания (общие результаты). М.: ВЦ РАН СССР, 1980. 66 с.

45. Рудаков К.В. О некоторых классах алгоритмов распознавания (параметрические модели). М.: ВЦ РАН СССР, 1981. 48 с.

46. Рыбин А.И. Об оценках минимального комитета. Москва, 2000. 35с. Деп. в ВИНИТИ 28 ноября 2000г., 3029-В00.

47. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации // ЖВМ и МФ. 1981. т. 21, № 6. С. 1533-1543.

48. Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии) // ЖВМ и МФ. 1982. т. 22, № 2. С. 429-440.

49. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // ЖВМ и МФ. 1986. т. 26, № 3, С. 439-448

50. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Труды Института математики и механики УрО РАН, 2008. т. 14, №2, С. 115-128.

51. Скарин В.Д. Об одном общем подходе к оптимальной коррекции несобственных задач выпуклого программирования // Труды Института математики и механики УрО РАН, 2010. т. 16, № 3, С. 265-275.

52. Хачай М.Ю. О существовании комитета большинства // Дискретная математика, 1997. т. 9, вып. 3. С. 82-95.

53. Хачай М.Ю. Об оценке числа членов минимального комитета системы линейных неравенств // ЖВМ и МФ, 1997. т. 37, № 11. С. 1399-1404.

54. Хачай М.Ю., Поберий М.И. Вычислительная сложность задачи о минимальном аффинном разделяющем комитете при фиксированной размерности пространства // в кн. "Методы оптимизации и их приложения", труды XIV Байкальской школы-семинара. 2008. т. 1. С. 542-549.

55. Хачай М.Ю., Рыбин А.И. О комитетном решении с минимальным числом членов системы линейных неравенств // Труды XI меоЫу-народной Байкальской школы-семинара «Методы оптимизации и их приложения». Иркутск: ИСЭ СО РАН, 1998. С. 26-40.

56. Хачай М.Ю. Об оценке емкости класса комитетных решающих функций // Доклады IX Всероссийской конференции «Математические методы распознавания образов». 1999, Москва, ВЦ РАН, С. 121-123.

57. Хачай М.Ю. Об одной комбинаторной задаче, связанной с понятием минимального комитета // Труды Международной конференцииРаспознавание образов и анализ изображений РОАИ-5-2000». — Самара: ИСОИ РАН. 2000. С. 167-169.

58. Хачай М.Ю. О достаточной длине обучающей выборки для коми-тетного решающего правила // Искусственный интеллект. 2000, №2, С. 219-223.

59. Хачай М.Ю. Об одном соотношении, связанном с процедурой принятия решений большинством голосов // ДАН. 2001. т. 381, №6. С. 748-752.

60. Хачай М.Ю. Об одном соотношении, связанном с голосованием большинством // Труды Международной конференции «Математическое моделирование (ММ-2001)». Самара: ИСОИ РАН. 2001. С. 41-44.

61. Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // Доклады X Всероссийской конференции «Математические методы распознавания образов». -Москва: ВЦ РАН. 2001. С. 149-153.

62. Хачай М.Ю. Об одной игре с природой, связанной с принятием решений большинством голосов // ЖВМ и МФ. 2002, т. 42, №10, С. 1609-1616.

63. Хачай М.Ю. Приближенный алгоритм решения задачи о минимальном комитете системы линейных неравенств / в сб. «Алгебра и линейная оптимизация», труды международного семинара, посвященного 90-летию С.Н.Черникова. Екатеринбург: УрО РАН. 2002. С. 314-318.

64. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Доклады XI Всероссийской конференции «Математические методы распознавания образов». Москва: ВЦ РАН. 2003. С. 198-201.

65. Хачай М.Ю. Об апроксимационной сложности задачи о минимальном комитете // Таврический вестник информатики и математики. 2004, №1. С. 78-82.

66. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете // Труды Международной конференции «Распознавание образов и анализ изображений РОАИ-7-2004»- — С.-Петербург: ЛЭТИ. 2004.

67. Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете и смежных задач //ДАН, 2006, 406, №6, С. 742-745.

68. Хачай М. Ю. О вычислительной и аппроксимационной сложности задачи о минимальном аффинном разделяющем комитете // Таврический вестник информатики и математики, 2006, №1, С. 34-43.

69. Черников С.Н. Линейные неравенства. М.: Наука, 1968. 488 с.

70. Черников С.Н. Свертывание конечных систем линейных неравенств // ДАН УССР, 1969, №1, С. 32-35.

71. Ablow С.М., Kaylor D.J. Inconsistent Homogeneous Linear Inequalities // Bull. Amer. Math. Soc., 1965, vol. 71, no. 5, p. 724.

72. Ablow C.M., Kaylor D.J. A Committee solution of the pattern recognition problem // IEEE Trans. Information Theory, 1965, vol. 11, no. 3, pp. 453-455.

73. Arora S., Safra M. Probabilistic Checking of Proofs: A new Characterization of NP // Journal of ACM. 1998. 45(1), pp. 70-122.

74. Blum A.L., Rivest R.L. Training a 3-node Neural Network is NP-complete // Neural Networks. 1992, vol. 5, pp. 117-127.

75. Cook S.A. The complexity of theorem-proving procedures// Proc. 3rd Ann. ACM Symp. on Theory of Computing. ACM. New York. 1971. pp. 151-158.

76. Dinur I., Regev 0. and Smyth C. The hardness of 3-uniform hypergraph coloring. In: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.

77. Fagin R. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets // Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings. 1974. V.7. pp. 27-41.

78. Feige U. A Threshold of In n for Approximating Set Cover. Journal of the ACM. 1998, 45(4).

79. Hachai M.Yu. Classification of Committee Solutions of Majority // Pattern Recognition and Image Analysis. 1997. V.7. N2. pp. 260-265.

80. Hochbaum D. ed. Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, 1996.

81. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of Computer and System Sciences. 1974, vol. 9(3), pp. 256-278.

82. Kachalkov A.V., Rybin A.I., Khachay M.Yu. Development of the Quasar-Online Computational Site // Pattern Recognition and Image Analysis. 2003, vol. 13, no 2. pp. 217-220.

83. Khachai M.Yu., Rybin A.I. A New Estimate of the Number of Members in a Minimum Committee of a System of Linear Inequalities // Pattern Recognition and Image Analysis, 1998. Vol. 8. No. 4. pp. 491-496.

84. Khachai M.Yu. On the Combinatorial Problem Concerned with the Notion of Minimal Committee // Pattern Recognition and Image Analysis. 2001. V.ll no.l. pp. 45-46.

85. Khachay M.Yu. On an Efficient Approximation Algorithm for the Minimal Committee Problem // Pattern recognition and Image Analysis. 2003. Vol.13, no 1. pp. 43-44.

86. Khachay M.Yu. On Approximate Algorithm of a Minimal Committee of a Linear Inequalities System// Pattern Recognition and Image Analysis. 2003, vol. 13, no 3. pp. 459-464.

87. Khachay M.Yu. On Computational Complexity of the Minimal Committee of Finite Sets Problem // In: Proc. of the 2nd International Workshop 'Discrete Optiomization Methods in Production and Logistics'. Omsk-Irkutsk. 2004. pp. 176-179.

88. Khachai M.Yu. Computational and Approximational Complexity of Combinatorial Problems Related to the Committee Polyhedral Separability of Finite Sets // Pattern Recognition and Image Analysis, 2008, vol. 18, no. 2. pp. 237-242.

89. Khachay M., Poberii M. Complexity and approximability of committee polyhedral separability of sets in general position // Informática. 2009. Vol. 20, no 2. pp. 217-234.

90. Kobylkin K.S. Necessary Condition for Committee Existence // Pattern Recognition and Image Analysis. 2002. vol. 12, no. 1. pp. 26-31.

91. Kumar A., Arya S., Ramesh H. Hardness of Set Cover with Intersection 1// Lecture Notes in Computer Science. 2000, vol. 1853. pp. 624-635.

92. Lin J.H., Vitter J.S. Complexity Results on Learning by Neural Nets // Machine Learning. 1991, vol. 6. pp. 211-230.

93. Mazurov VI.D. Duality in Pattern Recognition // Pattern Recognition and Image Analysis. 1991. v. 1, no. 2. pp. 81-87.

94. Mazurov VI.D. Recognition and Choice in a Multistage Procedure of Modeling Complex Systems.// Pattern Recognition and Image Research. 1994. v.4, no. 2. pp. 87-92.

95. Mazurov VI.D. Generalized Existence in Nonequilibrium Models of Choice in Modeling Complex Systems.// Pattern Recognition and Image Research. 1995. v.5, no. 1. pp. 7-12.

96. Mazurov VI.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceedings of the Steklov Institute of mathematics. Suppl. 1, (2002). pp. 67-101.

97. Megiddo N. On the complexity of polyhedral separability // Discrete and Computational Geometry. 1988, no. 3. pp. 325-337.

98. Megiddo N., Tamir A. On the complexity of locating linear facilities in the plane // Operations research letters. 1982, vol. 1, no. 5. pp. 194-197.

99. Osborne M.L. The Senjority Logic: A Logic for a Committee Machine // IEEE Trans, on Comp. 1977. v.C-26, no. 12. pp. 1302-1306.У

100. Papadimitriou Ch. Computational Complexity. Addison-Wesley. 1995, 523p.

101. Papadimitriou C., Yannakakis M. Optimization, approximation, and complexity classes //J. Comput. System Sci. 1991, vol. 43, no. 3. pp. 425-440.

102. Rybin A.I. On Some Sufficient Conditions of Existence of a Majority Committe // Pattern Recognition and Image Analysis. 2000. vol. 10, no. 3. pp. 297-302.

103. Vazirarri V. Approximation algorithms. Berlin: Springer, 2001. 378 p.