English website

Hörerkreis:
Masterstudiengang Informatik (nach dem Bachelor)

Vorlesungstermin: Mi 09:30 Uhr - 12:15 Uhr, HS5 + RZ3
    (Die Veranstaltung beginnt jeweils in HS5. Für praktische Übungen gehen wir in RZ3)

Computer-Algebra beschäftigt sich mit symbolischem Rechnen. So werden z.B. Funktionen exakt differenziert und integriert, ihre Nullstellen exakt berechnet. Polynome werden in ihre irreduziblen Faktoren zerlegt. Es kann mit beliebig großen Zahlen exakt gerechnet werden.

Computer-Algebra-Systeme sind ferner in der Lage, die symbolisch ausgerechneten Werte in Koordinatensystemen grafisch darzustellen und so z.B. komplette Kurvendiskussionen vorzunehmen, wie Sie es in der Schule noch per Hand durchführen mussten.

Durch die exakte Weiterverarbeitung von Termen können auch Vereinfachungen erkannt werden (Kürzen, Zusammenfassen, Faktorisierungen) und so Ungenauigkeiten vermieden werden, wie sie durch das zu frühe Einsetzen von approximierten Zahlenwerten entstehen würden.

In diesem Sinne liefert die Computer-Algebra eine exakte Alternative zur numerischen Datenverarbeitung. Während die Numerik auf analytischen Konvergenzuntersuchungen von Folgen und Reihen beruht, basiert die Computer-Algebra mehr auf den Methoden der Diskreten Mathematik und Algorithmik.

In dieser Vorlesung wird der inhaltliche Schwerpunkt auf das exakte Rechnen mit Zahlen und Polynomen, auch in endlichen Körpern, gelegt. Wir werden auch Anwendungen in der Kryptographie diskutieren. Dafür spielt vor allem auch die Faktorisierung von Zahlen und Polynomen eine große Rolle, mit der wir uns eingehend beschäftigen werden. Über das in der Linearen Algebra vermittelte Lösen von linearen Gleichungssystemen hinaus beschäftigen wir uns auch mit dem Lösen von polynomialen Gleichungssystemen.

Neben einer theoretischen Behandlung wird auch Einblick in die Praxis gegeben, in dem wir die Verfahren Computer-Algebra-Systemen ausprobieren. In diesem Semester werden wir das im letzten Jahr verwendete open-source-System Maxima mit dem kommerziellen System Mupad vergleichen. Mupad ist seit kurzem in die ursprünglich rein numerische Mathematiksoftware Matlab eingebettet. Die wichtigsten im Internet erhältlichen Tutorials für diese beiden Werkzeuge sowie eine Installationsroutine von Maxima stehen auch auf dem Handout-Server (nur für Hochschulangehörige zugänglich).

Der Leitfaden wird das Buch von Köpf sein, das wir im Wesentlichen in der angegebenen Reihenfolge durcharbeiten werden. Einige der angesprochenen Themen sind bereits aus dem Bachelorstudium bekannt (Diskrete Mathematik) und werden daher nur kurz wiederholt. Andere Themen bedürfen einer ausführlicheren Behandlung. Hierfür werden wir auch Anleihen in den Büchern von Kaplan und von zur Gathen / Gerhard machen. Die Themen ab Kap. 9 in Köpf werden aus Zeitgründen nicht mehr behandelt. Sie beschäftigen sich hauptsächlich mit symbolischer Lösung von Aufgaben aus der Analysis.

Ein großer Teil des zu behandelnden Inhalts wird durch die Vorträge und Ausarbeitungen des Seminars zur Computeralgebra aus dem WS 2007/2008 abgedeckt. Ich werde die Vorträge, wenn sie geeignet sind, in der Vorlesung vorstellen und durch eigene Ausführungen an der Tafel ergänzen. Einige Unterlagen werden noch modifiziert und ergänzt werden.

Es wird in keinem Fall von mir komplett ausgearbeitete Foliensätze geben, sondern nur eine Übersicht über die zu behandelnden Themen (analog zu den ersten Folien meiner Vorlesung Diskrete Mathematik) sowie die verwendeten Materialien. Details werden in der Regel an der Tafel vorgestellt.

Im Folgenden wird eine grobe Gliederung der Vorlesung gegeben, die im Laufe der Vorlesung noch verfeinert wird. Die angegebenen Kapitel werden zeitnah (kurz vor oder nach der Vorlesung) mit dieser Übersicht verlinkt.

Für den praktischen Teil werden in unregelmäßigen Abständen Übungsaufgaben gestellt. Die Aufgaben, eventuelle Demolösungen sowie vertiefende Artikel werden auf den Handout-Server (nur für Studierende der FH Wedel zugänglich) gestellt.

1) Einführung in das Computer-Algebra-System Maxima (08.04.)

2) Ganzzahlarithmetik
    2.1) Zahlendarstellung, Vergleiche, Addition, Multipikation (15.04.) 
    2.2) Division, Rationale Arithmetik (22.04.)

3) Modulare Arithmetik
    3.1) Berechnung modularer Funktionen (29.04.)
    3.2) Anwendungen in der Kryptographie (06.05.)
    3.3) Primzahltest mit Hilfe modularer Arithmetik (wird zu einem späteren Zeitpunkt nachgeholt)

4) Polynomarithmetik
    4.1) Addition und Multiplikation (13.05.)
    4.2) Division und einfache Faktorisierung (27.05.)

5) Polynomiale Gleichungssysteme
    5.1) Algebraische Grundlagen (03.06., Foliensatz aktualisiert am 04.06.)
    5.2) Lösung über Resultanten (wird begonnen am 10.06., beendet am 17.06.)

6) Effiziente Faktorisierung von Polynomen 
    6.1) Faktorisierung in Z_p[x] und GF(q)[x] (geändert am 07.07.)
    6.2) Faktorisierung in Q[x] über den Umweg Z_p[x]

Zusammenfassung der Vorlesung und Klausurabgrenzung

Joachim von zur Gathen / Jürgen Gerhard: Modern Computer Algebra, Cambridge University Press 2003 (2nd ed.), ISBN 0-521-82646-2

Michael Kaplan: Computeralgebra, Springer 2005, ISBN 3-540-21379-1

Donald Knuth: The Art of Computer Programming, vol. 1,2,3,
Addison Wesley 1997, ISBN 0-201-89683-4,  0-201-89684-2, 0-201-89685-0

Wolfram Koepf: Computeralgebra, Springer 2006, ISBN 3-540-29894-0

Zum Wiederholen und Nacharbeiten von algebraischen Grundlagen: