David Stanovský    //   

POČÍTAČOVÁ ALGEBRA (2021/22)

Předmětem kurzu jsou základní algoritmy pro aritmetiku čísel a polynomů. Přednáška má tři základní cíle:

  • ukázat si různé principy návrhu efektivních aritmetických algoritmů,
  • naučit se analyzovat složitost algoritmů,
  • naučit se implementovat matematické algoritmy.
Témata pokrývají přesně první čtyři kapitoly učebnice Stanovský, Barto: Počítačová algebra:
  1. datová reprezentace a základní aritmetické operace s čísly a polynomy, rychlé algoritmy metodou rozděl a panuj
  2. princip a výpočet modulární reprezentace čísel a polynomů (čínská věta o zbytcích, rychlá Fourierova transformace), rychlé násobení polynomů
  3. Newtonova metoda a rychlé dělení čísel a polynomů
  4. Eukleidův algoritmus a trable s růstem koeficientů

Předběžný plán / Průběžně aktualizovaný program přednášky:

přednáška skripta cvičení
30.9.
(3+1)		 Algoritmy a jejich složitost.
Počítačová reprezentace dat. 		sekce 1, 3 Systém Sage.
7.10.
(4+0)		 Školské algoritmy na artimetiku celých čísel a jejich složitost.
Metoda rozděl a panuj, Karacubovo a Toom-Cookovo násobení. 		sekce 4.1-4.3 ---
14.10.
(2+2)		 Eukleidův algoritmus: složitost, varianty. sekce 4.4-4.6 Číselné algoritmy.
21.10.
(4+0)		 Základní aritmetika polynomů. Modulární reprezentace. sekce 5,6 ---
4.11.
(2+2)		 Algoritmy na čínskou větu o zbytcích. sekce 7 Základní polynomiální algoritmy.
11.11.
(3+1)		 Diskrétní a rychlá Fourierova transformace. sekce 8, 9 FFT
18.11.
(4+0)		 Rychlé násobení a dělení polynomů. sekce 9, 10 ---
25.11.
(2+2)		 Rychlý výpočet inverzní mocninné řady, aproximace zlomků (Newtonova metoda). sekce 10.2, 10.3 násobení, dělení, zlomky
2.12.
(2+2)		 Řešení obecných rovnic: zužování intervalu a obecná Newtonova metoda. sekce 11 Newtonova metoda
9.12.
(3+1)		 Největší společný dělitel polynomů: posloupnosti polynomiálních zbytků. sekce 12 úvod do NSD polynomů
16.12.
(4+0)		 Rezultant a Sylvesterovo kritérium nesoudělnosti.
Největší společný dělitel polynomů: modulární algoritmus.		 sekce 13, 14.1 ---
6.1.
(2+2 nebo 3+1)		 Největší společný dělitel polynomů více proměnných. sekce 14.2

Web cvičení, včetně domácích úloh a podmínek zápočtu.

Konzultace: kdykoliv osobně či on-line, po předchozí domluvě emailem. Ptejte se, kdykoliv něčemu nerozumíte! K dotazům můžete využít i kvízy.

Literatura:

Zkouška TBA