Условия существования, алгоритмы построения и оценки комитетов для несовместных систем ограничений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Определения и предварительные результаты

1 Основные понятия и определения

2 Теоремы существования.

3 Уточнение оценок числа членов минимального комитета для систем линейных неравенств

2 Некоторые достаточные условия существования комитета

1 Системы включений, порожденных множествами над /?п

2 Системы включений, порожденных множествами в плоскости

3 Комитет системы включений, образованных выпуклыми многогранными множествами над В?.

3 Задача о минимальном комитете

1 Постановка задачи.

2 Общие свойства.

3 Случай квадратной матрицы.

4 Алгоритм поиска минимального комитета.

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

Возникновению понятия комитета предшествовали эксперименты с ассоциативными машинами типа перцептрона [5, 12]. Понятие комитета ("committee solution") было введено C.M.Ablow и D.J.Kaylor [1, 3] для системы однородных строгих линейных неравенств над Rn. Комитетом системы cij, х) > 0, j Е Nm, где aj:x Е Rn ими было названо конечное множество К С Rn, такое что в полупространстве решений каждого неравенства лежит более половины элементов К.

Пусть задана произвольная система включений xeDj С X, j Е Nm. Комитетом этой системы называется конечная последовательность

Q - (xi,x2,. .lit) элементов X, такая что в каждом множестве Dj находится более половины членов Q. Другими словами, для каждого j Е Nm выполнено неравенство к i Е Nk : Xi Е Dj}| > -.

Минимальным комитетом указанной системы называют последовательность <5 с наименьшим возможным числом членов.

Исследование комитетов и комитетных конструкций в ИММ УрО РАН было инициировано С.Б.Стечкиным в начале 60-х годов. С тех пор систематические исследования в этом направлении проводятся под руководством Вл.Д.Мазурова, в работах которого [35]—[40],[42]—[53]

-доказано необходимое и достаточное условие существование комитета строгих однородных линейных неравенств, дана оценка числа членов минимального комитета;

-доказаны теоремы существования комитета для более общих классов систем неравенств (неоднородных линейных, нелинейных, над произвольным вещественным линейным пространством, неравенств сопряженного вида);

-введены определения и доказаны соответствующие теоремы существования для других комитетных конструкций: разделяющего комитета функционалов, комитета системы множеств, решения, р—комитета, коллективного решения;

-разработаны и обоснованы методы и вычислительные схемы для построенных комитетных конструкций, в том числе минимальных комитетов;

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

Комитетным конструкциям посвящены исследования ряда других Екатеринбургских математиков. В работах А.И.Кривоногова [31]-[34] получены некоторые условия конечности алгоритма построения комитета типа линейной коррекции, обоснована эффективная схема построения комитета системы линейных неравенств с дообучением, исследованы методы проектирования в задаче построения комитета. В работах В.А.Новокшенова, Д.Н.Гайнанова, Л.И.Тягунова [64, 15, 16, 17, 78] исследованы структура максимальных совместных подсистем несовместных систем линейных неравенств и свойства порождаемых ими графов. В работах Н.Г.Белецкого [14] изучены разделяющие свойства комитетов. В исследованиях М.Ю.Хачая [79, 80, 81], на основе введенного им понятия гиперграфа максимальных совместных подсистем, предложена комбинаторная схема классификации минимальных комитетов, сформулирован и доказан критерий существования комитета с заданным наперед числом членов, получены новые оценки числа членов минимального комитета для систем линейных неравенств. Им также показано, что задача построения минимального комитета в общем случае ./VP-трудна [83]. Теоретические и алгоритмические разработки в области комитетных конструкций были реализованы в пакетах распознавания образов "КВАЗАР" [55] и "КВАЗАР—" [68]. успешно применяемых для задач классификации, диагностики, прогнозирования в медицине и моделировании технико-экономических систем.

Ю.И.Журавлевым предложен подход к исследованию методов распознавания образов с точки зрения алгебраической теории алгоритмов, в рамках которого им проанализированы стандартные классы алгоритмов распознавания и, в частности, классы комитетных алгоритмов [23]—[26]. Исследованию свойств комитетов, комитетных алгоритмов классификации и таксономии посвящены работы [27, 28, 29, 66, 67, 75, 76].

Комитетные конструкции представляют собой удобный инструмент при анализе противоречивых моделей. Возникновение противоречий в моделировании сложных систем вполне закономерно и обусловлено целым рядом объективных причин [21]. Одним из способов разрешения противоречий является включение в модель блока распознавания образов — дискриминант-ного анализа или таксономии [19, 20, 21], [43]—[46], [48, 50, 53, 58], [59, 60, 61]. Пусть заданы множества А, В С Rn, известны их конечные подмножества А' С А, В' С В и определен класс функций F С {Rn —> R}. Назовем [58] задачей дискриминантного анализа задачу нахождения такой функции / G F, что f(a) > 0, а£А', о, be в'.

Если такая функция найдена, то полагаем

А — {х е Rn \ f{x) >0}, В = {х е Rn I f(x) < 0}.

Предположим, что класс F некоторым образом параметризован, так что F — {/(с, •) | с £ С}. Тогда поставленная задача преобразуется в задачу решения системы неравенств с,а) > 0, аеЛ1,

М)< о, ье в1 относительно неизвестного параметра с Е С. В ряде случаев эта система может оказаться несовместной. Тогда, в зависимости от ситуации, можно использовать то или иное подходящее обобщение понятия решения, например, дискретную аппроксимацию в форме комитета. Пусть определена конечная последовательность

Я = (Л, /2, • • • , Л) = (Дсъ ■), /(С2, ■),.-., /(с*, •)) элементов ^ и для произвольного а; 6 Яп

У>{х) = {геЫк : /г(х)>0}СЛГь = : /¿(®) < 0} С Я*.

Если для всех а Е А',6 € В' выполнены неравенства

У>(а)|>*/2, \У~{Щ > к/2, то (5 называется разделяющим комитетом множеств А' и В'. В этом случае полагаем

А = {х£Кп : \У>(х)\>к/2}, В = {х£11п : > */2} .

То. что (5 является разделяющим комитетом множеств А! и В' эквивалентно тому, что последовательность К = (сх, С2,. , является комитетом системы (1): для всякого а* € А1 и большинства членов К выполнено неравенство /(сг,а*) > 0, а для любого Ь* € В' и большинства членов К следует

М*)< о.

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

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

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

В диссертации используется методика теории комитетов, дискретной оптимизации, выпуклого анализа, теории линейных неравенств и линейного программирования.

Представленная диссертация состоит из трех глав. Глава 1 является вводной. В ней даются необходимые определения и понятия теории комитетов. Далее в ней приводятся и обосновываются новые оценки числа членов минимального комитета для несовместных систем линейных неравенств, связанные со свойством совместности или разрешимости комитетом всевозможных подсистем данной системы определенного ранга. Таким образом, в частности, дан ответ на вопрос, поставленный в 1981 году Вл.Д.Мазуровым [57]: что можно сказать о числе членов минимального комитета системы линейных неравенств, если нет противоречий к-го рода, но есть противоречия к + 1-го рода?

В главе 2 получены достаточные условия существования комитетного решения для несовместной системы включений, порожденных произвольными множествами над Яп. Показано, что для существования комитета такой системы достаточно существования комитета для некоторой системы включений, образованной конусами, в частности, многогранными, если исходная система была образована выпуклыми многогранными множествами. Также в главе 2 указываются достаточные условия существования комитета большинства для несовместных систем включений, образованных многогранными, не обязательно выпуклыми, конусами и многогранными выпуклыми множествами над Я2. Показано, что для рассматриваемых классов включений может быть построен комитет, не превосходящий по числу членов числа включений в системе. Доказывается, что в случае когда система включений образована выпуклыми многогранными множествами и, в частности, выпуклыми многогранными конусами над Я2, задача построения комитета сводится к комитет-ному решению системы линейных однородных неравенств.

В главе 3 рассмотрена задача целочисленного линейного программирования, возникающая в связи с проблемой поиска комитета с наименьшим возможным числом членов — минимального комитета — для произвольной несовместной системы включений. В предположении, что множество решений тех максимальных совместных подсистем, на основе которых строится минимальный комитет, известно (при этом ни одно из них нельзя исключить), указываются нижние и верхние оценки числа членов минимального комитета (оптимума соответствующей задачи целочисленного линейного программирования). Для более узкого случая, когда число решений максимальных совместных подсистем, необходимых для построения минимального комитета, совпадает с числом включений, исследованы некоторые, возникающие в связи с этим, свойства матриц ограничений. Получены двусторонние оценки числа членов минимального комитета, являющиеся одновременно точными сверху и снизу. Приведены условия, при наличии которых за полиномиальное время указывается минимальный комитет и строится параметрическое представление множества комитетов. Предложен алгоритм поиска приближенного решения задачи о минимальном комитете.

Результаты диссертации являются новыми. Они докладывались на 29/31— й Школе-конференции молодых ученых (Екатеринбург, 1998,2000), Международных конференциях "Математические методы распознавания образов" (Москва, 1999), "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" (Екатеринбург, 2000), "Распознавание образов и анализ изображений" (Самара, 2000), на семинарах Отдела математического программирования ИММ УрО РАН. Основные результаты опубликованы в [69, 70, 71, 72, 73, 74, 82, 83].

Автор выражает глубокую признательность своему научному руководителю Вл.Д.Мазурову, а также И.И.Ерёмину за всестороннюю помощь в подготовке диссертации. Автор благодарен М.Ю.Хачаю за критическое обсуждение результатов и полезные замечания.

Заключение

Сформулируем основные результаты, полученные в работе:

1. на основе введенного понятия рецессивного конуса множества С С Яп в точке х £ С получены достаточные условия существования комитета для несовместной системы включений, образованных произвольными множествами над Я71. Показано, что для существования комитета такой системы достаточно существования комитета для некоторой системы включений, образованной конусами, в частности, многогранными, если исходная система была образована выпуклыми многогранными'множествами;

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

3. исследована задача целочисленного линейного программирования, возникающая в связи с проблемой поиска минимального комитета произвольной системы включений. Из ее анализа, в предположении, что рассматривается такая несовместная, разрешимая комитетом система включений, что любой ее комитет строится из решений всех без исключения максимальных совместных подсистем а) указываются нижние и верхние оценки числа членов минимального комитета (оптимума соответствующей задачи целочисленного линейного программирования); b) при дополнительном условии, что число максимальных совместных подсистем совпадает с числом включений в системе получены двусторонние оценки числа членов минимального комитета, являющиеся одновременно точными сверху и снизу. Показано, что за полиномиальное время может быть найдено приближенное решение задачи о минимальном комитете с гарантированной погрешностью; c) исследованы, связанные с доминируемостью, свойства матриц ограничений. Из них, в частности, следует, что если матрица ограничений задачи целочисленного ЛП для поиска минимального комитета некоторой системы включений доминируется соответствующей матрицей для системы строгих линейных однородных неравенств в плоскости, то минимальный комитет этой системы находится за время порядка 0(п3), где п — число включений в системе; с!) приведены условия, при наличии которых за полиномиальное время (порядка 0(п3)) указывается минимальный комитет и строится параметрическое представление множества комитетов.

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

1. Aho A. V., Hopcroft J.E., Ullman J.D. The Design and Analysis of Computer Algorithms. Addason-Wesley Publishing Company.-1976.

2. Ablow C.M, Kaylor D.J A committee solution of the pattern recognition problem// IEEE Trans.-1965.-v.IT-ll.-№3.-pp.453-455.,

3. Blaha S. The convergence of one groop a< correction training procedures. / / Kybernetica.-1969 .-v. 5 .-№2.

4. Gamba A., Gambertini L., Palmieri G., Sanna R. Further experiments with PAPA.// Nuovo Cimento Suppl.-1961.-v.20.-№2.-pp.ll2-115.

5. Goldman A. J., Tucker A. W. Polyhedral convex cones, in: Linear Inequalities and Related Systems. (H.W.Kuhn and A.W.Tucker, eds.), Princeton Univ. Press, Princeton, N.J.-1956.

6. Goldman A.J. Resolution and separation theorems for plyhedral convex sets, in: Linear Inequalities and Related Systems. (H.W.Kuhn and A.W.Tucker, eds.), Princeton Univ. Press, Princeton, N.J.-1956.

7. Hoffman A.J., Kuhn H.W. On systems of distinct representatives, in: Linear Inequalities and Related Systems. (H.W.Kuhn and A.W.Tucker, eds.), Princeton Univ. Press, Princeton, N.J.-1956.

8. Novikoff A.B.J. On convergence proofs for perceptrons.- Proc. of Symposium of Mathematical Theory of Automata. N.Y.: "Polytechnika".-1962.

9. Osborne M.L The Seniority Logic: A Logic for a Committee Machine.// IEEE Trans. Comp.-1977.-v.C-26.-M2.-pp.l302-1306.

10. Ridgway W.C An adaptive logic system with generalizing properties.// Stanford Electronic Laboratories Technical Report. 1556-1. Stanford Univ.-1962. IEEE Trans.

11. Rosenblatt F. Principles of Neurodinamics.-Wash.: "D.e.:Spattan".-1962.

12. Widrow B. Generalization and information storage in networks of Adaline neurons.// Self — organizing systems. Washington, Spartan Books. -1962. IEEE Trans. Comp.-1977.-v.C-26.-№12.-pp.l302-1306.

13. Белецкий Н.Г. Комитетные конструкции в многоклассовых задачах распознавания образов. Дис. на соискание степени к.ф.-м.н.(01.01.09 -мат.кибернетика).-Свердловск.-1984.

14. Гайнанов Д.Н. Алгоритм выделения всех максимальных совместных подсистем несовместной системы линейных неравенств, в кн.: Тлгунов Л.И., Карапетян Э.Г., Мирзоев Р. Г. Управление качеством промышленных изделий. Ленинград: Изд-во ЛГУ.-1977.-сс. 110-115.

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

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

17. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников).//-М.:Наука.-1981.-344с.

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

19. Еремин И.И., Мазуров Вл.Д. Вопросы оптимизации и распознавание образов.-Свердловск: Средне-Уральское кн. изд-во.-1979.-64с.

20. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования.//-М.:Наука.-1983.-336с.

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

22. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации.// Докл. АН СССР.-1976.-т.231.-№3.-сс.532-535.

23. Журавлев Ю.И. Непараметрические задачи распознавания образов.// -Кибернетика (Киев).-1976.-№6.-сс.93-103.

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

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

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

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

28. Зуев Ю.А. Наихудший случай для принятия решения большинством голосов//' ЖВМ и МФ.-1989.-т.29.-№8.-сс. 1256-1257.

29. М.М.Ковалев. Дискретная оптимизация (целочисленное программирование). Мн., Изд-во БГУ.-1977.-192с.

30. Кривоногое А.И. Некоторые модификации комитетных алгоритмов в распознавании образов// Методы математического программирования и приложения. -Свердловск: УНЦ АН СССР.-1979.-сс.49-55.

31. Кривоногое А.И. О некоторых комитетных конструкциях классификации// Методы оптимизации и распознавания образов в задачах планирования. -Свердловск: УНЦ АН СССР. -1980.-сс.92-98.

32. Кривоногое А. И. Некоторые вопросы обоснования комитетных алгоритмов// Классификация и оптимизация в задачах управления. -Свердловск: УНЦ АН СССР.-1981.-сс.39-51.3435 36 [37 [38 [3940 4142

33. Кривоногое А.И., Мазуров Вл.Д. Метод комитетов для задач оптимизации и диагностики технико-экономических систем. -Свердловск: УНЦ АН CCCP.-1985.-40c.

34. Мазуров Вл.Д. О комитете системы выпуклых неравенств.-Труды 1СМ-66. -Москва: МГУ.-1966.-Ж14.-С.41.

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

36. Мазуров Вл.Д. О комитете системы выпуклых неравенств // Сибир. ма-тем. ж.-№2.-1968.-сс.466-470.

37. Мазуров Вл.Д. Об одном методе обучения узнаванию// Кибернетика.-1970.-№2.-сс.92-94.

38. Мазуров Вл.Д. Распознавание образов как средство автоматического выбора процедуры в вычислительных методах// ЖВМ и МФ.-1970.-т.10.-№6.-сс.1520-1525.

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

40. Мазуров Вл.Д., Тягунов Л.И. Метод комитетов для распознавания нескольких образов и двойственность несовместных систем неравенств.// Математические методы в некоторых задачах оптимального планирования. -Свердловск: УНЦ АН СССР.-1971.-сс.55-59.

41. Мазуров Вл.Д. О системах неравенств сопряженного вида в задачах распознавания./ / Методы выпуклого программирования и приложения. -Свердловск: УНЦ АН СССР.-1973.-№4.-сс.42-47.

42. Мазуров Вл.Д. Дискриминантный анализ при математическом моделировании плохо формализуемых ситуаций.// Нелинейная оптимизация и приложения в планировании. -Свердловск: УНЦ АН СССР.-1973.-№5.-сс.26-36.

43. Мазуров Вл.Д. Об одном итерационном методе планирования, использующем распознавание образов для учета плохо формализуемых факторов.// Изв. АН СССР. Техн. кибеонетика.-1973.-№3.-сс.205-207.

44. Мазуров Вл.Д. Распознавание образов как метод формирования плохо формализуемых ограничений в моделях планирования.// Оптимизация. Труды Ин-та матем. СО АН СССР. вып.10(27). Новосибирск.-1973.-сс.144-158.

45. Мазуров Вл.Д. Организация итерационных процедур при наличии плохо формализуемых ограничений// Нестационарные процессы математического программирования. -Свердловск: УНЦ АН СССР.-1974.-№14.-сс.23-36.

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

47. Мазуров Вл.Д. Применение методов теории распознавания образов в оптимальном планировании и управлении// Метод комитетов в распознавании образов. -Свердловск: УНЦ АН CCCP.-1974.-cc.58-80.

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

49. Мазуров Вл.Д. О некоторых алгоритмах математического программирования, включающих эвристические процедуры.// Прикладн. матем. и программ. (Кишинев).-1975.-№13.-сс.79-83.

50. Мазуров Вл.Д. Теория линейных неравенств и распознавание образов.// Методы фейеровского типа в выпуклом программировании.-Свердловск: УНЦ АН CCCP.-1975.-M8.-cc.9-39.

51. Мазуров Вл.Д. Проект пакета распознавания образов на основе линейных неравенств.// Труды международной конференции "Структура и организация пакетов программ".-Тбилиси.-"Мецниереба".-1976.-сс.80-86.

52. Мазуров Вл.Д. Нестационарные методы математического программирования, использующие экспертизы.// Численные методы нелинейного программирования. -Киев.-"Наукова думка".-1976.-сс. 101-104.

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

