Пятница, 9 апреля, ауд. 106. Начало в 18:00.
Докладчик: Александр Тискин (University of Warwick).
Тема: Тропические матрицы Монжа: Алгебраическая структура и алгоритмы.
Abstract
Матрицы Монжа являются фундаментальным объектом в теории оптимизации, а
также в вычислениях на графах и строках. В этой связи большой интерес
представляет тропическое умножение матриц Монжа, соответствующее поиску
кратчайших путей в ориентированном планарном графе. Мы рассматриваем
подкласс матриц Монжа, получаемый суммированием подматриц в матрицах
перестановок. С точки зрения тропического умножения, данный подкласс
образует моноид, описываемый при помощи простой модификации классической
группы кос. Оказывается, что умножение в этом моноиде можно осуществлять
исключительно быстро, что имеет массу алгоритмических приложений: быстрое
разрешение упорядоченности Брюа на перестановках; быстрое вычисление
максимальной клики в круговом графе; быстрый приближенный поиск подстроки
в сжатом файле. Будут приведены основные теоретические результаты, а
также обзор некоторых из вычислительных приложений.
