В ЛЭТИ расскажут о вычислениях без вычитаний и тропической математике

В ЛЭТИ расскажут о вычислениях без вычитаний и тропической математике

Приглашаем студентов и преподавателей СПбГЭТУ «ЛЭТИ» на лекции главного научного сотрудника Французского национального центра научных исследований Дмитрия Юрьевича Григорьева на темы «Сложность вычислений без вычитаний (или калькулятор с частично сломанными кнопками)» и «Введение в тропическую математику».

12.12.2018 246

12 и 13 декабря в нашем университете пройдут лекции главного научного сотрудника Французского национального центра научных исследований Дмитрия Юрьевича Григорьева.

Сложность вычислений без вычитаний (калькулятор с частично сломанными кнопками)

12 декабря в 15:35, ауд. 3238

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

Второй из наших результатов устанавливает экспоненциальный разрыв между сложностью вычислений, использующих с одной стороны сложение, умножение и деление, и с другой стороны, использующих все четыре арифметических операции.

13 декабря в 17:20, ауд. 5419, тема: «Введение в тропическую математику»

В тропической математике привычные сложение и умножение заменяются, соответственно, на минимум и сложение. Это приводит к необычным уравнениям.

Будет рассказано об истоках и приложениях тропической математики, результатах и алгоритмах в тропической линейной алгебре, а также о тропической теореме о нулях.