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ů.