Počítačová algebra

Průběh přednášky

   (22.2.) Časová složitost algoritmu. Počítačová prezentace velkých celých čísel, racionálních čísel, polynomů, konečných těles a konečných rozšíření racionálních čísel. Školské algoritmy sčítání, odčítání a násobení.

   (24.2.) Školské algoritmy dělení se zbytkem a převodu mezi bázemi. Násobení metodou rozděl a panuj, Karacubův algoritmus.

   (7.3.) Binární mocnění. Eukleidův algoritmus pro hledání největšího společného dělitele a Bezoutových koeficientů, binární Eukleidův algoritmus.

   (14.3.) Operace na konečných tělesech a racionálních číslech. Základní operace s polynomy (sčítání, násobení, dělení se zbytkem, Eukleidův algoritmus).

   (21.3.) Operace na konečných tělesech a rozšířeních konečného stupně racionálních číslech. Zobecněná Čínská věta o zbytcích. Lagrangeův algoritmus na Čínskou větu o zbytcích.

   (28.3.) Garnerův algoritmus na Čínskou větu o zbytcích. Modulární reprezentace okruhu. Násobení polynomů pomocí modulární reprezentace. Diskrétní Fourierova transformace polynomů.

   (4.4.) Rychlá Fourierova transformace a rychlé násobení polynomů. Primitivní odmociny z jedné v konečných tělesech. Rychlá Fourierova transformace pro polynomy s celočíselnými koeficienty.

   (11.4.) Inverzní mocniné řady. Rychlé dělení polynomů.

   (18.4.) Kořeny rovnic a Newtonovy metody. Posloupnosti polynomiálních zbytků.

   (25.4.) Časové odhady výpočtu NSD oboru celočíselných polynomů pomocí posloupnosti polynomiálních zbytků. Rezultanty a soudělnost polynomů nad Gaussovým oborem.

   (2.5.) Modulární algoritmus na výpočet NSD celočíselných polynomů s jedním prvočíslem.

   (9.5.) Efektivní modulární algoritmus na výpočet NSD celočíselných polynomů. Bezčtvercová faktorizace polynomů. Berlekampův algoritmus pro faktorizace polynomů nad konečným tělesem.

   (23.5.) Pomocné algoritmy pro Henselovo zdvihání a Henselovo zdvihání. Berlekampův-Henselův algoritmus.