Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика», 2010
23 июля 2010 г. 15:30, г. Дубна
 


Алгебраическая сложность. Лекция 1

А. А. Разборов
Видеозаписи:
Windows Media 509.0 Mb
Flash Video 852.1 Mb
MP4 852.1 Mb

Количество просмотров:
Эта страница:1231
Видеофайлы:601

А. А. Разборов


Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке

Аннотация: Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов?
Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.
В настоящих лекциях мы, в частности, попытаемся рассказать о некоторых (или всех, если хватит времени) направлениях из следующего списка.
1. Nonscalar complexity (вариант сложности, в котором учитываются только умножения) и полиномы высокой степени.
2. Билинейная сложность и матричное умножение.
3. Определитель, перманент и теория алгебраической NP-полноты.
Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021