Вы здесь

Семинар «Информатика, управление и системный анализ»

Версия для печатиSend by email

ОБЩЕРОССИЙСКИЙ СЕМИНАР «ИНФОРМАТИКА, УПРАВЛЕНИЕ И СИСТЕМНЫЙ АНАЛИЗ»
под общим руководством
Академика РАН Юрия Ивановича Журавлева,
Академика РАН Евгения Ивановича Моисеева,
Академика РАН Станислава Николаевича Васильева,
Академика РАН Юрия Соломоновича Попкова
организатор и ученый секретарь семинара
профессор Михаил Васильевич Ульянов

Сайт семинара: www.commonmind.ru

ЗАСЕДАНИЕ №34 Вторник 17 октября 2017 г., 17-30, ауд. 685 ВМК МГУ

ПОВЕСТКА ДНЯ
1.Научный доклад:
«МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НЕСОВМЕСТНЫХ СИСТЕМ УСЛОВИЙ МЕТОДАМИ ТЕОРИИ ГРАФОВ И КОМБИНАТОРНОЙ ГЕОМЕТРИИ»
Докладчик: Гайнанов Дамир Насибуллович
Московский авиационный институт (национальный исследовательский университет)

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


Предложения по содержанию и функционированию сайта направляйте по адресу cmcproject@cs.msu.ru.