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.