Počítačová algebra


Průběh přednášky

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

   (20.2.) Operace na prezentacích celých čísel a čísel, polynomů, konečných těles a konečných rozšíření racionálních čísel. Časová složitost algoritmu. Školské algoritmy sčítání a odčítání.

   (25.2.) Školské algoritmy násobení, dělení se zbytkem a převodu mezi bázemi.

   (4.3.) Karacubův algoritmus násobení. Časová složitost obecných algoritmů rozděl a panuj.

   (6.3.) Algoritmus Toom-3. Binární mocnění. Eukleidův algoritmus pro hledání největšího společného dělitele a Bezoutových koeficientů.

   (11.3.) Časový odhad složitosti Eukleidova algoritmu. Binární Eukleidův algoritmus.

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

   (20.3.) Eukleidův algoritmus na polynomech. Operace na konečných tělesech a rozšířeních konečného stupně racionálních číslech.

   (25.3.) Modulární reprezentace celých čísel a polynomů, násobení v modulární reprezentaci. Zobecněná Čínská věta o zbytcích. Lagrangeův algoritmus na Čínskou větu o zbytcích.

   (3.4.) Lagrangeův a Garnerův algoritmus na Čínskou větu o zbytcích.

   (8.4.) Sdílení tajemství, (k,n)-schéma. Primitivní odmociny z jedné v komplexních číslech a konečných tělesech. Diskrétní Fourierova transformace polynomů.

   (15.4.) Rychlá Fourierova transformace polynomů, rekurzivní a iterativní varianta.

   (17.4.) Rychlé násobení polynomů. Rychlá Fourierova transformace pro polynomy s celočíselnými koeficienty. Shönhagenův-Strassenův trik.

   (22.4.) Inverzní mocninné řady. Rychlý výpočet prvních n členů inverzní mocninné řady k polynomu.

   (29.4.) Rychlé dělení polynomů. Aproximace zlomků.

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

   (13.5.) Rezultanty a soudělnost polynomů nad Gaussovým oborem. Šťastná a smolná prvočísla.

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

   (20.5.) Časové odhady výpočtu NSD. Posloupnosti polynomiálních zbytků.