Symbolic Computation

2021/2022

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

4 year, 3 module

Instructors

Arzhantsev, Ivan

Zaitseva, Yulia

Программа дисциплины

Аннотация

Многие объекты и процессы окружающего мира как минимум приближенно описываются системами полиномиальных уравнений, и информация о множествах решений таких систем крайне полезна. К плохим новостям относится теорема Абеля-Руффини, утверждающая, что для общего многочлена степени пять и выше его корни не могут быть выражены в радикалах через коэффициенты. Но есть и хорошие новости. В XX веке найдены алгоритмы, которые по системе полиномов любой степени и от любого числа переменных определяют, есть ли у системы комплексное решение и конечно ли число таких решений. Эти алгоритмы основаны на понятии базиса Гребнера идеала в алгебре многочленов и известной теореме Гильберта о нулях (Nullstellensatz). В курсе мы приведем элементарное доказательство этой теоремы, изучим основные свойства базисов Гребнера, разберем алгоритм Бухбергера построения таких базисов и рассмотрим многочисленные приложения базисов Гребнера. Вторая часть курса будет посвящена конечным полям и многочленам над ними. Мы рассмотрим алгоритмы разложения многочленов на множители, а также приложения этой науки в теории кодирования.

Цель освоения дисциплины

• Изучить основные постановки задач теории символьных вычислений и компьютерной алгебры, освоить необходимые для этого понятия из алгебры.
• Изучить основы аффинной алгебраической геометрии и научиться решать возникающие здесь алгоритмические задачи с помощью теории базисов Грёбнера.
• Знать теорему Гильберта о базисе и теорему Гильберта о нулях.
• Освоить алгоритм Берлекэмпа разложения многочлена на множители над конечными полями.
• Изучить приложения теории конечных полей и многочленов над ними в теории кодирования.

Планируемые результаты обучения

• Изучить приложения базисов Гребнера в теории систем полиномиальных уравнений, коммутативной алгебре и алгебраической геометрии, уметь решать соответствующие алгоритмические задачи.
• Изучить строение конечных полей и многочленов над ними.
• Научиться применять алгоритм Бухбергера и его модификации для построения базиса Гребнера идеала в кольце многочленов.

Содержание учебной дисциплины

• Общие сведения о символьных вычислениях и компьютерной алгебре. Многочлены от многих переменных. Мономиальные порядки и старший член многочлена. Теорема Гильберта о базисе.
• Базис Гребнера идеала в кольце многочленов. Критерий и алгоритм Бухбергера. Минимальный редуцированный базис Гребнера и теорема единственности. Универсальный базис Гребнера.
• Приложения базисов Гребнера к системам полиномиальных уравнений. Теорема Гильберта о нулях.
• Аффинные алгебраические многообразия. Приложения базисов Гребнера к задачам алгебры и алгебраической геометрии.
• Необходимые сведения из криптографии.
• Необходимые сведения из теории кодирования.
• Строение конечных полей. Подполя конечного поля.
• Функция Мебиуса и число неприводимых многочленов данной степени над конечным полем.
• Алгоритм Берлекэмпа разложения многочлена на множители над конечным полем.

Элементы контроля

• Домашнее задание 1
  Выдается в конце февраля и содержит 5 задач, посвященных вычислению базисов Гребнера, их приложениям в типовых алгоритмических задачах и аффинным алгебраическим многообразиям. Решение каждой из задач может быть оценено от 0 до 2 баллов (т.е. максимум 10 баллов).
• Домашнее задание 2
  Выдается после лекции № 10 и содержит 5 задач, посвященных вычислению в конечных полях и с многочленами над конечными полями, а также иллюстрации основных криптосистем и методов теории кодирования. Решение каждой из задач может быть оценено от 0 до 2 баллов (т.е. максимум 10 баллов).
• Контрольная работа
  Проводится после лекции №11 и содержит 7 задач. Задачи 1-3 и 4-6 относятся к тем же темам, что и задачи домашних заданий № 1 и № 2, соответственно, а задача 7 посвящена материалу лекции № 11. Решение каждой из задач может быть оценено от 0 до 2 баллов (т.е. максимум 14 баллов).
• Экзамен
  Экзамен проводится в устной форме, возможно проведение в аудитории или на платформе Zoom. Студент получает билет, который включает в себя два вопроса из программы экзамена – один вопрос из первой половины программы и один вопрос из второй половины программы. Во время подготовки можно использовать любые печатные материалы, но запрещается использовать электронные средства коммуникации. После ответа студенту могут быть заданы дополнительные вопросы по программе курса, а также предложены задачи на понимание теоретического материала. Такие задачи не требуют проведения обширных вычислений. Оценка за экзамен выставляется по 10-балльной шкале на основании общего впечатления преподавателя от ответа студента.

Промежуточная аттестация

• 2021/2022 учебный год 3 модуль
  0.3 * Контрольная работа + 0.15 * Домашнее задание 2 + 0.4 * Экзамен + 0.15 * Домашнее задание 1

Список литературы

Рекомендуемая основная литература

• Компьютерная алгебра : системы и алгоритмы алгебраических вычислений, Дэвенпорт, Дж., 1991

Рекомендуемая дополнительная литература

• Алгеброгеометрические коды : основные понятия, Влэдуц, С. Г., 2003
• Курс алгебры, Винберг, Э. Б., 2019