Algoritmy na polynomech


Průběh přednášky

   (2.10.) 1.Přepisování. Ideály okruhů, báze a problém náležení ideálu. Terminující, normální a konveregentní relace. Přípustná uspořádání na termech.

   (9.10.) Uspořádání na polynomech, relace přepisování jako terminující relace na polynomech. Příklady a vlastnosti relace přepisování.

   (16.10.) 2.Gröbnerovy báze. Otázka náležení ideálu a přepisování. Gröbnerova báze a Buchbergerův algoritmus A. Fundovaná indukce. Kritické páry a s-polynomy. Formulace Buchbergerovy věty a Buchbergerův algoritmus B.

   (23.10.) 3.Důkaz Buchberegerovy věty. Konfluentní, lokálně konfluentní a slabě lokálně konfluentní relace. Konfluentní relace jsou normální, popis konvergentní relace jako slabě konfluentní terminující relace.

   (30.10.) Důkaz konfluence slabě konfluentní terminující relace. Reformulace a důkaz Buchberegerovy věty.

   (6.11.) 4.Redukce. Redukovaná normovaná Gröbnerova báze a její nalezení. Existence a jednoznačnost redukované normované Gröbnerova báze. Redukované Gröbnerovy báze ideálů v okruzích polynomů jedné neurčité a ideálů gennerovaných lineárními polynomy.

   (13.11.) 5.Aplikace. Algoritmy náležení prvku ideálu a rovnosti ideálů. Gröbnerova báze průniku ideálů a eliminační lemma. Problém náležení radikálu.

   (20.11.) 6.Bezčtvercový rozklad. Existence bezčtvercového rozkladu polynomů nad Gaussovým oborem. Frobeniův endomorfismus a existence odmocnin polynomů.

   (27.11.) Vztah NSD(f,f' ) a bezčtvercového rozkladu polynomu f nad obory nulové charakteristiky a nad konečnými tělesy. Výpočet bezčtvercové faktorizace polynomů nad obory nulové charakteristiky a nad konečnými tělesy.

   (4.12.) Časová složitost bezčtvercové faktorizace. 7.Berlekampův algoritmus. Vektorové prostory určené ireducibilním rozkladem bezčtvercového polynomu nad konečným tělesem. Oddělení dvou polynomů pomocí nekonstantního polynomů podprostoru vlastních vektorů mocniny Frobeniova automorfismu pro vlastní číslo 1.

   (11.12.) Oddělení dvou polynomů pomocí bázických polynomů a Berlekampův algoritmus pro faktorizaci polynomů. Časová složitost Berlekampova algoritmu. Rozklad obecného polynomu nad konečným tělesem.

   (18.12.) 8.Henselovo zdvihání. Pomocné algoritmy pro Henselovo zdvihání. Henselovo zdvihání. Korektnost a časová složitost algoritmu Henselova zdvihání.

   (8.1.) 9.Kombinace faktorů. Kombinace faktorů podle Zassenhause. Berlekampův-Henselův algoritmus pro hledání ireducibilního rozkladu polynomů nad celými čísly.



Literatura.
[SB] D. Stanovský, L. Barto: Počítačová algebra, Matfyzpress.