Computer Algebra - NMIB003

• Title: Počítačová algebra
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2012 to 2017
• Semester: summer
• E-Credits: 8
• Hours per week, examination: summer s.:4/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Additional information: http://www.karlin.mff.cuni.cz/~stanovsk/vyuka/palg.htm
• Guarantor: doc. RNDr. David Stanovský, Ph.D.; doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Classification: Mathematics > Algebra
• Interchangeability : NMMB204
• Is incompatible with: NMMB204
• Is interchangeable with: NMMB204

Annotation

English

Last update: T_KA (10.05.2006)

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.

Czech

Last update: T_KA (10.05.2006)

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.

Literature

English

Last update: T_KA (21.05.2009)

D. Stanovský: Počítačová algebra, http://www.karlin.mff.cuni.cz/~stanovsk/vyuka/palg.htm

F. Winkler: Polynomial Algorithms in Computer Algebra, Springer 1996.

Geddes, Czapor, Labahn: Algorithms for computer algebra, Kluwer Academic Publishers, 1992.

G. von zur Gathen: Modern computer algebra, Cambridge Univ. Press 1999

Knuth: The art of computer programming, vol. 1, Fundamental algorithms, Addison-Wesley, 3rd edition 1997.

Czech

Last update: STANOVSK/MFF.CUNI.CZ (16.05.2008)

D. Stanovský: Počítačová algebra, http://www.karlin.mff.cuni.cz/~stanovsk/vyuka/palg.htm

F. Winkler: Polynomial Algorithms in Computer Algebra, Springer 1996.

Geddes, Czapor, Labahn: Algorithms for computer algebra, Kluwer Academic Publishers, 1992.

G. von zur Gathen: Modern computer algebra, Cambridge Univ. Press 1999

Knuth: The art of computer programming, vol. 1, Fundamental algorithms, Addison-Wesley, 3rd edition 1997.

Syllabus

English

Last update: T_KA (12.05.2009)

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 multuiplication and division of polynomials.

3. Greatest common divisor: Primitive polynomials and Gauss' lemma, polynomial remainder sequences, modular algorithm.

4. Factorization of polynomials: square-free factorization, Berlekamp-Hensel's algorithm.

Czech

Last update: STANOVSK/MFF.CUNI.CZ (12.05.2009)

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ů.

3. Největší společný dělitel polynomů: Primitivní polynomy a Gaussovo lemma, posloupnosti polynomiálních zbytků, modulární algoritmus.

4. Faktorizace polynomů: bezčtvercová faktorizace, Berlekamp-Henselův algoritmus.