|
|
|
||
Last update: doc. Mgr. Petr Kaplický, Ph.D. (05.06.2019)
|
|
||
Last update: doc. RNDr. David Stanovský, Ph.D. (07.10.2021)
Zápočet student získá za odevzdání zadaných domácích úkolů. Podrobnosti viz https://www2.karlin.mff.cuni.cz/~raskam/vyuka/pocalg.html |
|
||
Last update: doc. Mgr. Petr Kaplický, Ph.D. (05.06.2019)
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. |
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (06.11.2022)
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 (seznamu bude určitě aktualizován), 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. |
|
||
Last update: doc. Mgr. Petr Kaplický, Ph.D. (05.06.2019)
1. Data representation, basic operations with numbers and polynomials, Karacuba's and extended Euclid's algorithm. 2. Modular representation, algorithms for Chinese Remainder Theorem. Fast Fourier transform, fast multiplication of polynomials. 3. Newton's method and fast division of polynomials. 4. Greatest common divisor: Primitive polynomials and Gauss' lemma, polynomial remainder sequences, modular algorithm.
|