Počítačová algebra


Průběh přednášky

   (2.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].

   (9.10.) 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]. 2.Základní algoritmy pro celá čísla. Časová složitost školských algoritmů sčítání, odčítání a jednociferného násobení [PA, část 4.1].

   (16.10.) Časová složitost školských algoritmů 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].

   (23.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]. Korektnost a složitost Steinova (binárního Eukleidova) algoritmu na počítání NSD [PA, cvičení 4.18].

   (30.10.) Binární mocnění [PA, část 4.3]. 4. Základní algoritmy pro práci s 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]. 5. Čínská věta o zbytcích Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace.

   (6.11.) Čí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]. 6. Diskrétní Fourierova transformace a rychlé násobení polynomů. Diskrétní Fourierova transformace polynomů.

   (13.11.) Primitivní odmociny z jedné v komplexních číslech a konečných tělesech. Rychlá Fourierova transformace a její časová složitost, iterativní varianta rychlé Fourierovy transformace polynomů [PA, kapitola 8]. Rychlé násobení polynomů nad tělesy s primitivní n-tou odmocninou [PA, kapitola 9].

   (20.11.) 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]. 7. 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ů. [PA, kapitola 10].

   (27.11.) Důkaz korektnosti a časové složitosti rychlého dělení polynomů. Aproximace zlomků [PA, kapitola 10]. 8. 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. Posloupnosti polynomiálních zbytků (PRS) [PA, kapitola 12].

   (4.12.) Výpočet NSD pomocí (PRS) [PA, konec kapitoly 12]. 9.Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice. Vyjádření rezultantu polynomů jako jejich polynomiální kombinace [PA, 13.1-3].

   (11.12.) Výpočet rezultantů pomocí kořenů, subrezultanty a Fundamentální věta o PRS [PA, 13.4-5]. 10.Modulární výpočet NSD celočíselných polynomů. Časová složitost operací na konečných tělesech [PA, část 5.2]. Vztah NSD(f, g) v okruhu Z[x] a NSD(f mod p, g mod p) v okruhu Zp[x] [PA, 14.1-14.7].


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