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

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

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

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Аржанцев Иван Владимирович, Зайцева Юлия Ивановна

Язык: русский

Кредиты: 4

Контактные часы: 44

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Многие объекты и процессы окружающего мира как минимум приближенно описываются системами полиномиальных уравнений, и информация о множествах решений таких систем крайне полезна. К плохим новостям относится теорема Абеля-Руффини, утверждающая, что для общего многочлена степени пять и выше его корни не могут быть выражены в радикалах через коэффициенты. Но есть и хорошие новости. В 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, КР – оценка за контрольную работу и ЭК – оценка за устный экзамен. Блокирующих элементов контроля в курсе нет. Автоматы не выставляются.

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