Algoritmy na polynomech


Průběh přednášky

   (4.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.

   (11.10.) Uspořádání na polynomech, relace přepisování jako terminující relace na polynomech. Otázka náležení ideálu a Gröbnerova báze.

   (18.10.) Buchbergerův algoritmus A. 2.Hledání Gröbnerovy báze. Kritické páry a s-polynomy. Formulace Buchbergerovy věty a Buchbergerův algoritmus B. Konfluentní a lokálně konfluentní relace.

   (25.10.) Konfluentní relace jsou normální. Fundovaná indukce. Slabě konfluentní relace, charakterizace konvergentní relace jako slabě konfluentní terminující relace.

   (1.11.) Důkaz Buchberegerovy věty. 3.Redukce. Redukovaná normovaná Gröbnerova báze a její nalezení.

   (8.11.) 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.

   (15.11.) 4.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.

   (22.11.) 5.Bezčtvercový rozklad. Existence bezčtvercového rozkladu polynomů nad Gaussovým obrem. Vztah NSD(f,f' ) a bezčtvercového rozkladu polynomu f nad obory nulové charakteristiky a nad konečnými tělesy.

   (29.11.) Výpočet bezčtvercové faktorizace polynomů nad obory nulové charakteristiky a nad konečnými tělesy. 6.Berlekampův algoritmus. Vektorové prostory určené ireducibilním rozkladem bezčtvercového polynomu nad konečným tělesem.

   (6.12.) Oddělení dvou polynomů pomocí bázických polynomů podprostoru vlastních vektorů mocniny Frobeniova automorfismu pro vlastní číslo 1. Berlekampův algoritmus pro faktorizaci polynomů.

   (13.12.) Časová složitost Berlekampova algoritmu. 7.Henselovo zdvihání. Pomocné algoritmy pro Henselovo zdvihání a Henselovo zdvihání.

   (20.12.) Korektnost a časová složitost algoritmu Henselova zdvihání.

   (3.1.) 8.Kombinace faktorů. Kombinace faktorů podle Zassenhause. Berlekampův-Henselův algoritmus pro hledání ireducibilního rozkladu polynomů nad celými čísly. Kroneckerův algoritmus pro hledání ireducibilního rozkladu polynomů více neurčitých.



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