Počítačová algebra


Průběh přednášky

   (4.10.) 1. Časová složitost a obory výpočtů. Asymptotické odhady a časová složitost v počtu základních operací [PA, část 1.1]. Vyjádření časové složitosti obecných rekurentních algoritmů [PA, Tvrzení 4.2 a cvičení 4.2]. Prezentace velkých celých čísel v dané bázi a převod mezi bázemi. Prezentace racionálních čísel, těles Zp, okruhů polynomů, obecných konečných těles a rozšíření racionálních čísel [PA, části 3.1-5].

   (11.10.) 2.Základní algoritmy pro celá čísla. Časová složitost školských algoritmů sčítání, odčítání, dělení se zbytkem a převodu mezi bázemi.[PA, část 4.1]. Školské a asymptoticky rychlejší násobení (Karacubův a Toomovy algoritmy) a jejich časová složitost [PA, část 4.2 a cvičení 4.6].

   (18.10.) 3.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. Odhad časové složitosti [PA, část 4.4].

   (25.10.) 4.Binární algoritmy. Binární Eukleidův algoritmus [PA, cvičení 4.18], binární mocnění [PA, část 4.3]. 5. Základní algoritmy pro polynomy. Časová složitost školských operací s polynomy: sčítání, násobení, dělení se zbytkem a dosazení. Pseudodělení polynomů. Eukleidův algoritmus pro polynomy nad tělesem [PA, část 5.1].

   (1.11.) 6. Čínská věta o zbytcích Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace. Čínská věta o zbytcích v oborech hlavních ideálů. Lagrangeův a Garnerův algoritmus na Čínskou větu o zbytcích. Časové odhady Lagrangeova a Garnerova algoritmu [PA, kapitoly 6 a 7].

   (8.11.) 7. Diskrétní Fourierova transformace. Diskrétní Fourierova transformace polynomů. 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 a její časová složitost, iterativní varianta rychlé Fourierovy transformace polynomů [PA, kapitola 8].

   (15.11.) 8. Rychlé násobení polynomů. Rychlé násobení polynomů nad tělesy s primitivní n-tou odmocninou. Rychlé násobení nad tělesem Zp and racionálními čísly, modulární počítání pomocí FFT prvočísel, Shönhagenův-Strassenův trik [PA, kapitola 9]. Časová složitost operací na konečných tělesech [PA, část 5.2].

   (22.11.) 9. Rychlé dělení polynomů. Mocninné řady a jejich invertování. Výpočet prvních n členů inverzní mocninné řady k polynomu, rychlý výpočet prvních n členů inverzní mocninné řady. Reciproké polynomy a rychlé dělení polynomů. Aproximace zlomků [PA, kapitola 10].

   (29.11.) 10. NSD v okruzích polynomů. Obsah a primitivní část polynomu nad nad Gaussovým oborem. Výpočet NSD v polynomech nad Gaussovým oborem. Výpočet NSD pomocí posloupnosti polynomiálních zbytků (PRS) [PA, kapitola 12].

   (6.12.) 11.Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice. Vyjádření rezultantu polynomů jako jejich polynomiální kombinace, výpočet rezultantů pomocí kořenů. Subrezultanty a Fundamentální věta o PRS [PA, kapitola 13].

   (13.12.) 12.Modulární výpočet NSD celočíselných polynomů. Vztah NSD(f, g) v okruhu Z[x] a NSD(f mod p, g mod p) v okruhu Zp[x]. Použitelná, šťastná a smolná prvočísla, smolných prvočísel a smolných hodnot je jen konečně mnoho. Landau-Mignottova mez. Problém vedoucího koeficientu. Algoritmus na výpočet NSD celočíselných polynomů s jedním velkým prvočíslem. [PA, 14.1-14.7].

   (20.12.) Modulární algoritmus na výpočet NSD celočíselných polynomů s více malými prvočísly [PA, zbytek sekce 14.1].

   (3.1.) 13.NSD polynomů více neurčitých. Reprezentace polynomů více neurčitých nad Gaussovým oborem. Modulární výpočet NSD polynomů více neurčitých, použitelné, šťastné a smolné hodntoty, problém vedoucího koeficientu [PA, sekce 14.2].


[PA] L. Barto, D. Stanovský: Počítačová algebra, MatfyzPress, 2017.