Přednáška: pondělí 15:40 -- 18:05, K2
Cvičení vedené Alexandrem Slávikem: sudé pondělí semestru 12:20 -- 13:50, K4, odkaz na stránku
Zápočet bude udělen za tři správně vyřešené a včas odevzdané domácí úkoly. Detaily na stránce cvičení.
Zkouška je písemná s ústní debatou nad výsledky. Zkoušený dostane dvě otázky, na které si písemně připraví odpovědi. První otázka bude vyžadovat formulaci a důkaz správnosti algoritmu, případně formulování a důkaz některého ze souvisejících teoretických problémů, druhá otázka se zaměří na odhad časové složitosti (jiného) algoritmu případně také simulaci chodu algoritmu na snadno upočitatelném konkrétním vstupu.Základní literatura: Skripta Stanovský, Barto: Počítačová algebra (Matfyzpress 2017) + errata.
Předmětem kurzu jsou základní algoritmy pro aritmetiku čísel a polynomů. Přednáška má tři základní cíle:
| téma | četba (Počítačová algebra) |
|
|---|---|---|
| 30.9. | Časová složitost a obory výpočtů. Asymptotické odhady a časová složitost v počtu základních operací. Vyjádření časové složitosti obecných rekurentních algoritmů -- mistrovská metoda (metoda rozděl a panuj). Prezentace velkých celých čísel v dané bázi. Prezentace racionálních čísel, těles Zp, okruhů polynomů, obecných konečných těles a rozšíření racionálních čísel. |
sekce 1.1, 3.1-3.5, začátek 4.2 a cvičení 4.3 |
| 07.10. | Základní algoritmy pro celá čísla. Časová složitost školských algoritmů sčítání, odčítání, dělení se zbytkem a převodu mezi bázemi. Školské a asymptoticky rychlejší násobení (Karacubův a Toomovy algoritmy) a jejich časová složitost, zmínka o časové náročnosti násobení matic |
sekce 4.1, 4.2 a cvičení 4.6 |
| 15.10. | 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.
|
sekce 4.4 |
| 21.10. | Binární algoritmy. Binární Eukleidův algoritmus, binární mocnění 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 |
cvičení 4.18 a 5.4, sekce 4.3 a 5.1 |
| 28.10. | přednáška není -- státní svátek | |
| 4.11. | Čí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
|
kapitoly 6 a 7 |
| 11.11. | Diskrétní 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. Rychlá Fourierova transformace a její časová složitost, iterativní varianta rychlé Fourierovy transformace polynomů (velice informativně) |
kapitola 8 |
| 18.11. | Rychlé násobení polynomů. Rychlé násobení polynomů nad tělesy s primitivní n-tou odmocninou. Rychlé násobení nad tělesem Zp a nad racionálními čísly, modulární počítání pomocí FFT prvočísel, Shönhagenův-Strassenův trik. Časová složitost operací na konečných tělesech | kapitola 9 a sekce 5.2 |
| 25.11. | 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ů. Aproximace zlomků | kapitola 10 |
| 2.12. | 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. Výpočet NSD pomocí posloupnosti polynomiálních zbytků (PRS). Rezultanty. Soudělnost polynomů nad Gaussovým oborem, definice Sylvesterovy matice a resultantu. | kapitola 12, začátek kapitoly 13 |
| 9.12. | Rezultanty (pokračování). Sylvesterovo kritérium. Vyjádření rezultantu polynomů jako jejich polynomiální kombinace, výpočet rezultantů pomocí kořenů. Subrezultanty a Fundamentální věta o PRS. Modulární výpočet NSD celočíselných polynomů. Vztah NSD(f,g) v okruhu Z[x] a NSD(f mod p, g mod p) v okruhu Zp[x]. Použitelná, šťastná, smolná prvočísla, smolných je jen konečně mnoho. | kapitola 13, cvičení 13.2, začátek 14.1 |
| 16.12. | Modulární výpočet NSD celočíselných polynomů (pokračování). Landau-Mignottova mez. Problém vedoucího koeficientu. Algoritmus na výpočet NSD celočíselných polynomů (s jedním velkým prvočíslem, s více malými prvočísly). | kapitola 14.1, cvičení 14.2 a 14.3 |
| 6.1. | 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 | kapitola 14.2, cvičení 14.9-14.11 |
Konzultace: po dohodě emailem na zuzka-at-kam.mff.cuni.cz. Je-li něco nejasné, nebojte se zeptat!
Doplňující literatura: