20.500.12556/RUL-134638 Nekomutativne Gröbnerjeve baze in izboljšave Buchbergerjevega algoritma magistrsko delo Non-commutative Gröbner bases and improvements of Buchberger's algorithm Namen tega magistrskega dela je predstaviti teorijo Gröbnerjevih baz idealov v kolobarju nekomutativnih polinomov in tri glavne algoritme za njihov izračun, Buchbergerjev algoritem ter Faugèrjeva algoritma $F_4$ in $F_5$. Začnemo pri osnovah teorije nekomutativnih polinomov, predstavimo algoritem deljenja, definiramo Gröbnerjeve baze idealov nekomutativnih polinomov in dokažemo nekaj njihovih temeljnih lastnosti. Nadaljujemo s klasičnim Buchbergerjevim algoritmom, vpeljemo pojem ovire in nato sledimo korakom Tea More do nekomutativne različice algoritma. Pri tem z Dicksonovo lemo pokažemo končnost prvotnega komutativnega Buchbergerjevega algoritma ter dokažemo nekomutativno različico Buchbergerjevega kriterija in pravilnost nekomutativnega Buchbergerjevega algoritma. Pokažemo, kako množice polinomov pretvoriti v matrike ter hkrati formuliramo komutativen in nekomutativen algoritem $F_4$. Dokažemo pravilnost algoritma $F_4$ in pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo končnost algoritma F4. Definiramo modul vezi množice polinomov in dokažemo nekaj osnovnih lastnosti. Buchbergerjevo teorijo dvignemo v prosti modul nad kolobarjem komutativnih polinomov in definiramo polinomske podpise. Predstavimo osnovnega predstavnika družine podpisnih algoritmov ter dokažemo njegovo pravilnost in končnost. Vpeljemo kriterij $F_5$ in podpisni algoritem uporabimo, da formuliramo algoritem $F_5$. Za konec ponovimo prejšnje korake in predstavimo podpisni algoritem za nekomutativne polinome in dokažemo pravilnost nekomutativnega algoritma $F_5$. Pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo še njegovo končnost. The goal of this Master's thesis is to present the theory of Gröbner bases of ideals in the ring of non-commutative polynomials, and the three main algorithms for computing them, Buchberger's algorithm and Faugère's $F_4$ and $F_5$ algorithms. We start with the basic theory of non-commutative polynomials, present the division algorithm, define Gröbner bases of ideals of non-commutative polynomials, and prove some of their fundamental properties. We continue with the classical Buchberger's algorithm, introduce the concept of obstruction sets, and follow the steps of Teo Mora to the non-commutative version of the algorithm. Doing so, we use Dickson's lemma to show that the original Buchberger's algorithm terminates, and we prove the non-commutative version of Bucherger's Criterion and correctness of the non-commutative version of Buchberger's algorithm. We show how to transform sets of polynomials into matrices, and simultaneously formulate the commutative and non-commutative $F_4$ algorithm. We prove the correctness of the $F_4$ algorithm, and we prove it terminates if a finite Gröbner basis exists for the given ideal. For a finite set of polynomials, we define the syzygy module and prove some of its basic properties. We lift Buchberger's theory into a free module over the ring of commutative polynomials and define polynomial signatures. We present the principal representative of the family of signature-based algorithms and prove its correctness and termination. We introduce the $F_5$ Criterion and use the signature-based algorithm to formulate the $F_5$ algorithm. We conclude by repeating the previous steps to arrive at a non-commutative signature-based algorithm and show the correctness of the non-commutative version of the $F_5$ algorithm. We prove this algorithm terminates if a finite Gröbner bases exists for the given ideal. nekomutativni polinomi Gröbnerjeve baze Buchbergerjev algoritem algoritem $F_4$ algebraična vez podpisni algoritmi algoritem $F_5$ non-commutative polynomials Gröbner bases Buchberger's algorithm $F_4$ algorithm syzygy signature-based algorithms $F_5$ algorithm true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-01-22 08:15:01 2022-01-22 08:15:08 2024-05-29 12:30:10 0000-00-00 00:00:00 2022 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 512 123007 93860099 4289.pdf 4289.pdf 1 1DB2246F6F8CA47D407105A61A9E2E14 fa8a59e096a29b6e6547001c888c0ee9c8558a22d613fff263cd0c96970dde17 d573e2da-7b52-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=153172 Fakulteta za matematiko in fiziko 0 0 0