Hörerkreis:
Masterstudiengang Informatik (nach dem Bachelor)

Vorlesungstermin: Di 15:30 Uhr - 18:15 Uhr, HS3 + RZ5
    (Die Veranstaltung beginnt jeweils in HS3. Für praktische Übungen gehen wir in RZ5)

Computeralgebra 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.

Computeralgebra-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.

Neben einer theoretischen Behandlung wird auch Einblick in die Praxis gegeben, in dem wir die Verfahren an einem Computeralgebra-System ausprobieren. Dafür steht uns in RZ5 das System Maxima zur Verfügung. Dieses System ist open-source und kann über die angegebene Webseite nebst umfangreichem Dokumentationsmaterial heruntergeladen werden. 

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.

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 vorläufige Gliederung der Vorlesung gegeben. Die angegebenen Kapitel werden zeitnah (spätestens am Vorabend vor dem nächsten Vorlesungstermin) mit dem erwarteten Terminumfang versehen sowie mit der Übersicht verlinkt.

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

1) Arbeiten mit Maxima (15.04., gleich in RZ5)

2) Ganzzahlarithmetik (22.04. inkl. Aufgabe 1, 29.04. inkl. Aufgabe 2)

3) Modulare Arithmetik (06.05. inkl. Aufgabe 3, 13.05.)

4) Anwendungen in der Kryptographie (13.05. inkl. Aufgabe 4: gegenseitiges Codieren und Decodieren)

5) Spezialthema: Primzahltest (20.05. inkl. Aufgabe 5)

6) Polynomarithmetik
    1. Teil: Addition und Multiplikation (27.05. inkl. Aufgabe 6, 03.06. inkl. Aufgabe 7)
    2. Teil: Division und Einfache Faktorisierung (10.06., aktualisiert am 24.06.)

Vorbereitung für die Kapitel 7-9: Algebraische Grundlagen (10.06. inkl. Aufgabe 8, 24.06.)

7) Polynomiale Gleichungssysteme (24.06. inkl. Aufgabe 9, 01.07.)

8) Effiziente Faktorisierung von Polynomen
    1. Teil: Faktorisierung in endlichen Körpern (01.07.inkl. Aufgabe 10)
    2. Teil: Effiziente Faktorisierung in Q[x] (08.07.)

Zusammenfassung der Vorlesung als Vorbereitung für die Prüfung

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

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

Zum Wiederholen und Nacharbeiten von speziellen Themen:

Gudrun Demmig: Matrizen und Determinanten, Demmig Verlag 1988 (3. Auflage), ISBN 3-921092-46-9

Rainer Schulze-Pillot: Elementare Algebra und Zahlentheorie: Springer 2007, ISBN 978-3-540-45379-6