GrEbner Bases

Краткое содержание учебной дисциплины, модуля / Brief summary

Тема 1. Идеалы и аффинные многообразия.

Полиномы и аффинное пространство. Аффинные многообразия. Идеалы и их связь с аффинными многообразиями. Системы алгебраических уравнений и их связь с идеалами. 

Тема 2. Базисы Гребнера.

Мономиальные порядки. Алгоритм деления многочлена на систему многочленов в кольце многочленов от нескольких переменных. Мономиальные идеалы и лемма Диксона. Теорема Гильберта о базисе и базисы Гребнера. Свойства базисов Гребнера. S-полиномы, критерий Бухбергера -пар. Алгоритм Бухбергера. Минимальный и редуцированный базис Гребнера. Критерий принадлежности идеалу. Критерий равенства идеалов.

Тема 3. Теория исключения.

Исключающие идеалы. Теорема об исключении, ее применение к системам алгебраических уравнений. Теорема о продолжении. 

Тема 4. Теорема Гильберта о нулях.

Слабая и сильная теоремы Гильберта о нулях. Критерий совместности системы алгебраических уравнений. Радикал идеала. Критерий принадлежности радикалу идеала. Критерий равенства радикалов двух идеалов. Критерий эквивалентности систем алгебраических уравнений.

Тема 5. Применения базисов Гребнера.

Суммы, произведения и пересечения идеалов. Алгоритм построения базиса пересечения идеалов. НОД и НОК многочленов, алгоритм их нахождения. Частное идеалов. Алгоритм построения базиса частного идеалов. Нормальная форма полиномов в факторкольце, операции в факторкольце. Критерий конечномерности факторкольца. Критерий конечности числа решений системы алгебраических уравнений. 

Topic 1. Ideals and affine varieties. 

Polynomials and affine space. Affine varieties. Ideals and their connection with affine varieties. Systems of algebraic equations and their connection with ideals.

Topic 2. Groebner bases. 

Monomial orders. An algorithm for dividing a polynomial by a system of polynomials in a ring of polynomials in several variables. Monomial ideals and Dixon’s lemma. Hilbert’s basis theorem and Groebner bases. Properties of Groebner bases. S-polynomials, Buchberger’s criterion for -pairs. Buchberger’s algorithm. Minimal and reduced Groebner basis. Criterion for belonging to an ideal. Criterion for equality of ideals. 

Topic 3. Exclusion theory. 

Excluding ideals. The exclusion theorem, its application to systems of algebraic equations. Extension theorem. 

Topic 4. Hilbert Nullstellensatz. 

Weak and strong Hilbert’s theorems on nulls. A compatibility criterion for a system of algebraic equations. Radical of an ideal. A criterion for belonging to the radical of an ideal. A criterion for the equality of radicals of two ideals. A criterion for the equivalence of systems of algebraic equations. 

Topic 5. Applications of Gröbner bases. 

Sums, products, and intersections of ideals. An algorithm for constructing a basis for the intersection of ideals. GCD and LCM of polynomials, an algorithm for finding them. Quotient of ideals. An algorithm for constructing a basis for the quotient of ideals. Normal form of polynomials in a quotient ring, operations in a quotient ring. A criterion for the finite dimensionality of a quotient ring. A criterion for the finiteness of the number of solutions of a system of algebraic equations.

Формируемые компетенции / The formed competences

Базовые профессиональные компетенции:

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

Применять основные алгебраические и геометрические понятия, конструкции и методы при решении теоретических и прикладных математических задач.

Специализированные компетенции:

Применять ключевые методы защиты информационных систем при реализации криптоприложений.

Basic professional competencies: 

Use concepts and methods of real, complex and functional analysis and apply them to study models of the surrounding world. 

Apply basic algebraic and geometric concepts, constructions and methods when solving theoretical and applied mathematical problems. 

Specialized competencies: 

Apply key methods of protecting information systems when implementing cryptographic applications.

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able)

В результате изучения учебной дисциплины студент должен

знать:

• основные понятия и результаты теории базисов Гребнера;
• методы доказательств важнейших результатов, изучаемых в рамках учебной дисциплины «Базисы Гребнера»;
• алгоритмы решения основных задач, связанных с системами алгебраических уравнений и с идеалами в кольцах полиномов;

уметь:

– строить базис Гребнера идеала;

– применять критерий Бухбергера -пар;

– строить базис пересечения идеалов;

– решать задачу о принадлежности идеалу и о принадлежности радикалу идеала;

– решать задачу о совместности системы и о конечности числа решений системы;

– уметь решать алгоритмические задачи по курсу «Базисы Гребнера»;

владеть:

•  основными навыками решения задач теории базисов Гребнера;
•  методами доказательств основных теорем, встречающихся в курсе «Базисы Гребнера»;

– навыками самообразования и способами использования аппарата теории базисов Гребнера для проведения математических и междисциплинарных исследований.

As a result of studying the academic discipline, the student should 

know: 

– the basic concepts and results of the theory of Groebner bases 

– methods of proving the most important results studied within the framework of the academic discipline “Groebner Bases”; 

– algorithms for solving the main problems associated with systems of algebraic equations and with ideals in polynomial rings; 

be able to:

– construct a Groebner basis of an ideal; 

– apply the Buchberger criterion of S-pairs; 

– construct a basis of intersection of ideals; 

– solve the problem of belonging to an ideal and belonging to the radical of an ideal; 

– solve the problem of compatibility of a system and the finiteness of the number of solutions of a system; 

– be able to solve algorithmic problems according to the course “Groebner Bases”; possess: 

– the basic skills of solving problems of the theory of Groebner bases; 

– methods of proving the main theorems encountered in the course “Groebner Bases”; – self-education skills and methods of using the apparatus of Groebner’s basis theory to conduct mathematical and interdisciplinary research.

Семестр изучения учебной дисциплины, модуля / Semester of study

7

7

Пререквизиты / Prerequisites

Алгебра и теория чисел

Algebra and Number Theory 

Трудоемкость в зачетных единицах (кредитах) / Credit units

3 зачетные единицы.

3 credit units.

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work, 

hours of self-directed learning

Всего 108 часов, из них 54 аудиторных часа и 54 часа самостоятельной работы.

A total of 108 hours, of which 54 academic hours of students’ class work and 54 hours of self-directed learning.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Устный опрос, коллоквиум, 

контрольная работа.

Зачет

Oral survey, colloquium, test. 

The test.