 | Григорьев Д.Ю. (CNRS, France) "Тропическая комбинаторная теорема о нулях и тестирование малочленов" |
|
В понедельник 9 октября в 18.00 в ПОМИ (ауд.106) состоится доклад Григорьева Д.Ю. (CNRS, France) "Тропическая комбинаторная теорема о нулях и тестирование малочленов" https://logic.pdmi.ras.ru/seminars/dm-seminar/2017-10-09 Абстракт: 1. Алгоритмы и сложность в тропической алгебре 2. Тропическая алгебра - область на стыке алгебраической геометрии и комбинаторики, бурно развивающаяся в последние два десятилетия. Ключевым моментом в тропической алгебре является замена обычной арифметики со сложением и умножением на тропическое полукольцо с минимумом и сложением. Поэтому тропические многочлены - кусочно-линейные выпуклые функции. В лекциях предполагается рассказать об алгоритмах в тропической алгебре, их сложности и открытых проблемах. 3. а) Сложность решения систем тропических линейных уравнений; б) Тропическая эффективная теорема о нулях: оценки; в) Тропическая комбинаторная теорема о нулях; г) Вероятностные тестовые множества для тропических многочленов: тропический аналог леммы Зиппеля-Шварца; д) Универсальные тестовые множества для тропических разреженных многочленов. 4. Первые работы по тропической алгебре восходят к Ньютону, в которых им был предложен метод (называемый сейчас многоугольник Ньютона), позволяющий вычислять асимптотику алгебраических кривых, являющихся решениями полиномиальных уравнений. Это находит сейчас приложения, например, в поиске асимптотики решений динамических систем, возникающих в биохимии и химической кинетике. Задача составления расписаний сводится к решению систем тропических линейных уравнений: в некоторых странах железнодорожное расписание составляется как раз с помощью решения тропических линейных систем. Недавно было предложено приложение к экономике: определение стартовой цены на аукционе описывается тропической кривой. Некоторые задачи теории графов, например, нахождение путей минимальных весов, сводятся к вычислениям в тропическом полукольце. Совсем недавние работы по задачам глубокого обучения с помощью нейронных сетей также приводят к вопросам тропической алгебры. Поэтому изучение алгоритмов в тропической алгебре весьма полезно для работы в теоретической информатике, а также в многочисленных приложениях к решению систем полиномиальных и дифференциальных уравнений, составлению расписаний, выпуклой оптимизации, экономике, теории графов и нейронных сетей. Предполагается, что изложение будет в доступной для студентов форме, дополнительных знаний не требуется. |