ВВЕДЕНИЕ 3
Глава 1. АЛГЕБРЫ ПОЛИНОМОВ 5
1.1 Свободные алгебры 5
1.2 Базисы Гребнера в некоммутативном случае 8
1.3 Базисы Гребнера в коммутативном случае 12
Глава 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БУХБЕРГЕРА НА ЯЗЫКЕ PYTHON 18
2.1 Символьные вычисления в Python 18
2.2 Построение базисов Гребнера 22
Глава 3. ПОСТРОЕНИЕ БАЗИСОВ ГРЕБНЕРА С ПОМОЩЬЮ РАЗРАБОТАННОГО ПАКЕТА PYTHON 25
3.1 Кольца с нарушением свойства ИБЧ 25
3.2 Построение колец с нарушением свойства ИБЧ 28
3.3 Присоединение идемпотентной матрицы к кольцу 31
ЗАКЛЮЧЕНИЕ 37
СПИСОК ЛИТЕРАТУРЫ
Приложение
Целью магистерской диссертации является написание пакета для автоматизации процесса построения базисов Гребнера. Базисы Гребнера были введены в 1965 г. в дипломной работе Б. Бухбергера [1] (см. [2]) для алгоритмического решения некоторых фундаментальных проблем коммутативной алгебры (теория полиномиальных идеалов, алгебраическая геометрия). Одновременно с работами Б. Бухбергера появляются работы А. И. Ширшова [3], где он вводит понятие композиции для лиевских многочленов, и Л. А. Бокутя [4], где был построен первый пример множества лиевских полиномов, не являющегося замкнутым относительно композиции. К истории исследований базисов Гребнера можно отнести такие знаменитые методы, как алгоритм Евклида, метод Гаусса (частный случай алгоритма Бухбергера) поиска решений систем линейных уравнений, работы Гильберта, Гребнера и другие. Существование стандартного базиса идеала опирается на клемму о композиции^, которая впервые была доказана А. И. Ширшовым для свободных алгебр Ли. Аналогичное утверждение для свободного ассоциативного и коммутативного случая долгое время не проверялось и считалась очевидным вплоть до более поздних работ Л. А. Бокутя (см. [5]). Особое значение теория базисов Гребнера имеет в коммутативном случае. Данный метод задает критерии совместности системы уравнений, эквивалентности систем, а также условие конечности числа решений. Если система уравнений имеет бесконечное множество решений, то метод базисов Гребнера позволяет определить размерность множества решений.
Наиболее известным алгоритмом построения базисов Гребнера является алгоритм Бухбергера. Алгоритм Бухбергера уже реализован как на платных решениях - Mathematica, Maple, MATHLAB, так и в бесплатных системах компьютерной алгебры, например, SageMath. Однако, для некоммутативных базисов Гребнера готовых программных комплексов нам найти не удалось. Было принято решение разработать на языке Python программу для поиска базисов Гребнера с помощью алгоритма Бухбергера. Язык программирования Python был выбран потому что фактически он стал основным инструментом в компьютерной алгебре. Язык близок к системе компьютерной алгебры MATH LAB, и на нем хорошо программируются математические вычисления. Также Python хорошо работает в связке с такими языками программирования, как С, C++, Fortran, которые широко применяются в научных расчетах. Кроме этого большая часть библиотек и программных модулей, написанных на Python, распространяются бесплатно.
В первой главе работы приводятся основные сведения теории ассоциативных алгебр, метод базисов Гребнера, алгоритм Бухбергера, разбирается ряд примеров. Во второй главе описана работа с запрограммированным пакетом для вычисления базисов Гребнера, возможные варианты его использования. В третьей главе с помощью разработанной программы мы строим примеры колец специального вида.
В работе были всесторонне изучены как коммутативные, так и некоммутативные базисы Гребнера. Были разобраны ряд примеров, приведено доказательство некоторых теорем.
Известно, что при построении коммутативных базисов Гребнера алгоритм Бухбергера всегда имеет конечное число шагов (теорема Гильберта о базисе). Для некоммутативных базисов это свойство не выполняется (в одном из примеров был получен бесконечный базис). Принимая это во внимание, а также тот факт, что программу нужно было писать с нуля из-за отсутствия каких-либо готовых функций была задача автоматизировать процесс вычислений отдельных функций (поиск композиции, редукция, нормировка). После реализации данных функций и их тестирования было решено реализовать алгоритм Бухбергера для некоммутативных базисов Гребнера полностью с возможностью для пользователя остановить процесс построения базиса (например, в тех случаях, когда структуру базиса можно определить на основе уже построенных элементов). После тестирования получившегося решения функционал программы был расширен и кроме вычислений над полем рациональных чисел была добавлена возможность работы с конечными полями Zp (p - простое число).
Получившийся инструмент оказался очень удобен при построении примеров колец с уникальными свойствами (а именно кольца с нарушением свойства инвариантности базисного числа). Были изучены и изложены основные теоретические сведения по данной проблематике, разобраны примеры колец с нарушением свойства инвариантности базисного числа. Также была рассмотрена конструкция присоединения идемпотентной матрицы к полю, построены примеры. Для вычисления базисов Гребнера использовалась разработанная Python библиотека.
