Символьные вычисления

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

4-й курс, 3 модуль

Преподаватели

Аржанцев Иван Владимирович

Зайцева Юлия Ивановна

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• Промежуточная аттестация (3 модуль)
  Итоговая оценка = Округление (0.15*ДЗ1+0.15*ДЗ2+0.3*КР+0.4*ЭК), где ДЗ1 – оценка за домашнее задание № 1, ДЗ2 – оценка за домашнее задание № 2, КР – оценка за контрольную работу и ЭК – оценка за устный экзамен. Блокирующих элементов контроля в курсе нет. Автоматы не выставляются.

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

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

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

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

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