|
|
|
||
|
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.
Poslední úprava: Kaplický Petr, doc. Mgr., Ph.D. (05.06.2019)
|
|
||
|
Zápočet z předmětu je nutnou podmínkou účasti u zkoušky.
Zápočet student získá za odevzdání zadaných domácích úkolů. Podrobnosti viz stránka cvičení: https://www.karlin.mff.cuni.cz/~slavika/wp/?page_id=174
Povaha kontroly studia pro získání zápočtu vylučuje možnost opakování této kontroly. Poslední úprava: Patáková Zuzana, RNDr., Ph.D. (09.10.2024)
|
|
||
|
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. Poslední úprava: Kaplický Petr, doc. Mgr., Ph.D. (05.06.2019)
|
|
||
|
Požadavky u zkoušky korespondují se sylabem přednášky a budou uplatňovány v rozsahu, ve kterém bylo téma prezentováno na přednášce. Zkouška je písemná s ústní debatou nad výsledky. Zkoušený dostane dvě otázky, na které si písemně během jedné až dvou hodin připraví odpovědi. První otázka bude vyžadovat formulaci a důkaz správnosti algoritmu, případně formulování a důkaz některého ze souvisejících teoretických problémů, druhá otázka se zaměří na odhad časové složitosti (jiného) algoritmu případně také simulaci chodu algoritmu na konkrétním vstupu. Poslední úprava: Patáková Zuzana, RNDr., Ph.D. (09.10.2024)
|
|
||
|
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.
Poslední úprava: Kaplický Petr, doc. Mgr., Ph.D. (05.06.2019)
|