Seminar über Computeralgebra SS 2002

Prof. Dr. Peter Bürgisser, Martin Lotz
 

Aufbauend auf Inhalten der Vorlesung Computeralgebra I und parallel zur Vorlesung Computeralgebra II sollen einige Themen vertieft und in verschiedene Richtungen erweitert werden. Im Mittelpunkt vieler Themen stehen angewandte Aspekte der algorithmischen algebraischen Geometrie.

Kriterium für den Scheinerwerb ist ein Vortrag mit Ausarbeitung.

Vorläufige Daten:
Jeweils Mi 09:15-10:45 im Raum E2.304
Beginn (Vorbesprechung): 17. April

Themen

  • BCH Codes
    8. Mai, Tobias Jakob
    Ausarbeitung: [ pdf ]
    In der Codierungstheorie geht es um die Minimierung von Fehlern bei der Informationsübertragung. Eine populäre Klasse von Codes sind die sog. BCH Codes. Bei deren Konstruktion und Decodierung spielen verschiedene Aspekte der Computeralgebra eine Rolle, z.B. Faktorisierung von Kreisteilungspolynomen und Pade-Approximation.
    Literatur: Kapitel 7 und 14.10 aus [MCA].
  • Einführung in Gröbner Basen
    15. Mai, Anita Gubik
    Gröbner Basen sind ein zentraler Begriff der algorithmischen algebraischen Geometrie. Sie ermöglichen es, Algorithmen der linearen Algebra auf Polynomringe in mehreren Veränderlichen zu erweitern. Dieses Thema wird ausführlicher in der Vorlesung CA II behandelt; dieser Vortrag dient der Vorbereitung der folgenden Vorträge. Themen: Monomiale Ordnungen, Division mit Rest in K[X_1,...,X_n], Buchberger Algorithmus.
    Literatur: Kapitel 21 aus [MCA], Kapitel 2 aus [IVA].
  • Anwendungen in der Robotik
    22. Mai, Markus Hufnagel
    29. Mai, Jennyfer Kaminski
    Gewisse kinematische Probleme (z.B. Bewegung eines Roboterarms) können algebraisch-geometrisch formuliert und mit Hilfe von Gröbner Basen gelöst werden.
    Literatur: Kapitel 6.1-3 aus [IVA], Projekt 3 aus [Tapas].
  • Automatisches Beweisen geometrischer Sätze
    5. Juni, Markus Diekämper
    Ausarbeitung: [ ps | pdf ]
    Mit Methoden der algorithmischen algebraischen Geometrie können Sätze aus der klassischen Geometrie (z.B. Satz von Pappus) automatisch verifiziert werden.
    Literatur: Kapitel 6.4 aus [IVA], Projekt 1 aus [Tapas].
  • Invariantentheorie endlicher Gruppen
    12. Juni, Andreas Meyer
    19. Juni, Andreas Meyer
    Die Invariantentheorie ist ein klassisches Thema der Mathematik, das durch algorithmische Fragestellungen neu belebt wurde. Es geht darum, die Invarianten unter der Aktion einer (endlichen) Gruppe möglichst gut zu verstehen. Für die Berechnung von Invarianten kann man Gröbner Basen gewinnbringend verwenden.
    Literatur: Kapitel 1 aus [Sturmfels], Kapitel 7 aus [IVA].
  • Multivariate Resultanten
    26. Juni, Sascha Nickel
    Resultanten beschreiben, ob ein System polynomialer Gleichungen lösbar ist. Es soll die aus der Vorlesung bekannte Situation univariater Polynome auf mehrere Variable übertragen werden. Eine interessante Erweiterung bilden die Resultanten dünn besetzter Polynome. Ein klassischer Anwendungsbereich ist die Eliminationstheorie.
    Literatur: Kapitel 2 aus [CAG], Kapitel 3.2 und 7.2 aus [UAG].
  • Ganzzahlige Optimierung mit Gröbner Basen
    3. Juli, Eduard Wiebe
    Bei der ganzzahligen Optimierung geht es darum, ganzzahlige Lösungen von linearen Optimierungsproblemen zu finden. Dafür können Varianten des Buchberger Algorithmus eingesetzt werden.
    Literatur: Kapitel 7 aus [Tapas], Kapitel 8 aus [UAG].
  • Faktorisierung von Polynomen über F_q:
    10. Juli, László Germán
    In diesem Vortrag sollen die Algorithmen von Berlekamp zur Faktorisierung von Polynomen über endlichen Körpern besprochen werden. Es handelt sich hier um die ältesten bekannten effizienten Faktorisierungsalgorithmen (1967,1970). Sie basieren auf Methoden der linearen Algebra.
    Literatur: Kapitel 14.8 aus [MCA], Kap 4.1 aus [Tapas].
Eigene Vorschläge zu Vortragsthemen sind auch willkommen. Der Vortrag über Gröbner Basen ist Voraussetzung für die im Anschluss genannten; sonst gibt es keine Abhängigkeiten.
Bei Interesse oder Rückfragen bitte Mail an Martin Lotz.

Literatur

  • [CAG] D. Cox, B. Sturmfels (eds.), Applications of Computational Algebraic Geometry, AMS 1997.
  • [IVA] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, Springer 1996.
  • [MCA] J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge 1999.
  • [Sturmfels] B. Sturmfels, Algorithms in Invariant Theory, Springer 1993.
  • [Tapas] A.M. Cohen, H. Cuypers, H.Sterk (eds.), Some Tapas of Computer Algebra, Springer 1999.
  • [UAG] D. Cox, J. Little, D. O'Shea, Using Algebraic Geometry, Springer 1998.