Přednáška: středa 16:30 -- 18:50, K6
Cvičení vedené Jirkou Pavlů: lichá středa semestru 10:40 -- 12:10, K11
Zápočet bude udělen za tři správně vyřešené a včas odevzdané domácí úkoly. Celkem budou zadány 4 úlohy a na každou z nich budu 3 týdny času. Případně lze zápočet získat za úspěšné vyřešení všech 4 úkolů (zde není nutné úkoly odevzdat v termínu). Poslední možný den na odevzdání úkolů po termínu je 31. 1. 2024. Úkoly můžete odevzdávat i před termínem odevzdání -- s velkou pravděpodobností se na ně pan cvičící stihne podívat dříve a upozornit na případné chyby. Dotazy ohledně cvičení či úkolů směřujte na Jirku Pavlů ( jiri.pavlu294-at-gmail.com).
Zkouška je písemná s ústní debatou nad výsledky. Zkoušený dostane dvě otázky, na které si písemně během jedné až dvou hodin 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čítatelném konkrétním vstupu.Základní literatura: Skripta Stanovský, Barto: Počítačová algebra (Matfyzpress 2017) + errata.
| kapitola 12 |
téma | četba (Počítačová algebra) |
cvičení |
| 4.10. | Č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ů (metoda rozděl a panuj). Prezentace velkých celých čísel v dané bázi a převod mezi bázemi. 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 |
Systém Sage materiál ze cvičení: ipynb, html |
| 11.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 |
sekce 4.1, 4.2 a cvičení 4.6 |
-- |
| 18.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 |
Karacuba, Toom-3 a úvod do násobení matic 1. DÚ |
| 25.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 sekce 4.3, 5.1 |
-- |
| 1.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 |
Eukleidův algoritmus, složitost počítání inverzu v konečném tělese 2. DÚ |
| 8.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ů |
kapitola 8 |
-- |
| 15.11. | Přednáška není! | Základní polynomiální algoritmy (Lagrange, Garner), příklady na ČZV | |
| 22.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 |
-- |
| 29.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 |
FFT: rekurzivně a iterativně, nevýhody těles, Strassenův trik 3. DÚ |
| 6.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) | kapitola 12 |
-- |
| 13.12. | Rezultanty. Soudělnost polynomů nad Gaussovým oborem a singularita Sylvesterovy matice. 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 | kapitola 13 |
inverzní mocninné řady 4. DÚ |
| 20.12. | 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á a smolná prvočísla, smolných prvočísel a smolných hodnot je jen konečně mnoho. 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. | část kapitoly 14.1 |
-- |
| 3.1. | Modulární algoritmus na výpočet NSD celočíselných polynomů s více malými prvočísly | zbytek kapitoly 14.1 |
výpočet NSD -- PRS a modulární metoda |
| 10.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 |
-- |
Konzultace: po dohodě emailem na zuzka-at-kam.mff.cuni.cz. Je-li něco nejasné, nebojte se zeptat!
Doplňující literatura: