English website

Hörerkreis:
Masterstudiengang Informatik (nach dem Bachelor)

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

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 in Computer-Algebra-Systemen ausprobieren. Wir werden sowohl mit dem open-source-System Maxima als auch mit dem kommerziellen System Mupad arbeiten. 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 die Gliederung der Vorlesung gegeben sowie die dazugehörigen Übersichtsfolien. Die angegebenen Inhalte werden unter Umständen noch zeitnah (kurz vor oder nach der Vorlesung) verändert.

Für den praktischen Teil werden an jedem Tag Übungsaufgaben gestellt. Diese werden im Übungsteil der Lehrveranstaltung im Rechenzentrum besprochen und dann bearbeitet. Es wird erwartet, dass diese Hausaufgaben nach Ende der offiziellen Übungszeit in Eigenarbeit beendet werden. Die Ergebnisse werden in einem SVN-Repository eingecheckt (Einteilung am 15.04.) und von mir durchgesehen. In der nächsten Übung werden dann die wichtigsten Schwierigkeiten noch einmal besprochen. 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 

2) Ganzzahlarithmetik
    2.1) Zahlendarstellung, Vergleiche, Addition, Multipikation 
    2.2) Division, Rationale Arithmetik

3) Modulare Arithmetik
    3.1) Berechnung modularer Funktionen
    3.2) Anwendungen in der Kryptographie
    3.3) Primzahltest mit Hilfe modularer Arithmetik

4) Polynomarithmetik
    4.1) Addition und Multiplikation
    4.2) Division und einfache Faktorisierung

5) Polynomiale Gleichungssysteme
    5.1) Algebraische Grundlagen
    5.2) Lösung über Resultanten

6) Effiziente Faktorisierung von Polynomen 
    6.1) Faktorisierung in Z_p[x] und GF(q)[x]
    6.2) Faktorisierung in Q[x] über den Umweg Z_p[x]

 Zusammenfassung für die Klausurvorbereitung

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: