Groebnerbasen

Die Computer Algebra ist der Teil der Informatik, der algebraische Algorithmen entwirft, analysiert, implementiert und anwendet (Loos 1982). Im Vergleich zu anderen Algorithmen haben algebraische Algorithmen einfache formale Spezifikationen, Korrektheitsbeweise und asymptotische Rechenzeitschranken, die auf einer wohl etablierten mathematischen Theorie beruhen. Ferner können algebraische Objekte im Gegensatz zu numerischen Werten im Rechner exakt dargestellt werden, so daß beim Rechnen mit ihnen keine Rundungsfehler auftreten. Schließlich werden algebraische Algorithmen üblicherweise so implementiert, dass für Ein- und Ausgabe die bekannte symbolische Notation der Algebra verwendet wird. Bekannte Computer Algebra Systeme, die in vielen Bereichen bereits eingesetzt werden, sind unter anderen Derive, Maple und Mathematica.

Als ein äußerst wichtiges Hilfsmittel in der Computeralgebra haben sich die sogenannten Groebnerbasen herausgestellt. Eine Groebnerbasis ist eine Basis für ein Ideal in einem Polynomring, die die Eigenschaft hat, daß sie eine Reduktionsrelation induziert, die terminierend und konfluent ist. Ist diese Reduktionsrelation effektiv berechenbar, so liefert eine Groebnerbasis G eindeutige Normalformen für den Quotientenring R[x]/<G>. Dadurch werden verschiedene Entscheidungsprobleme wie das Ideal Membership Problem lösbar. Damit sind folgende Fragestellungen von Bedeutung:

Anwendungen von Groebnerbasen finden sich zum Beispiel in Beweisern für die Prädikatenlogik erster Stufe und beim automatischen Beweisen in der Geometrie.

Literatur:

Th. Becker, V. Weispfennig:
Groebner Bases
Springer 1993.
Kapitel 10 des Buchs:
Algorithms for Computer Algebra
von K. Geddes, S. Czapor und G. Labahn (Kluver, Boston, 1992).
Originalarbeiten.
Diese Vorlesung richtet sich an Studenten der Mathematik in mittleren und höheren Semestern mit Grundkenntnissen in der Algebra.