Sylabus
1. Reprezentace dat, základní operace s čísly a polynomy, Karacubův a Eukleidův algoritmus.
2. Modulární reprezentace, algoritmická verze Čínské věty o zbytcích. Rychlá Fourierova transformace, její využití pro rychlé násobení polynomů.
3. Newtonova metoda a rychlé dělení polynomů.
4. Největší společný dělitel polynomů: Primitivní polynomy a Gaussovo lemma, posloupnosti polynomiálních zbytků, modulární algoritmus.
Anotace
Povinný předmět bakalářského oboru MIT. Obsahem přednášky jsou algoritmy používané v počítačových systémech pro symbolickou manipulaci.
Přednáška vychází z analýzy nejjednodušších algebraických algoritmů a ukazuje, jak lze použít teoretické poznatky na jejich zefektivnění. Hlavní důraz je kladen na práci s polynomy, jejichž koeficienty jsou buď celá a racionální čísla, nebo to jsou prvky konečných těles.