Počítačová algebra

Průběh přednášky

   (23.2.) 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. Časová složitost algoritmu. Školský algoritmus sčítání.

   (2.3.) Školské algoritmy odčítání, násobení, dělení se zbytkem a převodu mezi bázemi. Násobení metodou rozděl a panuj, odhady časové složitosti rekurzivních algoritmů, Karacubův algoritmus.

   (9.3.) Algoritmus Toom-k pro násobení. Násobení matic. Eukleidův algoritmus pro hledání největšího společného dělitele.

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

   (23.3.) Algoritmy na Čínskou větu o zbytcích.

   (30.3.) Diskrétní Fourierova transformace. Rychlá Fourierova transformace a Rychlé násobení polynomů.

   (6.4.) Primitivní odmociny z jedné a polynomy s racionálními koeficienty. Rychlé dělení polynomů.

   (13.4.) Kořeny rovnic a Newtonovy metody.

   (20.4.) Posloupnosti polynomiálních zbytků, soudělnost polynomů nad Gaussovým oborem.

   (27.4.) Modulární algoritmus na výpočet NSD celočíselných polynomů.

   (4.5.) Bezčtvercová faktorizace polynomů.

   (11.5.) Berlekampův algoritmus pro faktorizace polynomů nad konečným tělesem. Pomocné algoritmy pro Henselovo zdvihání.

   (25.5.) Henselovo zdvihání, kombinace faktorů a Berlekampův-Henselův algoritmus.