Počítačová algebra


Průběh přednášky

   (22.2.) Motivace a předpoklady. Cíle přednášky. Asymptotické odhady a časová složitost v počtu základních operací. 1.Školské algoritmy pro celá čísla. Prezentace velkých celých čísel v dané bázi, prezentace racionálních čísel a těles Zp. Časová složitost školských algoritmů sčítání, odčítání a jednociferného násobení

   (1.3.) Časová složitost školských algoritmů násobení, dělení se zbytkem, převodu mezi bázemi a binárního mocnění velkých celých čísel:. 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. Odhad časové složitosti.

   (8.3.) Binární Eukleidův algoritmus (na cvičení). 3.Násobení v Z pomocí rekurze. Karacubův algoritmus a jeho časová složitost. Časová složitost obecných algoritmů rozděl a panuj. Časová složitost algoritmu Toom-3.

   (15.3.) Algoritmy Toom-s. 4. 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. Časová složitost operací na konečných tělesech.

   (22.3.) 5. Čí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.

   (29.3.) Sdílení tajemství, (k,n)-schéma. Modulární reprezentace celých čísel a polynomů. 6. Rychlá Fourierova transformace a rychlé násobení polynomů. 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 pro polynomy s celočíselnými koeficienty a její časová složitost. Rychlé násobení polynomů.

   (5.4.) Iterativní varianta rychlé Fourierovy transformace polynomů (na cvičení). Rychlé násobení polynomů nad tělesy bez primitivních n-tých mocnin. Shönhagenův-Strassenův trik.

   (12.4.) 7. Rychlé dělení polynomů, mocninné řady a Newtonova metoda. Inverzní mocninné řady. 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ů.

   (19.4.) Numerické metody pro hledání kořene spojité funkce. Newtonova metoda tečen.

   (26.4.) 8. Výpočet NSD v okruzích polynomů nad Z. 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). Vztah NSD(f, g) v okruhu Z[x] a NSD(f mod p, g mod p) v okruhu Zp[x]

   (3.5.) Použitelná, šťastná a smolná prvočísla. Landau-Mignottova mez. Problém vedoucího koeficientu a algoritmus na výpočet NSD celočíselných polynomů s jedním velkým prvočíslem. Modulární algoritmus na výpočet NSD celočíselných polynomů s více malými prvočísly.

   (10.5.) 9.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. 10.Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice.

   (17.5.) Smolných prvočísel a smolných hodnot je jen konečně mnoho. Vyjádření rezultantu polynomů jako jejich polynomiální kombinace.

   (24.5.) Výpočet rezultantů pomocí kořenů. Subrezultanty a Fundamentální věta o PRS. 11.Obecná Čínská věta o zbytcích. Komaximální ideály. Čínská věta o zbytcích pro komutativní okruhy. 12.Shrnutí.