DiffGeom Logo
 
О кафедре
История кафедры
Фотоальбом
Сотрудники
Наши студенты
Наши аспиранты
Научная работа
Научные достижения
Лаборатория компьютерных методов
Digital Vision Laboratory
Где работают наши выпускники
Международные и внутри-российские связи кафедры
Публикации
Наши книги
Наши статьи
Диссертации
Работы студентов
Студентам
Спецкурсы
Спецсеминары
Учебные материалы
Задачи для исследования
Олимпиада кафедры
Наглядная и компью­терная геометрия и топология
Геометрические сюжеты
Энциклопедические статьи
Задать вопрос


 

СПЕЦСЕМИНАРЫ  КАФЕДРЫ
(2017–2018 уч. год)

 

РуководительНазваниеДеньВремя Ауд. 
В.О.Мантуров
Д.П.Ильютко
Узлы и теория представленийВТ18-3014-02

Дополнительная информация
 
КРАТКАЯ АННОТАЦИЯ

25 ноября 2008
В.В.Кочергин
«О сложности вычислений»

Рассматриваются следующие три задачи:

1) задача о сложности вычисления системы одночленов от нескольких переменных;

2) задача о сложности вычисления системы целочисленных линейных форм;

3) задача о сложности вычисления системы элементов свободной абелевой группы.

Эти задачи являются обобщениями задачи о наскорейшем возведении в степень, известной также как задача об аддитивных цепочках. Эти обобщения могут быть описаны на языке вычисления системы из p векторов размерности q векторными аддитивными цепочками следующим образом. Цепочка q-мерных векторов, начинающаяся с q единичных (базисных) векторов и обладающая тем свойством, что любой отличный от базисного вектор цепочки является поокоординатной суммой каких-либо двух предшествующих векторов, вычисляет систему векторов (или соответствующую ей матрицу размера pxq), если все векторы этой системы содержатся в цепочке. Сложность системы векторов (сложность матрицы) определяется как минимальная длина цепочки (число небазисных векторов), вычисляющей эту систему. Для второй задачи наряду с операцией сложения также разрешается использовать и операцию вычитания, а третья помимо базисных векторов допускает использование противоположных к ним векторов. В докладе предполагается дать обзор известных результатов в этой области, а также представить ряд результатов автора.


Вернуться к расписанию спецсеминаров