Dr. rer. nat.

Algorithmische Mathematik und Computeralgebrasysteme

Computeralgebrasysteme (CAS) stellen eine wichtige Verbindung zwischen der reinen Mathematik und der (theoretischen) Informatik dar. Vor allem können CAS Berechnungen durchführen, die ein Mensch aufgrund des enormen Aufwandes niemals in einer vernünftigen Zeit bewältigen könnte. Deswegen sind CAS in den modernen Wissenschaften, insbesondere in der reinen Mathematik (Numerik, Gruppentheorie, …) unersetzlich.

Fragen wie

  • Ist das Integral einer gegebenen elementaren Funktion wieder durch elementare Funktion darstellbar?
  • Ist die Lösung einer gegebenen Differentialgleichung in kompakter Form darstellbar?
  • Sind die Wurzeln eines Polynoms durch Radikale (als Wurzelausdrücke) darstellbar?

können heute in einer recht vernünftigen Zeit durch CAS beantwortet werden. Die erste (und partiell auch die zweite) Frage können mit Hilfe des Risch-Algorithmus beantwortet werden. Der Risch-Algorithmus ist ein Algorithmus, welchem als Eingabe eine elementare Funktion f(x) übergeben wird und der dann entscheidet, ob f(x) eine elementare Stammfunktion F(x) besitzt, und gegebenenfalls wird F(x) explizit berechnet. Zwar liefert der Risch-Algorithmus in der Tat eine Stammfunktion F, falls diese existiert, bei komplizierteren Funktionen allerdings kann der benötigte Rechenaufwand (Komplexität der auftretenden Terme, Anzahl der Rekursionen, Berechnung entsprechender Resultanten, …) das menschliche Leistungsvermögen hoffnungslos übersteigen. Hier sind dann CASe gefragt.

An dieser Stelle müssen, der Vollständigkeit halber, ein paar wichtige Bemerkungen über den Risch-Algorithmus gemacht werden. Zunächst einmal ist der Risch-Algorithmus im Allgemeinen nur ein Semi-Algorithmus, denn in einem bestimmten Schritt muss man entscheiden, ob ein gegebener Ausdruck identisch 0 ist, und dies ist im Allgemeinen leider ein unentscheidbares Problem. Ist f(x) dagegen eine transzendente Funktion (also beispielsweise ex2, ln(x+e), x/(sin(x-ln(x))+ex · ln(x)), nicht aber f(x) = e(ln(x)/2), denn f lässt sich als f(x) = x1/2 = √x schreiben), so ist der Risch-Algorithmus in der Tat ein echter Algorithmus.

Eine weitere außergewöhnliche Anwendung der algorithmischen Mathematik ist das sogenannte automated theorem prooving. Mit der Entwicklung der Gröbnerbasen wurde nämlich gleichzeitig die Realisierung einer weiteren, viel interessanteren Idee ermöglicht: das „maschinelle“ Beweisen mathematischer (oft geometrischer) Aussagen. Die Idee dahinter ist, dass man mathematische Aussagen manchmal in die kommutative Algebra übersetzen kann und die Aussage wird auf das Ideal Membership Problem, also auf das Problem der Zugehörigkeit eines Polynoms zu einem Ideal, reduziert.

Wir illustrieren dieses Prinzip kurz an einem einfachen und bekannten Satz aus der Geometrie: In einem Dreieck schneiden sich die drei Mittelsenkrechten in einem Punkt. Obwohl dieses Problem noch „per Hand“ gelöst werden kann, erweisen sich automatische Beweise etwas komplizierterer Sätze aus der Geometrie (wie etwa dem Schmetterlingssatz) als viel aufwändiger. Im Folgenden verwenden wir Notationen wie in der untenstehenden Abbildung.

Mittelsenkrechten

Zunächst einmal können wir die Ausgangssituation entscheidend vereinfachen: wir legen das Dreieck in ein Koordinatensystem derart, dass die Punkte A, B und C die folgenden Koordinaten tragen: A = (0, 0), B = (c, 0) und C = (a, b). Seien O1 = (x1, y1) der Schnittpunkt der Mittelsenkrechten zu den Strecken AB und BC und O2 = (x2, y2) der Schnittpunkt der Mittelsenkrechten zu den Strecken AB und AC. Dies führt uns zu den folgenden Gleichungen:

p1 = x1 – c/2 = 0

p2 = (c-a)/b·x1 – y1 + (a2+b2-c2)/(2b) = 0.

Für den Schnittpunkt O2 erhalten wir durch analoge Überlegungen die folgenden Gleichungen:

p‘1 = x2 – c/2 = 0

p3 = a/b·x2 – y2 – (a2+b2)/(2b) = 0.

Wir betrachten nun das Ideal I = (p1, p2, p‘1, p3) ⊆ ℝ[x1, y1, x2, y2], welches von unseren vier Polynomen erzeugt wird. Nun kann (s. unten) gezeigt werden, dass die Polynome

f = x1 – x2 und g = y1 – y2

ebenfalls im Ideal liegen (an dieser Stelle wird das Ideal Membership Problem gelöst), d.h. sie erfüllen ebenfalls die Relation f = 0 und g = 0. Somit gilt (x1, y1) = (x2, y2) und daher sind die Punkte O1 und O2 identisch. Der Satz ist damit bewiesen.

Um das Ideal Membership Problem zu lösen, muss zu einem Ideal I ⊆ ℝ[x1, x2, …, xn] eine sogenannte Gröbnerbasis berechnet werden. Der Aufwand für die Berechnung einer Gröbnerbasis wächst, in Abhängigkeit von der Anzahl der Variablen n und den Graden der Polynome in den Erzeugern {f1(x1, …, xn), …, fk(x1, …, xn)} von I, allerdings rasant. Deswegen sind gerade für die Berechnung von Gröbnerbasen und ähnlichen Problemen in der (kommutativen) Algebra die Verwendung eines CAS unentbehrlich.