Počítačová algebra
Průběh přednášky
(22.2.) Motivace a obsah přednášky. 1.Prezentace a školské algoritmy na nich. Datové typy. Časová složitost algoritmu.
Počítačově prezentovatelné algebraické struktury.
(23.2.) 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. Délka vstupu a základní operace.
(1.3.) Časová složitost školských algoritmů pro počítání s velkými celými čísly:
sčítání, odčítání, jednociferného násobení, násobení celých čísel, dělení se zbytkem, převodu mezi bázemi a binárního mocnění.
(8.3.) Časová složitost školských operací s polynomy:
sčítání, násobení, dělení se zbytkem a pseudodělení.
Operace na prezentacích konečných těles a konečných rozšíření racionálních čísel.
(9.3.) 2.Eukleidův algoritmus. Eukleidův algoritmus pro hledání největšího společného dělitele a Bezoutových koeficientů.
Korektnost a počet kroků cyklu. Časový odhad složitosti Eukleidova algoritmu pro celá čísla.
(15.3.) Binární Eukleidův algoritmus. Eukleidův algoritmus pro polynomy nad tělesem.
(22.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.
(23.3.) Časová složitost algoritmu Toom-3. Algoritmy Toom-k. 4. Čínská věta o zbytcích v oborech hlavních ideálů Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace.
(29.3.) Čí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.
(5.4.) Sdílení tajemství, (k,n)-schéma. Modulární reprezentace celých čísel a polynomů.
5. Rychlá 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.
(6.4.)
Rychlá Fourierova transformace a její časová složitost. Iterativní varianta rychlé Fourierovy transformace polynomů.
Rychlé násobení polynomů.
(12.4.) Rychlá Fourierova transformace pro polynomy s celočíselnými koeficienty,
Shönhagenův-Strassenův trik.
6. Newtonovy metody. Inverzní mocninné řady. Výpočet prvních n členů inverzní mocninné řady k polynomu.
(19.4.) Rychlý výpočet prvních n členů inverzní mocninné řady. Reciproké polynomy a rychlé dělení polynomů. Aproximace zlomků.
(20.4.) Newtonova metoda tečen. 7. Největší společné dělitele v okruzích polynomů
Gaussovým obory, obsah a primitivní část polynomu nad nad Gaussovým oborem. Gaussovo lemma .
(26.4.) Dělitelnost primitivních polynomů nad Gaussovým oborem a výpočet NSD v polynomech nad Gaussovým oborem.
Posloupnosti polynomiálních zbytků (PRS).
(3.5.) Výpočet NSD pomocí posloupnosti polynomiálních zbytků (PRS). Heuristické odhady časové složitosti Eukleidovy a redukované PRS pro celočíselné polynomy.
(4.5.) 8.Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice.
Rezultanty a Eukleidův algoritmus.
(10.5.) Výpočet rezultantů. Subrezultanty a Fundamentální věta o PRS.
(18.5.) 9. Modulární algoritmy na výpočet NSD. Použitelná, šťastná a smolná prvočísla. Smolných prvočísel je jen konečně mnoho. 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.
(24.5.) Modulární algoritmus na výpočet NSD celočíselných polynomů s více malými prvočísly. Modulární výpočet NSD polynomů více neurčitých.