|
Лысиков В. В.
Понедельник,
18:00,
ауд. 508
|
Полугодовой курс. Первое занятие 3 октября
В курсе излагаются базовые понятия алгебраической теории сложности и основные результаты
теории билинейных алгоритмов. Рассматриваются методы получения нижних оценок сложности
неветвящихся программ. Формулируются и доказываются некоторые классические и современные
результаты о сложности вычисления билинейных отображений, в частности, матричного
умножения.
- Алгебраические модели вычислений и примеры задач алгебраической теории сложности.
- Метод подстановки. Оптимальность схемы Горнера. Сложность умножения матрицы на вектор.
-
Теорема о делениях. Квадратичные алгоритмы.
- Cвязь между рангом билинейной формы
и мультипликативной сложностью ее вычисления. Основы мультилинейной алгебры. Билинейные
алгоритмы и тензорный ранг.
- Оценки сложности вычисления пар и троек билинейных
форм.
- Умножение многочленов. Мультипликативная сложность умножения многочленов.
Описание множества всех билинейных алгоритмов умножения многочленов.
- Умножение
и деление многочленов с помощью преобразования Фурье. Задача вычисления значения
многочлена во многих точках.
- Сложность умножения матриц. Тензор матричного умножения и его свойства. Тау-теорема.
-
Приближенные билинейные алгоритмы и граничный ранг. Применение приближенных алгоритмов
для оценки сложности матричного умножения.
- Понятие алгебры над полем. Умножение
в алгебре как билинейное отображение. Примеры алгебр. Оценки ранга и мультипликативной
сложности некоторых алгебр.
- Нижняя оценка Блезера для ранга умножения в матричных
алгебрах и алгебрах с делением.
- Сложность умножения многочленов и матриц над
полем из двух элементов.
[1] P. Buergisser, M. Clausen, M. A. Shokrollahi. Algebraic complexity theory.
[2] В. Н. Латышев. Комбинаторная теория колец: сложность алгебраических алгоритмов.
[3] M. Blaser. Lower bounds for the bilinear complexity of associative algebras.
// Computational Complexity vol.9 issue 2, pp. 73-112.
[4] A. Shpilka. Lower bounds for matrix product. // SIAM J. on Computing vol.32
issue 2, pp. 1185-1200.
Страница курса: http://vmk.somee.com/Details/210
|