Počítačová algebra LS 2018/19

Rozvrh

Čt, 12:20 – 13:50, přednáška v K8

Pá (liché výukové týdny), 10:40 – 12:10, přednáska v K11

Pá (sudé výukové týdny), 10:40 – 12:10, cvičení v K11; vede Jiří Pavlů

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).

Konzultace

Konzultace po dohodě e-mailem na kazda@karlin.mff.cuni.cz.

Program přednášek (změna programu vyhrazena)

21.2.2019 Motivace a cíle přednášky. Asymptotické odhady a časová složitost v počtu základních operací.
22.2.2019 Reprezentace velkých celých čísel v dané bázi, reprezentace racionálních čísel a konečných těles. Reprezentace polynomů.
28.2.2019 Školské algoritmy pro aritmetiku s celými čísly a polynomy. Č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.
7.3.2019 Mocniny. Eukleidův algoritmus v ℤ
8.3.2019 Cvičení implementace algoritmů v systému Sage
14.3.2019 Složitost Eukleidova algoritmu v ℤ. Operace v ℚ a ℤ_p
21.3.2019 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.
22.3.2019 Čínská věta o zbytcích pro celá čísla a Lagrangeova interpolace. Zobecněná čínská věta o zbytcích. Modulární reprezentace a násobení celých čísel a polynomů. Lagrangeův algoritmus pro modulární reprezentaci.
28.3.2019 Časové odhady Lagrangeova algoritmu. Garnerův algoritmus.
4.4.2019 Správnost a časové odhady Garnerova algoritmu. Diskrétní Fourierova transformace.
5.4.2019 Algoritmus pro rychlou Fourierovu transformaci.
11.4.2019 Časový odhad algoritmu pro FFT. Rychlé násobení polynomů pomocí rychlé Fourierovy transformace. Existence a konstrukce primitivních n-tých mocnin.
18.4.2019 Shönhagen-Strassenův trik, princip rychlého násobení čísel pomocí FFT. Mocninné řady a inverzní mocninné řady. Rychlé dělení polynomů.
~~19.4.2019~~ Velikonoce
25.4.2019 Rychlý výpočet prvních n členů inverzní mocninné řady. Rychlé dělení polynomů. Aproximace zlomků. Iterativní metody hledání kořene rovnice f(x)=0, řád konvergence metody.
2.5.2019 Newtonova metoda. Newtonova metoda je kvadratická pro hezkou funkci.
3.5.2019 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).
8.5.2019 Primitivní, redukovaná a subrezultantová PRS. Čtyři různé pohledy na soudělnost polynomů f,g.
9.5.2019 Rezultanty, Sylvesterovo kritérium. Výpočet rezultantů pomocí kořenů.
16.5.2019 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.
23.5.2019 NSD celočíselných polynomů pomocí ČZV (hlavní myšlenky). NSD polynomů více neurčitých. Závěr.

Program cvičení

1.3.2019 Časová složitost školských algoritmů a algoritmu Toom-3.
15.3.2019 Odčítání v ℤ, binární Eukleidův algoritmus.
29.3.2019 Počítání v konečných tělesech a rozšířeních Q, ČZV
12.4.2019 Fourierova transformace. Iterativní varianta rychlé Fourierovy transformace polynomů
26.4.2019 Dělení, aproximace zlomků.
17.5.2019 NSD polynomů, posloupnosti polynomiálních zbytků (PRS). Rezultanty.
24.5.2019 NSD polynomů více proměnných.

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 ℤ
Toom-3 pro násobení v ℤ
Naivní mocnění v ℤ
Binární mocnění v ℤ
Eukleidův algoritmus v ℤ
Binární 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
Násobení polynomů pomocí Karacubova algoritmu
Hornerovo schéma pro vyhodnocení polynomu v bodě
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
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, Karolinum, 2011.

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)

Taháky pro Sage