Вы здесь
Лекция профессора Маркова И.Л. (Мичиганский ун-т, США)
![Версия для печати Версия для печати](https://cs.msu.ru/sites/all/modules/print/icons/print_icon.png)
![Send by email Send by email](https://cs.msu.ru/sites/all/modules/print/print_mail/icons/mail_icon.png)
12 октября 2012 г. в 16:20 в ауд. 612 на объединенном заседании спецсеминаров «Теория управляющих систем и математические модели СБИС», «Дискретные функции и сложность алгоритмов», «Дискретный анализ», «Сложность решения дискретных задач» кафедры математической кибернетики состоится доклад профессора Маркова И. Л. (Мичиганский университет, США)
«Алгоритмы для нахождения автоморфизмов больших разреженных графов»
Аннотация доклада:
Эффективный поиск автоморфизмов графов позволяет исследовать симметрию в сложных дискретных системах, начиная от химических молекул до микропроцессоров. Предложенный подход к анализу структуры сложной системы используется при визуализации, верификации, а также ускоряет операции оптимизации структуры сложных систем. Известные алгоритмы поиска автоморфизмов в графе используют методы уточнения разбиений, а также отсечение с использованием теории групп. Несмотря на отсутствие полиномиального алгоритма решения данной задачи для наихудшего случая, для многих практических приложений и специальных тестов задача может быть решена очень быстро. Результаты применения данного метода для сложных примеров подтверждают его эффективность для решения прикладных задач