Počítačová algebra
Průběh přednášky
(25.2.) 1.Prezentace a školské algoritmy na nich. Datové typy. Časová složitost algoritmu.
Počítačová prezentace velkých celých čísel, racionálních čísel, polynomů, konečných těles
a rozšíření konečného stupně racionálních čísel.
Operace na prezentacích celý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í, jednociferného násobení a násobení celých čísel.
(3.3.) Školské algoritmy dělení se zbytkem a převodu mezi bázemi. Časová složitost operací s polynomy.
Sčítání, násobení, dělení se zbytkem a pseudodělení na polynomech.
2.Eukleidův algoritmus v Z. Eukleidův algoritmus pro hledání největšího společného dělitele a Bezoutových koeficientů.
Korektnost a počet kroků cyklu.
(10.3.) Časový odhad složitosti Eukleidova algoritmu pro celá čísla.
(17.3.) Binární Eukleidův algoritmus. Eukleidův algoritmus pro polynomy nad tělesem.
(24.3.) Časová složitost operací na konečných tělesech a polynomech nad konečnými tělesy.
3.Rozděl a panuj. Karacubův algoritmus násobení. Časová složitost obecných algoritmů rozděl a panuj.
Časová složitost algoritmu Toom-3. Algoritmy Toom-k.
(31.3.) 4. Modulární reprezentace Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace. Zobecněná Čínská věta o zbytcích.
(7.4.) Modulární reprezentace celých čísel a polynomů, násobení v modulární reprezentaci.
Lagrangeův a Garnerův algoritmus na Čínskou větu o zbytcích. Časové odhady Lagrangeova a Garnerova algoritmu.
Sdílení tajemství, (k,n)-schéma. 5. Diskrétní Fourierova transformace. Diskrétní Fourierova transformace polynomů.
(14.4.) Primitivní odmociny z jedné v komplexních číslech a konečných tělesech.
Inverzní diskrétní Fourierova transformace jako Diskrétní Fourierova transformace.
Rychlá Fourierova transformace.
(21.4.) Iterativní varianta rychlé Fourierovy transformace polynomů.
Rychlé násobení polynomů. Rychlá Fourierova transformace pro polynomy s celočíselnými koeficienty,
Shönhagenův-Strassenův trik.
6. Newtonovy metody. Inverzní mocninné řady. Rychlý výpočet prvních n členů inverzní mocninné řady k polynomu.
(28.4.) Reciproké polynomy a rychlé dělení polynomů. Aproximace zlomků.
(5.5.) Newtonova metoda tečen.
7.GCD a PRS.
Výpočet GCD v polynomech nad Gaussovým oborem.
Výpočet GCD celočíselných polynomů pomocí posloupnosti polynomiálních zbytků (PRS).
(12.5.) Heuristické odhady časové složitosti Eukleidovy redukované PRS.
8.Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice.
(19.5.) Rezultanty a Eukleidův algoritmus. Subrezultanty a Fundamentální věta o PRS.
9. Modulární algoritmy na výpočet GCD. Šťastná a smolná prvočísla. Modulární algoritmy na výpočet GCD celočíselných polynomů s jedním velkým prvočíslem.
(26.5.) Modulární algoritmy na výpočet GCD celočíselných polynomů s více malými prvočísly.
Modulární algoritmus na výpočet GCD polynomů více neurčitých.