Бакалавриат
2022/2023
Символьные вычисления
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
4
Контактные часы:
44
Программа дисциплины
Аннотация
Многие объекты и процессы окружающего мира как минимум приближенно описываются системами полиномиальных уравнений, и информация о множествах решений таких систем крайне полезна. К плохим новостям относится теорема Абеля-Руффини, утверждающая, что для общего многочлена степени пять и выше его корни не могут быть выражены в радикалах через коэффициенты. Но есть и хорошие новости. В 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-балльной шкале на основании общего впечатления преподавателя от ответа студента.
