Počítačová algebra
Průběh přednášky
(17.2.) Počítačová prezentace velkých celých čísel, racionálních čísel, konečných těles
a rozšíření konečného stupně racionálních čísel.
(20.2.) Prezentace polynomů. Operace na prezentacích celých čísel, polynomů, konečných těles
a konečných rozšíření racionálních čísel. Časová složitost algoritmu. Školské algoritmy sčítání, odčítání a jednociferného násobení.
(27.2.) Školské algoritmy násobení, dělení se zbytkem a převodu mezi bázemi.
Karacubův algoritmus násobení.
(3.3.) Časová složitost obecných algoritmů rozděl a panuj. Algoritmus Toom-3. Binární mocnění.
(6.3.) Eukleidův algoritmus pro hledání největšího společného dělitele a Bezoutových koeficientů.
Časový odhad složitosti Eukleidova algoritmu.
(13.3.) Binární Eukleidův algoritmus. Časová složitost operací na tělesech prvočíselného řádu
a racionálních číslech. Časová složitost operací s polynomy. Sčítání a násobení polynomů.
(17.3.) Dělení se zbytkem a pseudodělení na polynomech. Časová složitost Eukleidova algoritmu
pro polynomy nad konečným tělesem.
(20.3.) Časová složitost operací na obecných konečných tělesech.
Výpočet NSD v polynomech nad Gaussovým oborem.
(27.3.) Výpočet NSD v celočíselných polynomů pomocí posloupnosti polynomiálních zbytků.
Lagrangeův a Garnerův algoritmus na Čínskou větu o zbytcích.
(31.3.) Časové odhady Lagrangeova a Garnerova algoritmu.
(3.4.) Zobecněná Čínská věta o zbytcích. Sdílení tajemství, (k,n)-schéma.
(10.4.) Modulární reprezentace celých čísel a polynomů,
násobení v modulární reprezentaci. Primitivní odmociny z jedné v komplexních číslech
a konečných tělesech. Diskrétní Fourierova transformace polynomů.
(14.4.) Inverzní diskrétní Fourierova transformace jako Diskrétní Fourierova transformace.
Rychlá Fourierova transformace polynomů.
(17.4.) Iterativní varianta rychlé Fourierovy transformace polynomů.
Rychlé násobení polynomů. Rychlá Fourierova transformace pro polynomy s celočíselnými koeficienty.
(24.4.) Fourierova transformace pro polynomy s celočíselnými koeficienty, Shönhagenův-Strassenův trik.
Inverzní mocninné řady. Rychlý výpočet prvních n členů inverzní mocninné řady k polynomu.
(5.5.) Rychlé dělení polynomů. Aproximace zlomků. Numerické metody na hledání kořenů rovnic.
(15.5.) Kořeny rovnic a Newtonovy metody. Gaussovo lemma a dělitelnost primitivních polynomů nad Gaussovým oborem.
(19.5.) Výpočet NSD v okruzích polynomů nad Gaussovým oborem.
Gaussova věta. Rezultanty a soudělnost polynomů nad Gaussovým oborem.
(22.5.) Šťastná a smolná prvočísla. Modulární algoritmy na výpočet NSD celočíselných polynomů s jedním prvočíslem.