Лекция профессора Маркова И.Л. (Мичиганский ун-т, США)

12 октября 2012 г. в 16:20 в ауд. 612 на объединенном заседании спецсеминаров «Теория управляющих систем и математические модели СБИС», «Дискретные функции и сложность алгоритмов», «Дискретный анализ», «Сложность решения дискретных задач» кафедры математической кибернетики состоится доклад профессора Маркова И. Л. (Мичиганский университет, США)

«Алгоритмы для нахождения автоморфизмов больших разреженных графов»

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