• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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, КР – оценка за контрольную работу и ЭК – оценка за устный экзамен. Блокирующих элементов контроля в курсе нет. Автоматы не выставляются.
Список литературы

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

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

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

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

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