Počítačová algebra LS 2019/20
Rozvrh
Pá, 10:40 – 12:10, přednáška v K11
Pá (liché výukové týdny), 12:20 – 13:50, přednáška v K11
Pá (sudé výukové týdny), 12:20 – 13:50, cvičení v K11; vede Michal Maršálek e-mail: marsalemi@labk10.karlin.mff.cuni.cz
Podmínky pro zápočet
Odevzdat aspoň 5 (z 6) domácích úkolů tak, aby fungovaly. Domácí úkoly budeme postupně zveřejňovat v průběhu semestru. Na typický úkol budete mít 3 týdny času a 2 opravné pokusy (s termínem odevzdání po 1 týdnu).
Aktuální domácí úkoly: Implementace základní aritmetiky (viz e-mail ze SISu). Řádný termín: 20. března 2020
Inverze hashovací funkce PM16 (viz e-mail ze SISu). Řádný termín: 3. dubna 2020
Kódování a dekódování Reed-Solomonova kódu pomocí FFT (viz e-mail) Řádný termín: 17. dubna 2020
Newtonova metoda (dvě varianty, viz e-mail) Řádný termín 1. května 2020
Soudělnost polynomů nad celými čísly pomocí rezultantu (viz e-mail) Řádný termín 15. května 2020
Modulární algoritmus pro NSD polynomů (viz e-mail) Řádný termín 5. června 2020
Konzultace
Konzultace po dohodě e-mailem na kazda@karlin.mff.cuni.cz.
Program přednášek (změna programu vyhrazena)
- 21.2.2020 Motivace a cíle přednášky. Asymptotické odhady a časová složitost v počtu základních operací. Reprezentace velkých celých čísel v dané bázi, reprezentace racionálních čísel a konečných těles. Reprezentace polynomů. Školské algoritmy pro aritmetiku s celými čísly a polynomy. Školský algoritmus převodu mezi bázemi.
- 28.2.2020 Časová složitost školských algoritmů převodu mezi bázemi. Násobení v ℤ pomocí metody rozděl a panuj. Karacubův algoritmus a jeho časová složitost. Mocniny, binární mocnění. Eukleidův algoritmus v ℤ
- 6.3.2020 Složitost Eukleidova algoritmu v ℤ. Operace v ℚ a ℤp. Operace v konečných tělesech. Základní operace s polynomy nad ℤ a ℤp. Eukleidův algoritmus pro polynomy. Aritmetika v konečných tělesech a v rozšířeních racionálních čísel. Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace. Modulární reprezentace a násobení celých čísel a polynomů. Lagrangeův algoritmus pro modulární reprezentaci.
- 13.3.2020 Časové odhady Lagrangeova algoritmu. Garnerův algoritmus. Správnost a časové odhady Garnerova algoritmu. Definice a motivace diskrétní Fourierovy transformace.
- 20.3.2020 Algoritmus pro rychlou Fourierovu transformaci. Časový odhad algoritmu pro FFT. Rychlé násobení polynomů pomocí rychlé Fourierovy transformace. Existence a konstrukce primitivních n-tých mocnin. , princip rychlého násobení čísel pomocí FFT.
- 27.3.2020 Shönhagen-Strassenův trik. Mocninné řady a inverzní mocninné řady. Rychlé dělení polynomů. Rychlý výpočet prvních n členů inverzní mocninné řady.
- 3.4.2020 Rychlé dělení polynomů. Aproximace zlomků. Iterativní metody hledání kořene rovnice f(x)=0, řád konvergence metody. Newtonova metoda. Newtonova metoda je kvadratická pro hezkou funkci.
- 17.4.2020 Výpočet NSD v ℤ[x]. Potíže s nárůstem koeficientů při použití Euklidova algoritmu. Obsah a primitivní část polynomu nad nad gaussovským oborem. Výpočet NSD v polynomech nad gaussovským oborem. Výpočet NSD pomocí posloupnosti polynomiálních zbytků (PRS). Primitivní, redukovaná a subrezultantová PRS. Čtyři různé pohledy na soudělnost polynomů f,g. Rezultant. Slajdy z přednášky Sage notebook s funkcemi na gcd
- 24.4.2020 Sylvesterovo kritérium. Výpočet rezultantů pomocí kořenů. Souvislost se stupni polynomů v Euklidově algoritmu slajdy
- 15.5.2020 Modulární algoritmus na výpočet NSD. Vztah NSD(f, g) v okruhu ℤ[x] a NSD(f mod p, g mod p) v okruhu ℤp[x]. Problém vedoucího koeficientu. Použitelná, smolná a šťastná prvočísla. Smolných prvočísel je jen konečně mnoho. Landau-Mignottova mez. Algoritmus na výpočet NSD celočíselných polynomů s jedním velkým prvočíslem. slajdy
- 22.5.2020 NSD celočíselných polynomů pomocí ČZV (hlavní myšlenky). NSD polynomů více neurčitých. Závěr. slajdy
Program cvičení
- 28.2.2020 Základy programování v Pythonu a Sage úlohy ze cvičení
- 13.3.2020 Odhady časové složitosti algoritmů, Toom-3 úlohy ze cvičení
- 27.3.2020 Fourierova transformace, rychlé násobení Zadání cvičení Řešení cvičení (PDF) Řešení cvičení (video)
- 24.4.2020 Rezultanty, pseudodělení Zadání Řešení
- 22.5.2020 Modulární Euklidův algoritmus Zadání Řešení
Algoritmy, co jsme probrali
- Školské sčítání v ℤ
- Školské násobení v ℤ
- Školské dělení se zbytkem v ℤ
- Školský převod mezi bázemi (pro ℤ)
- Karacubův algoritmus pro násobení v ℤ
- Naivní mocnění v ℤ
- Binární mocnění v ℤ
- Eukleidův algoritmus v ℤ
- Sčítání, odčítání, násobení, inverze v racionálních číslech
- Scítání, odčítání, násobení, inverz v ℤp
- Školské scítání, odčítání, násobení, mod a div v R[x], kde R je vhodný okruh
- Sčítání, odčítání, inverz v konečných tělesech (zadaných pomocí prvočísla p a minimálního polynomu stupně k)
- Sčítání, odčítání, inverz v ℚ(q), kde q je algebraické komplexní číslo
- Princip modulárního násobení
- Lagrangeův algoritmus na převod z modulární reprezentace
- Garnerův algoritmus na převod z modulární reprezentace
- Násobení polynomů pomocí Karacubova algoritmu
- Naivní Fourierova transformace
- Rychlá Fourierova transformace (FFT)
- Násobení polynomů pomocí FFT, pokud máme primitivní 2^k-tou odmocninu z 1
- Modulární násobení v ℤ[x], pokud známe vhodné FFT-prvočíslo
- Modulární násobení v ℤ[x], kde počítáme modulo 2^(2^(k-1)u)+1
- Princip rychlého násobení v ℤ
- Výpočet inverzní mocninné řady z definice
- Dělení polynomů nad tělesem, pokud umíme spočíst inverzní mocninné řady
- Výpočet prvních n členů inverzní mocninné řady
- Aproximace čísla 1/a (s asymptoticky kvadratickou konvergencí)
- Newtonova metoda pro přibližný výpočet u, že f(u)=0
- Výpočet NSD pro (primitivní) polynomy nad gaussovským okruhem R pomocí PRS (Euklidovská, Primitivní, Redukovaná, Subrezultantová)
Literatura
L. Barto, D. Stanovský: Počítačová algebra, MatfyzPress, 2017.
V. Shoup: A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2nd edition 2008.
F. Winkler: Polynomial Algorithms in Computer Algebra, Springer 1996.
K. Geddes, S. Czapor, G. Labahn: Algorithms for computer algebra, Kluwer Academic Publishers, 1992.
G. von zur Gathen: Modern computer algebra, Cambridge Univ. Press 1999
D. Knuth: The art of computer programming, vol. 1, Fundamental algorithms, Addison-Wesley, 3rd edition 1997.
Odkazy
Balík Sage
Notebookové prostředí Jupyter
Balík Singular
Knihovna MPIR (součást systému Sage)
Knihovna NTL pro C++ (lze k ní přistupovat ze Sage)
Úvod do Pythonu (s díky za doporučení Jakubovi Bulínovi)