54. Мазуров Вл.Д., Казанцев B.C., Белецкий Н.Г. Пакет КВАЗАР прикладных программ распознавания образов, информационные материалы по математическому обеспечению. -Свердловск: УНЦ АН СССР.-1979.

55. Мазуров Вл.Д. Комитеты в нечетких задачах.// Методы оптимизации и распознавания образов в задачах планирования. -Свердловск: УНЦ АН CCCP.-1980.-cc.44-77.

56. Мазуров Вл.Д. О некоторых дискретных аппроксимациях для несобственных задач// Классификация и оптимизация в задачах управления. -Свердловск: УНЦ АН СССР.-1981.-сс.15-29.

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

58. Mazurov VID. Duality in Pattern Recognition and Operation Research.//Pattern Recognition and Image Research.-1991.-v.l.-№4.-pp.376-384.

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

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

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

62. Нильсон Н. Обучающиеся машины.-Москва: Мир.-1968.

63. Новокшенов В. А. Комбинаторные совойства системы линейных неравенств.//Дипломы. работа. Свердловск.-1974 (УрГУ).

64. Рокафеллар Р. Выпуклый анализ. М:Мир.-1973.

65. Рудаков К.В. О числе гиперплоскостей, разделяющих конечные множества в эвклидовом пространстве.// Докл. АН СССР.-1976.-т.231.-№6.-сс.1296-1299.

66. Рудаков К.В., Трофимов C.B. Алгоритм синтеза корректных процедур распознавания для задач с непересекающимися классами.// ЖВМ и МФ.-1988.-т.28.-№9.-сс.1431-1434.

67. Рыбин А.И., Тютин А.Н., Хачай М.Ю. Интегрированная среда анализа и решения задач распознавания образов КВАЗАР+.// Тез. Х1-й Всеросс. Конф. "Матем. прогр. и прилож.", -Екатеринбург: УрО РАН.-1999.-сс.238-240.

68. Рыбин А.И. О некоторых достаточных условиях существования комитета большинства.// Докл. 9-й Всеросс. Конф. "Математические методы распознавания образов", -Москва. ВЦ PAH.-1999.-cc.98-99.

69. Рыбин А.И. О комитетах систем нелинейных включений.// Тез. докл. молодежи, конф. №31, -Екатеринбург: УрО РАН.-2000.-сс.119-120.

70. Рыбин А.И. Об одном подходе к решению задачи о минимальном комитете.//Сборы. док. к Межд. конф. "Распред. системы: оптимизация и приложения в экономике и науках об окружающей среде" (DSO'2000). -Екатеринбург: УрО PAH.-2000.-cc. 166-169.

71. Rybin A.I. On Some Sufficient Conditions of Existence of a Majority Committee.// Pattern Recognition and Image Analysis.-2000.-v. 10.-№3.-pp.297-302.

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

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

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

75. Тютин А.Н. О числе членов комитетов систем включений.// Докл. 8-й Всеросс. Конф. "Математические методы распознавания образов", -Москва. ВЦ РАН.-1997.-сс. 109-110.

76. Хачай М.Ю. О построении комитета системы линейных неравенств методом проектирования на плоскость. -Москва.-1996.-21с. Деп. в ВИНИТИ, ДО-3161-В96.

77. Khachai М. Yu. Classification of committee solutions of majority.// Pattern Recognition and Image Analysis.-1997.-v.7.-№2.-pp.222-230.

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

79. Хачай М.Ю. Рыбин А.И. О числе членов минимального комитета.//Тез. докл. молодежи, конф.-№29.-Екатеринбург: УрО PAH.-1998.-cc.54-55.

80. Khachai M.Yu. Rybin A.I. A New Estimate of the Number Of Members in a Minimum Committee of a Linear Inequalities.//Pattern Recognition and Image Analysis.-1998.-v.8.-№4.-pp.491-496.

81. Черников C.H. Метод свертывания систем линейных неравенств// Успехи мат. наук.-1964.-т.19.-№5.

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