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.