PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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.
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 -
Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (05.06.2019)
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.
Podmínky zakončení předmětu
Poslední úprava: RNDr. Zuzana Patáková, Ph.D. (19.10.2023)

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/

Literatura -
Poslední úprava: 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.

Požadavky ke zkoušce
Poslední úprava: 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.

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

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.

 
Univerzita Karlova | Informační systém UK