Počítačová algebra

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. Přednáška bude probíhat formou kontrolované četby skript Počítačová algebra.

Anotace

Povinný předmět bakalářského oboru MMIB. 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.