Počítačová algebra - NMMB309

• Anglický název: Computer Algebra
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:3/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://www.karlin.mff.cuni.cz/~patakova/vyuka/23-24/
• Garant: RNDr. Zuzana Patáková, Ph.D.
• Vyučující: RNDr. Zuzana Patáková, Ph.D.; RNDr. Alexander Slávik, Ph.D.
• Třída: M Bc. MMIB; M Bc. MMIB > Povinně volitelné; M Bc. MMIB > 2. ročník; M Bc. MMIT; M Bc. MMIT > Povinně volitelné
• Kategorizace předmětu: Matematika > Algebra
• Neslučitelnost : NMIB003, NMMB204
• Záměnnost : NMIB003
• Je neslučitelnost pro: NMMB204
• Je záměnnost pro: NMMB204

Anotace

čeština

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)

angličtina

Required course for bachelor's program in Information security. The course contains description of algorithms used in computer systems for symbolic manipulation. It begins with analysis of the simplest algebraic algorithms and shows how to use theoretic results for their improvement. Algorithms for polynomials over integers, rational numbers or finite fields are emphasized.

Poslední úprava: Kaplický Petr, doc. Mgr., Ph.D. (05.06.2019)

Podmínky zakončení předmětu

Zápočet student získá za odevzdání zadaných domácích úkolů. Podrobnosti viz stránka předmětu: https://www.karlin.mff.cuni.cz/~patakova/vyuka/23-24/

Poslední úprava: Patáková Zuzana, RNDr., Ph.D. (19.10.2023)

Literatura

čeština

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 ke zkoušce

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (06.11.2022)

Sylabus

čeština

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)

angličtina

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.

Poslední úprava: Kaplický Petr, doc. Mgr., Ph.D. (05.06.2019)