Аннотация:
В докладе изучаются общие свойства несовместных систем условий. Рассматриваются системы независимости, связанные с общими системами несовместных условий, определяются графы систем независимости. Методами теории графов изучаются комбинаторные свойства систем независимости, порождаемых различными классами несовместных систем условий. Для ряда таких классов систем условий доказывается связность соответствующих графов систем независимости, являющаяся важнейшим их свойством с алгоритмической точки зрения. Подробно изучаются свойства графов независимости для класса несовместных систем линейных неравенств. Доказывается теорема о существовании цикла нечетной длины в таких графах, которая положена в основу эффективных алгоритмов поиска комитетов минимальной мощности для метода комитетов распознавания образов.
Вводится понятие G-диагонали выпуклого многогранника. Доказывается теорема о двойственности диагоналей выпуклого многогранника и максимальных совместных подсистем несовместных систем линейных неравенств. Полученная двойственность позволяет исследовать комбинаторные свойства несовместных систем линейных неравенств методами комбинаторной геометрии. Подробно изучаются свойства положительных базисов.
Комбинаторная задача выделения всех баз систем независимости общего вида рассматривается в формулировке расшифровки монотонной булевой функции, верхние нули которой соответствуют базам системы независимости. Вводится естественный критерий оптимальности алгоритма расшифровки монотонных булевых функций. Для класса монотонных булевых функций, порождаемых несовместными системами линейных неравенств предлагается эффективный алгоритм ее расшифровки. Для класса монотонных булевых функций, порождаемых неориентированными графами предлагается эвристический алгоритм поиска максимального верхнего нуля с абсолютной оценкой отклонения полученного решения от точного решения.
Приводятся примеры практического применения полученных результатов при решении прикладных задач распознавания образов в геометрической постановке, оптимизации технологических маршрутов в металлургическом производстве и управления транспортными процессами.
|
