Algoritmy počítačové algebry - NALG078

• Anglický název: Algorithms in Computer Algebra
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2011
• Semestr: zimní
• E-Kredity: 9
• Rozsah, examinace: zimní s.:2/2, Z [HT]; letní s.:2/0, 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: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: doc. RNDr. Jiří Tůma, DrSc.
• Třída: Algebra v informatice; Algebra v přírodních vědách
• Kategorizace předmětu: Informatika > Teoretická informatika; Matematika > Algebra
• Prerekvizity : NALG027

Anotace

čeština

Popis a analýza základních algortimů pro počítání s čísly a polynomy. Modulární aritmetika. Rychlé algoritmy. Nutným předpokladem je absolvování přednášky z algebry ve 2.roč. oboru M nebo I.

Poslední úprava: T_KA (24.05.2001)

angličtina

Description and analysis of fundamental algorithms for polynomial and number arithmetics. Modular arithmetics. Fast algorithms.

Poslední úprava: T_KA (14.05.2002)

Sylabus

čeština

Základní algoritmy pro sčítání a násobení polynomů.

Rozšířený euklidův algoritmus a jeho aplikace.

Modulární aritmetika, evaluace a interpolace, sdílení klíče.

Čínská věta o zbytku, modulární výpočet determinantu.

Algoritmy pro rychlé násobení, Karacubův algoritmus, diskrétní a rychlá Fourierova transformace.

Rychlý algoritmus pro čínskou větu o zbytcích.

Rychlý euklidův algoritmus pro polynomy.

Rychlé násobení matic.

Faktorizace polynomů nad konečnými tělesy a nad celými čísly.

Poslední úprava: T_KA (14.05.2002)

angličtina

Fundamental algorithms for addition and multiplication of numbers and polynomials.

Extended Euclidean algorithm and its applications.

Modular arithmetics, evaluation and interpolation, secret sharing.

Chinese reminder theorem, modular calculation of determinants.

Algorithms for fast multiplication, Karatsuba's algorithm, discrete and fast Fourier transform.

Fast algorithm for Chinese reminder theorem.

Fast Euclidean algorithm for polynomials.

Fast matrix multiplication.

Factorization of polynomials over finite fields and over integers.

Poslední úprava: T_KA (14.05.2002)