Computeralgebra Systeme gewinnen immer mehr an Bedeutung bei der Anwendung mathematischer Methoden in Naturwissenschaft und Technik. Solche Systeme erlauben umfangreiche symbolische Berechnungen und, im Gegensatz zur Numerik, auch exakte Berechnungen. Es wird eine Einführung in die mathematischen und algorithmischen Konzepte gegeben werden, welche solchen Computeralgebra Systemen zugrunde liegen. Dabei stehen die folgenden drei Aspekte im Vordergrund: Algorithmische Ideen, Korrektheitsbeweise für Algorithmen, (asymptotische) Laufzeitanalysen. Neben theoretischen Aufgaben wird im Rahmen der Übungen der Einsatz von CA-Systemen anhand kleinerer Projekte trainiert werden. Zur Begleitung der Vorlesung empfehle ich besonders von zur Gathen und Gerhard's schöne und umfassende Darstellung.

Inhalt

• Fundamentale Algorithmen (Multiplikation von Polynomen und ganzen Zahlen, schnelle Fouriertransformation, Newtonverfahren)
• Euklidscher Algorithmus
• Chinesischer Restsatz, Interpolation, modulare Algorithmen
• Subresultantentheorie
• Faktorisierung von Polynomen über endlichen Körpern
• Hensel Lifting und Faktorisierung von Polynomen in Z[X] und Q[X]
• Kurze Vektoren in Gittern (LLL-Algorithmus)

• Lineare Algebra (Wiedeman's Algorithmus)
• Primzahltests
• Faktorisierung ganzer Zahlen
• Gröbner Basen

• Akritas. Elements of computer algebra. Wiley, 1989.
• Bürgisser, Clausen, Shokrollahi. Algebraic Complexity Theory. Springer 1997.
• Cohen, Cuypers, Sterk (Editors). Some tapas of computer algebra. Springer, 1999.
• Davenport, Siret, Tournier. Computer algebra: systems and algorithms for algebraic computation. Acad. Press, 1993.
• von zur Gathen, Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.
• Geddes, Czapor, Labahn. Algorithms for Computer Algebra. Kluwer, 1992.
• Grabmeier, Kaltofen, Weispfenning. Handbook of computer-algebra. Springer, 2001.
• Mignotte. Mathematics for computer algebra. Springer, 1992.