Komputer algebrai algoritmusok
(előadás)
| Az
előadás kódja(i) |
|
MBN017E-1 és Mv5103-1 |
| Az előadás időpontja |
|
csütörtök 14:00-16:15 |
| Az
előadás helye |
|
az előadó szobája |
Tematika
Aritmetikai műveletek: nagy egész számok, nagy pontosságú racionális számok, polinomok,
racionális törtfüggvények, hatványsorok számítógépes reprezentációjának lehetőségei.
Gyors algoritmusok aritmetikai műveletekre: Karatsuba algoritmusa, gyors hatványozás modulo n,
polinomszorzás gyors (diszkrét) Fourier-transzformációval (FFT).
Egészek és polinomok moduláris reprezentációja.
Kínai maradéktétel algoritmusok (speciális eset: Newton-interpoláció).
Polinomfaktorizáció: algoritmusok a legnagyobb közös osztó kiszámítására
(az euklideszi algoritmus javítási lehetőségei, moduláris algoritmus).
Négyzetmentes faktorizáció. Berlekamp faktorizációs algoritmusa véges test
fölötti négyzetmentes polinomokra. Hensel algoritmusa egy-, illetve
többhatározatlanú egész együtthatós polinomokra. A Lenstra-Lenstra-Lovász
algoritmus.
Egyenletrendszer-megoldás: lineáris egyenletrendszerek, a törtmentes
Gauss-elimináció. Magasabbfokú algebrai egyenletrendszerek megoldása
rezultánssal. Test fölötti többhatározatlanú polinomgyűrű ideáljai, Gröbner-bázis,
Buchberger algoritmusa. A Gröbner-bázisok alkalmazásai: kifejezések
egyszerűsítése megadott egyenlőségek felhasználásával (azaz számolás
polinomgyűrű faktorgyűrűjében), magasabbfokú algebrai egyenletrendszerek
megoldása. Szimbolikus integrálás: Risch algoritmusa.
Ajánlott irodalom
- Geddes, K. O., Czapor, S. R. és Labahn, G.: Computer algebra, Kluwer, 1992.
- Mignotte, M.: Mathematics for Computer Algebra, Springer-Verlag, 1991.
- Mishra, B.: Algorithmic Algebra, Texts and Monographs in Computer Science, Springer-Verlag, 1993.
Szeged, 2010. február 4.
Dormán Miklós