Символьные вычисления 21/22 — различия между версиями
(+ лекция 2) |
(+ программа экзамена) |
||
(не показано 16 промежуточных версии этого же участника) | |||
Строка 17: | Строка 17: | ||
[https://drive.google.com/file/d/1Bcb19seQWW-iCG2_yKby6gJES7rBf-6a/view?usp=sharing Лекция 2] (19.01.2022): Алгоритм деления. Оператор редукции. Нормальная форма многочлена. Базис Грёбнера идеала. Критерий Бухбергера и алгоритм Бухбергера. Минимальный базис Грёбнера и его единственность. | [https://drive.google.com/file/d/1Bcb19seQWW-iCG2_yKby6gJES7rBf-6a/view?usp=sharing Лекция 2] (19.01.2022): Алгоритм деления. Оператор редукции. Нормальная форма многочлена. Базис Грёбнера идеала. Критерий Бухбергера и алгоритм Бухбергера. Минимальный базис Грёбнера и его единственность. | ||
+ | |||
+ | [https://drive.google.com/file/d/1KqOK10Q8ZYfdUNPQDg4wLRfF93EHUI6P/view?usp=sharing Лекция 3] (26.01.2022): Универсальный базис Грёбнера и его существование. Алгебраическое подмножество. Алгебра регулярных функций. Аффинное алгебраическое многообразие. | ||
+ | |||
+ | [https://drive.google.com/file/d/1nuyKkM0ZDI9naKjQsZ-JcJAZCP-MdqAG/view?usp=sharing Лекция 4] (02.02.2022): Радикал идеала. Радикальный идеал. Теорема Гильберта о нулях. Максимальный идеал. Слабая версия теоремы Гильберта о нулях. Cooтветствие между максимальными идеалами и точками многообразия. Морфизмы и изоморфизмы многообразий. Аффинные алгебры. Спектр алгебры. | ||
+ | |||
+ | [https://drive.google.com/file/d/1H2SjZ-vGMzXkhjyXS5pEolaEdPUu2O0l/view?usp=sharing Лекция 5] (09.02.2022): Топологическое пространство. База топологии. Топология Зарисского. Главные открытые подмножества. Непрерывность морфизмов. Плотные подмножества и неприводимые пространства. Нетеровы топологические пространства. Неприводимые компоненты. Открытые, замкнутые и доминантные морфизмы. Замкнутые вложения. | ||
+ | |||
+ | [https://drive.google.com/file/d/1mbNvMwn_cgBCDjIlSvguX9uX1mPxDoPE/view?usp=sharing Лекция 6] (16.02.2022): Двенадцать задач на применение базисов Грёбнера в теории систем полиномиальной уравнений, аффинной алгебраической геометрии и коммутативной алгебре. | ||
+ | |||
+ | [https://drive.google.com/file/d/1liWOAuKxk-aOB125keJ8tJS85c9EgThC/view?usp=sharing Лекция 7] (02.03.2022): Характеристика поля. Конечные поля. Простое подполе и порядок конечного поля. Автоморфизм Фробениуса. Теорема существования и единственности для конечных полей. Поле из четырех элементов. Цикличность мультипликативной группы. Неприводимые многочлены над конечным полем. Подполя конечного поля. | ||
+ | |||
+ | [https://drive.google.com/file/d/1iRBCdZSkSsTLXX9VnCkJ0Hf-8Y29_iqt/view?usp=sharing Лекция 8] (09.03.2022): Неприводимые многочлены над конечными полями. Теорема о степени башни расширений. Функция Мёбиуса и ее свойства. Аддитивная формула Мёбиуса и явная формула для числа неприводмых многочленов данной степени над конечным полем. Примеры. Существование не менее одного неприводимого многочлена данной степени. Мультипликативная формула Мёбиуса и произведение неприводимых многочленов данной степени. | ||
+ | |||
+ | [https://drive.google.com/file/d/1kb4LhPIpJGi2IRXUJGjh3fAziUXAuln3/view?usp=sharing Лекция 9] (16.03.2022): Задача о разложении многочлена на неприводимые множители. Избавление от кратных множителей. f-разлагающие многочлены. Сведение к системе линейных уравнений: алгоритм Берлекэмпа. Алгоритм Кронекера разложения многочлена с целыми коэффициентами. Лемма Гаусса. | ||
+ | |||
+ | [https://drive.google.com/file/d/1-yxsCSfZ05f-cwvJBBzIGhl7gkyZFoSb/view?usp=sharing Лекция 10] Основная задача теории кодирования. Расстояние Хэмминга. Коды, исправляющие ошибки. Характеристики кода. Неравенство Синглтона. Совершенные коды. Линейные коды. Вес Хэмминга. Код Хэмминга [7, 4, 3]_2. Коды Рида-Соломона. Циклические коды и главные идеалы. Коды Голея и БЧХ-коды. Алгоритм декодирования по лидеру смежного класса. | ||
== Семинары == | == Семинары == | ||
Строка 26: | Строка 42: | ||
Семинар 2 (22.01.2022): Мономиальные порядки. Алгоритм деления на набор многочленов от нескольких переменных. Идеал старших членов, доказательство теоремы Гильберта о базисе через лемму Гордана. Базис Грёбнера, критерий Бухбергера, алгоритм Бухбергера, минимальный базис Грёбнера. | Семинар 2 (22.01.2022): Мономиальные порядки. Алгоритм деления на набор многочленов от нескольких переменных. Идеал старших членов, доказательство теоремы Гильберта о базисе через лемму Гордана. Базис Грёбнера, критерий Бухбергера, алгоритм Бухбергера, минимальный базис Грёбнера. | ||
+ | |||
+ | Семинар 3 (29.01.2022): Пример поиска базиса Грёбнера и минимального базиса Грёбнера, разные упрощения. Алгебраические подмножества, примеры. Пересечение и объединение двух алгебраических подмножеств. Алгебры регулярных функций параболы и окружности. Радикал идеала, пример нерадикального идеала. Слабая теорема Гильберта о нулях как следствие теоремы Гильберта о нулях. | ||
+ | |||
+ | Семинар 4 (05.02.2022): Включения алгебраических подмножеств, идеалов и их радикалов. Максимальные идеалы. Отображение функций на множествах и алгебраических многообразиях. | ||
+ | |||
+ | Семинар 5 (12.02.2022): Изоморфизм алгебраических многообразий, примеры с параболой и полукубической параболой. Нормальное многообразие. Неприводимые компоненты. Доминантные и сюръективные морфизмы. | ||
+ | |||
+ | Семинар 6 (19.02.2022): Морфизмы из прямой в гиперболу. Задачи на применение базисов Грёбнера: принадлежность многочлена идеалу, решение системы полиномиальных уравнений, замыкание образа при морфизме, исключительные идеалы. | ||
+ | |||
+ | Семинар 7 (26.02.2022): Применение базисов Грёбнера к автоматическому доказательству геометрических теорем. Диагонали параллелограмма, окружность Аполлония. Строгое и обобщённое следования из системы полиномиальных условий, неприводимые компоненты многообразия, алгебраическая независимость, достаточное условие для обобщённого следования. | ||
+ | |||
+ | Семинар 8 (05.03.2022): Конечные поля. Уравнения над конечными полями, автоморфизм Фробениуса. Задачи про цикличность мультипликативной группы конечного поля, нецикличность мультипликативной группы бесконечного поля. | ||
+ | |||
+ | Семинар 9 (12.03.2022): Пример неприводимого многочлена степени p над Z_p. Конструкция поля как фактор-кольца кольца многочленов по главному идеалу, вычисление в фактор-кольце. Расширения полей, задачи. | ||
+ | |||
+ | Семинар 10 (19.03.2022): Функции Мёбиуса и Эйлера, формула Мёбиуса. Алгоритм Берлекэмпа (примеры). Неприводимость над Z и Q, признак Эйзенштейна. | ||
== Контрольные мероприятия == | == Контрольные мероприятия == | ||
+ | |||
=== Домашние задания === | === Домашние задания === | ||
+ | Домашнее задание 1 доступно по [https://drive.google.com/file/d/1AwDB_Nfpto4T1UtKLEknRLvP_ZdUz0GU/view?usp=sharing ссылке], срок сдачи 26 февраля 23:59. | ||
+ | Домашнее задание 2 доступно по [https://drive.google.com/file/d/16rgbuiY5r84Uy1BXRj8LlcApqliCY4u6/view?usp=sharing ссылке], срок сдачи 26 марта 23:59. | ||
=== Контрольная работа === | === Контрольная работа === | ||
− | + | Контрольная работа состоится 26 марта в 14:40. [https://drive.google.com/file/d/1aI8pPmmuJVR9wBqBzsGnK3Oz2gyFjZJr/view?usp=sharing Регламент контрольной]. | |
− | + | ||
=== Экзамен === | === Экзамен === | ||
− | Экзамен проводится в устной форме. | + | Экзамен проводится в устной форме. [https://drive.google.com/file/d/1GM2OemHBBggmn3AvXBselAo7P6WlQRTt/view?usp=sharing Вопросы к экзамену]. |
=== Правила выставления оценок === | === Правила выставления оценок === | ||
Строка 72: | Строка 106: | ||
[5] Н.Коблиц. Курс теории чисел и криптографии. М.; ТВП, 2001 | [5] Н.Коблиц. Курс теории чисел и криптографии. М.; ТВП, 2001 | ||
− | [6] А.Ромащенко, А. | + | [6] А.Ромащенко, А.Румянцев и А.Шень. Заметки по теории кодирования (2-е издание). М.: МЦНМО, 2017 |
− | [7] Сборник задач по алгебре под редакцией А.И. Кострикина. Новое | + | [7] Сборник задач по алгебре под редакцией А.И. Кострикина. Новое издание. М.: МЦНМО, 2009 |
− | издание. М.: МЦНМО, 2009 | + | |
[8] T.Becker, H.Kredel, V.Weispfenning. Groebner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics, Springer, 1993 | [8] T.Becker, H.Kredel, V.Weispfenning. Groebner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics, Springer, 1993 | ||
− | [9] D.Cox, J.Little, D.O'Shea. Using Algebraic Geometry. 2nd Edition. | + | [9] D.Cox, J.Little, D.O'Shea. Using Algebraic Geometry. 2nd Edition. Graduate Texts in Mathematics, vol. 185, Springer, 2005 |
− | Graduate Texts in Mathematics, vol. 185, Springer, 2005 | + | |
[10] B.Sturmfels. Groebner Bases and Convex Polytopes. University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996 | [10] B.Sturmfels. Groebner Bases and Convex Polytopes. University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996 |
Текущая версия на 00:50, 25 марта 2022
Содержание
О курсе
Курс читается для студентов 4-го курса в 3 модуле.
Лектор — Аржанцев Иван Владимирович
Семинарист — Зайцева Юлия Ивановна
Ассистент — Попкович Александр
Лекции
Проходят по средам в 11:10.
Лекция 1 (12.01.2022): Кольца и идеалы. Конечно порожденные идеалы и нётеровы кольца. Факторкольца. Конечно порожденные модули и подмодули. Теорема Гильберта о базисе. Мономиальный порядок на множестве мономов. Лемма Гордана. Старший член многочлена от многих переменных. Лемма о старшем члене.
Лекция 2 (19.01.2022): Алгоритм деления. Оператор редукции. Нормальная форма многочлена. Базис Грёбнера идеала. Критерий Бухбергера и алгоритм Бухбергера. Минимальный базис Грёбнера и его единственность.
Лекция 3 (26.01.2022): Универсальный базис Грёбнера и его существование. Алгебраическое подмножество. Алгебра регулярных функций. Аффинное алгебраическое многообразие.
Лекция 4 (02.02.2022): Радикал идеала. Радикальный идеал. Теорема Гильберта о нулях. Максимальный идеал. Слабая версия теоремы Гильберта о нулях. Cooтветствие между максимальными идеалами и точками многообразия. Морфизмы и изоморфизмы многообразий. Аффинные алгебры. Спектр алгебры.
Лекция 5 (09.02.2022): Топологическое пространство. База топологии. Топология Зарисского. Главные открытые подмножества. Непрерывность морфизмов. Плотные подмножества и неприводимые пространства. Нетеровы топологические пространства. Неприводимые компоненты. Открытые, замкнутые и доминантные морфизмы. Замкнутые вложения.
Лекция 6 (16.02.2022): Двенадцать задач на применение базисов Грёбнера в теории систем полиномиальной уравнений, аффинной алгебраической геометрии и коммутативной алгебре.
Лекция 7 (02.03.2022): Характеристика поля. Конечные поля. Простое подполе и порядок конечного поля. Автоморфизм Фробениуса. Теорема существования и единственности для конечных полей. Поле из четырех элементов. Цикличность мультипликативной группы. Неприводимые многочлены над конечным полем. Подполя конечного поля.
Лекция 8 (09.03.2022): Неприводимые многочлены над конечными полями. Теорема о степени башни расширений. Функция Мёбиуса и ее свойства. Аддитивная формула Мёбиуса и явная формула для числа неприводмых многочленов данной степени над конечным полем. Примеры. Существование не менее одного неприводимого многочлена данной степени. Мультипликативная формула Мёбиуса и произведение неприводимых многочленов данной степени.
Лекция 9 (16.03.2022): Задача о разложении многочлена на неприводимые множители. Избавление от кратных множителей. f-разлагающие многочлены. Сведение к системе линейных уравнений: алгоритм Берлекэмпа. Алгоритм Кронекера разложения многочлена с целыми коэффициентами. Лемма Гаусса.
Лекция 10 Основная задача теории кодирования. Расстояние Хэмминга. Коды, исправляющие ошибки. Характеристики кода. Неравенство Синглтона. Совершенные коды. Линейные коды. Вес Хэмминга. Код Хэмминга [7, 4, 3]_2. Коды Рида-Соломона. Циклические коды и главные идеалы. Коды Голея и БЧХ-коды. Алгоритм декодирования по лидеру смежного класса.
Семинары
Проходят по субботам в 14:40.
Чат в телеграм: https://t.me/+Mxs1mQbQnSdmMzZi
Семинар 1 (15.01.2022): Идеалы в кольцах. Многочлены от одной переменной: деление с остатком, кольцо главных идеалов, наибольший общий делитель. Контрпримеры в случае нескольких переменных. Альтернативное доказательство леммы Гордана.
Семинар 2 (22.01.2022): Мономиальные порядки. Алгоритм деления на набор многочленов от нескольких переменных. Идеал старших членов, доказательство теоремы Гильберта о базисе через лемму Гордана. Базис Грёбнера, критерий Бухбергера, алгоритм Бухбергера, минимальный базис Грёбнера.
Семинар 3 (29.01.2022): Пример поиска базиса Грёбнера и минимального базиса Грёбнера, разные упрощения. Алгебраические подмножества, примеры. Пересечение и объединение двух алгебраических подмножеств. Алгебры регулярных функций параболы и окружности. Радикал идеала, пример нерадикального идеала. Слабая теорема Гильберта о нулях как следствие теоремы Гильберта о нулях.
Семинар 4 (05.02.2022): Включения алгебраических подмножеств, идеалов и их радикалов. Максимальные идеалы. Отображение функций на множествах и алгебраических многообразиях.
Семинар 5 (12.02.2022): Изоморфизм алгебраических многообразий, примеры с параболой и полукубической параболой. Нормальное многообразие. Неприводимые компоненты. Доминантные и сюръективные морфизмы.
Семинар 6 (19.02.2022): Морфизмы из прямой в гиперболу. Задачи на применение базисов Грёбнера: принадлежность многочлена идеалу, решение системы полиномиальных уравнений, замыкание образа при морфизме, исключительные идеалы.
Семинар 7 (26.02.2022): Применение базисов Грёбнера к автоматическому доказательству геометрических теорем. Диагонали параллелограмма, окружность Аполлония. Строгое и обобщённое следования из системы полиномиальных условий, неприводимые компоненты многообразия, алгебраическая независимость, достаточное условие для обобщённого следования.
Семинар 8 (05.03.2022): Конечные поля. Уравнения над конечными полями, автоморфизм Фробениуса. Задачи про цикличность мультипликативной группы конечного поля, нецикличность мультипликативной группы бесконечного поля.
Семинар 9 (12.03.2022): Пример неприводимого многочлена степени p над Z_p. Конструкция поля как фактор-кольца кольца многочленов по главному идеалу, вычисление в фактор-кольце. Расширения полей, задачи.
Семинар 10 (19.03.2022): Функции Мёбиуса и Эйлера, формула Мёбиуса. Алгоритм Берлекэмпа (примеры). Неприводимость над Z и Q, признак Эйзенштейна.
Контрольные мероприятия
Домашние задания
Домашнее задание 1 доступно по ссылке, срок сдачи 26 февраля 23:59.
Домашнее задание 2 доступно по ссылке, срок сдачи 26 марта 23:59.
Контрольная работа
Контрольная работа состоится 26 марта в 14:40. Регламент контрольной.
Экзамен
Экзамен проводится в устной форме. Вопросы к экзамену.
Правила выставления оценок
Итоговая оценка вычисляется по формуле
- Округление(0.15*ДЗ1 + 0.15*ДЗ2 + 0.3*КР + 0.4*ЭК),
где ДЗ1 – оценка за домашнее задание № 1, ДЗ2 – оценка за домашнее задание № 2, КР – оценка за контрольную работу и ЭК – оценка за устный экзамен.
Округление арифметическое.
Блокирующих элементов контроля в курсе нет. Автоматы не выставляются. Оценка на комиссии выставляется по результатам ответа без учета других элементов контроля.
Список литературы
Рекомендуемая основная литература:
[1] Дж.Дэвенпорт, И.Сирэ и Э.Турнье. Компьютерная алгебра. Системы и алгоритмы алгебраических вычислений. М.: Мир, 1991
[2] Д.Кокс, Дж.Литтл, Д.О’Ши. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. М.: Мир, 2000
[3] V.Ene and J.Herzog. Groebner Bases in Commutative Algebra. Graduate Studies in Mathematics 130, American Mathematical Society, Providence, RI, 2011
Рекомендуемая дополнительная литература:
[1] А.Акритас. Основы компьютерной алгебры с приложениями. М.: Мир, 1994
[2] Введение в криптографию. Под редакцией В.В.Ященко. М.: МЦНМО, 2012
[3] Э.Б. Винберг. Курс алгебры (4-е издание). М.: МЦНМО, 2019
[4] С.Г.Влэдуц, Д.Ю.Ногин и М.А.Цфасман. Алгеброгеометрические коды. М.: МЦНМО, 2003
[5] Н.Коблиц. Курс теории чисел и криптографии. М.; ТВП, 2001
[6] А.Ромащенко, А.Румянцев и А.Шень. Заметки по теории кодирования (2-е издание). М.: МЦНМО, 2017
[7] Сборник задач по алгебре под редакцией А.И. Кострикина. Новое издание. М.: МЦНМО, 2009
[8] T.Becker, H.Kredel, V.Weispfenning. Groebner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics, Springer, 1993
[9] D.Cox, J.Little, D.O'Shea. Using Algebraic Geometry. 2nd Edition. Graduate Texts in Mathematics, vol. 185, Springer, 2005
[10] B.Sturmfels. Groebner Bases and Convex Polytopes. University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996