Michael Eisermann

Alles Leben ist Problemlösen.
Karl Popper (1902-1994)

Algorithmische Algebra

Seminar im Wintersemester 2010/2011.

Seminar Montag 17:30 - 19:00 Raum V57.7.530

Auf dieser Seite finden Sie:

Aktuelles

Diese Seite wird nicht mehr regelmäßig aktualisiert; sie wird aber noch längere Zeit zugänglich bleiben, um als Archiv zu dienen. Zur Übersicht: aktuelle und vergangene Lehrveranstaltungen

Einführung und Motivation

Seit Beginn der Computer-Ära vor mehr als 60 Jahren versucht man neben numerischen Rechnungen auch algebraische Umformungen maschinell zu erledigen. Hierzu stehen heutzutage leistungsfähige Computeralgebrasysteme zur Verfügung (wie GAP, Magma, Maple, und Bibliotheken wie GMP, NTL), deren Entwicklung Hand in Hand ging mit der Entstehung der algorithmischen Algebra.

Ziel dieses Seminars ist eine Einführung in die grundlegenden Algorithmen, die hierfür nötig sind und deren Effizienz das A und O jeder realistischen Anwendung darstellen.

Was bedeutet Algorithmik?

Viele (einfache, leichte) Rechnungen können Sie lösen, ohne sich darüber klar werden zu müssen, nach welchem allgemeinen Verfahren Sie vorgehen. Bei einer maschinellen Ausführung delegieren Sie einen (monotonen, lästigen) Teil dieser Arbeit. Damit das gut gehen kann, müssen Sie in der Vorbereitung bzw. Programmierung jedoch sehr viel genauer arbeiten als gewohnt: Sie müssen sich über das auszuführende Verfahren vorher genau Rechenschaft ablegen.

Zur sorgfältigen Analyse des gegebenen Problems und Ihrer (vermeintlich allgemeinen) Lösung müssen Sie sich folgende Fragen stellen:

Vor- und Nachbedingungen sind die Spezifikation des Problems, die Methode schlägt einen möglichen Lösungsweg vor. Zu einem gegebenen Problem gibt es im Allgemeinen viele verschiedene Lösungswege: Ein Algorithmus besteht aus Spezifikation und Methode. Ob ein Algorithmus etwas taugt, entscheidet sich anhand von zwei Fragen:

Die Erfahrung zeigt, dass es für ein gegebenes Problem sehr verschiedene Algorithmen geben kann, die jeweils ihre eigenen Stärken und Schwächen haben, und somit verschiedene Teile des Gesamtproblems abdecken. Diese Alternativen muss man kennen und ihre Vor- und Nachteile verstehen , um sie geeignet einzusetzen.

Manchmal sind auch vermeintliche Umwege über andere Strukturen hilfreich und stellen sich bei genauerem Verständnis als geschickte Abkürzungen heraus.

Was ist Computeralgebra?

Die obigen Grundprinzipien treffen auf jede Art von Programmierung zu, und es gibt unzählige Algorithmen die interessante Probleme auf raffinierte Weise lösen, und die eines eingehenden Studiums würdig sind. — Man lese Knuth!

Dieses Seminar betrachtet die Algebra unter diesen algorithmischen Gesichtspunkten. Anders als in der Numerik, wo Fragen der Näherung und Konvergenz eine wichtige Rolle spielen, geht es in der Computeralgebra um exakte, algebraische Rechnungen. Hier sind Korrektheit und Komplexität die alles überragenden Kriterien. Das Seminar soll in die grundlegenden Algorithmen und Techniken einführen.

Hinweis: Im WiSe 2010 wird parallel eine Vorlesung Computeralgebra angeboten. Wir werden versuchen, thematische Überschneidungen möglichst zu vermeiden. Das Seminar bietet insbesondere die Möglichkeit, die Schwerpunkte zu wählen und die Themen nach den Interessen der Teilnehmer auszurichten.

Die Mathematik ist mehr ein Tun als eine Lehre.
Luitzen Brouwer (1881-1966)

Vorkenntnisse

Die algorithmische Algebra ist ein faszinierendes, großes und sehr erfolgreiches Gebiet. Sie ist zu einem Standardwerkzeug geworden, in industruiellen Anwendungen ebenso wie in der mathematischen Forschung. Dieses Seminar kann nur die Grundlagen präsentieren und als Einladung zum weiteren Studium dienen.

Hierzu werden grundlegende Techniken, insbesondere effiziente Rechenverfahren für große ganze Zahlen, Polynome, Matrizen, etc. untersucht, aber auch speziellere Fragen wie Algorithmen zu Polynomen in mehreren Variablen oder endlichen Gruppen können bei Interesse behandelt werden.

Das Seminar erfordert gute algebraische Kenntnisse: Die lineare Algebra und die Algebra sind daher zum Verständnis unabdingbar. Nützlich ist zudem die Vertrautheit mit algorithmischer Denkweise und Programmiererfahrung. In vielen Fällen ist es von Vorteil, die vorgestellten Algorithmen selbst zu implementieren, zu testen, und zu variieren (aufbauend auf einem Computeralgebrasystem oder einer geeigneten Programmbibliothek).

Die Themen sind gut zugänglich. Allerdings braucht jeder, der zur wahren Erleuchtung gelangen will, eine vertiefte Einarbeitung. (Das hängt natürlich von der Affinität zur Algebra und zur Algorithmik ab.) Bitte entscheiden Sie sich für dieses Seminar nur, wenn Sie viel lernen wollen und bereit sind, hart dafür zu arbeiten.

`I only took the regular course.' – `What was that?' inquired Alice.
`Reeling and Writhing, of course, to begin with,' the Mock Turtle replied;
`and then the different branches of Arithmetic —
Ambition, Distraction, Uglification, and Derision.'
Lewis Carroll (1832–1898), Alice's Adventures in Wonderland

Zielsetzung

Das Ziel dieses Seminars ist es, möglichst weite Teile des wunderbaren Buches Modern Computer Algebra von Gathen & Gerhard durchzuarbeiten und somit einen vertieften Überblick über die algorithmische Algebra zu gewinnen. Gelegentliche Ausflüge zu anderen Themen, je nach Interesse, können das Repertoire auflockern.

Manche der Themen lassen sich zu Bachelor-Arbeiten ausarbeiten.

Vorträge

Jeder Vortrag präsentiert eine Kernidee, meist in Form eines Algorithmus oder mehrere Varianten. Ausgehen sollten Sie dabei von einer interessanten Fragestellung oder einem praktischem Problem, das Sie klar herausstellen und motivieren. Anschließend erläutern Sie mögliche Lösungen — so grob wie nötig, so detailliert wie möglich. Hierzu arbeiten Sie die Kernidee klar heraus und erklären den so entwickelten Algorithmus, nach Möglichkeit insbesondere seine Korrektheit und Komplexität. Zum guten Schluss ist es immer schön, ein paar repräsentative Anwendungen zu erläutern.

Wenn Sie möchten können Sie zur Illustration auch Computer-Experimente präsentieren, wenn dies übersichtlich möglich ist und inhaltlich überzeugend. Die Illustration setzt ihrer Arbeit sozusagen das Krönchen auf, sie ersetzt natürlich nicht die harte mathematisch-algorithmische Arbeit: Man kann nicht ernten ohne zu ackern.

Programmierung

Dieses Seminar könnte genauso gut "Computeralgebra" heißen. Dieser Titel wäre allerdings leicht irreführend, denn wir werden uns hier aus Zeitgründen auf die Theorie konzentrieren und die Praxis der Programmierung aufschieben müssen. Das ist sehr bedauerlich, aber erfahrungsgemäß fehlen Mathematik-Studenten schlicht die nötigen Programmierkenntnisse und Erfahrung. Dieses Seminar kann diese leider nicht herbeizaubern, sondern nur die theoretischen Grundlagen legen und hoffentlich zur Vertiefung und Anwendung motivieren.

Idealerweise sollten die Teilnehmer programmieren können und die vorgestellten Algorithmen in eigenen Implementationen auch experimentell untersuchen. Eine lehrreiche oder gar ordentliche Implementation erfordert jedoch sehr viel Zeit und würde den Rahmen des Seminars sprengen. Wer es dennoch ernsthaft versucht, wird zur Belohnung die Algorithmik richtig verstehen lernen.

Science is what we understand
well enough to explain to a computer.
Art is everything else we do.
Donald Knuth, Vorwort zu dem Buch A=B

Hinweise zu Seminarvorträgen

Generell gilt: Nehmen Sie die Vorbereitung ernst und den Vortrag locker!
(Umgekehrt funktioniert es aller Erfahrung nach schlecht.)

Zielsetzung

Ein Seminarvortrag hat zwei verschiedene, sich ergänzende Ziele:

  1. Das Ziel bei der Vorbereitung ist, dass Sie möglichst viel verstehen.
  2. Das Ziel beim Vortrag ist, dass Ihre Zuhörer möglichst viel verstehen.

Der Erwerb eines Scheins gehört dagegen nicht zu den Zielen eines Vortrages sondern ist allenfalls ein Nebeneffekt. Nehmen Sie sich das bitte zu Herzen, besonders dann, wenn der Scheinerwerb tatsächlich Ihre wesentliche Motivation sein sollte.

Vorbereitung

Gemäß den obigen Zielen findet die Vorbereitung auf zwei Ebenen statt:

  1. Inhaltliche Vorbereitung: Einen guten Vortrag kann man nur halten, wenn man verstanden hat, wovon man spricht. Daher ist eine gründliche inhaltliche Vorbereitung eine unabdingbare Voraussetzung für jeden Vortrag. Diese geht weit über das strikte Minimum des später gehaltenen Vortrags hinaus.
  2. Vortragsvorbereitung: Wenn Sie mit Ihrem Thema vertraut sind, geht die inhaltliche Vorbereitung allmählich über in die Gestaltung des Vortrags. Dazu müssen Sie aus Ihrem inzwischen reichhaltigen Wissen sorgfältig einen kleinen, möglichst relevanten Teil auswählen und zu einem Vortrag verdichten.

Es ist wichtig, diese Ebenen zu verstehen und zu unterscheiden. Nur einen kleinen Teil von dem, was Sie in der inhaltlichen Vorbereitung erlernt haben, werden Sie an der Tafel erklären können. Dennoch ist Ihr Hintergrundwissen wesentlich, schon im Vorfeld um den Vortrag mit Überblick gestalten zu können, dann um im Falle von Rückfragen Details erläutern zu können, oder um passende Beispiele zur Hand zu haben, etc.

Zeitplanung

Bereiten Sie Ihren Vortrag rechtzeitig vor. Wenn Sie erst zwei Wochen vor Ihrem Vortragstermin beginnen, dann ist das nicht rechtzeitig.

Zwei Wochen vor dem Termin soll Ihr Vortrag inhaltlich fertig sein und ein Konzept vorliegen. Kommen Sie dann (spätestens) in meine Sprechstunde oder machen Sie ein Treffen mit mir aus, damit Sie Ihr Konzept diskutieren und Fragen stellen können.

Jetzt ist auch der richtige Zeitpunkt für einen Probevortrag vor Freunden.

Sie können eine Woche vor Ihrem Vortrag gerne noch einmal vorbeikommen, um letzte Fragen zu klären. Wenn Sie allerdings in der letzten Woche zum ersten Mal auftauchen, ist es erfahrungsgemäß zu spät für ernsthafte Ergänzungen und Änderungen.

Nehmen Sie sich zuvor etwa vier Wochen für die inhaltliche Einarbeitung. – Es dauert oft doch länger als man denkt, zudem sind Sie auch anderweitig gefordert. Fangen Sie also insgesamt spätestens sechs Wochen vor Ihrem Vortragstermin mit der Arbeit an.

Ratschläge

Wie halte ich einen guten Seminarvortrag? von Prof. Dr. Manfred Lehn.

Ratschläge für einen schlechten Redner von Kurt Tucholsky.

Wer's nicht einfach und klar sagen kann,
der soll schweigen und weiterarbeiten,
bis er's klar sagen kann.
Karl Popper (1902-1994), Wider die großen Worte

Literatur

Das Ziel dieses Seminars ist es, möglichst weite Teile des wunderbaren Buches Modern Computer Algebra von Gathen & Gerhard durchzuarbeiten. Auch die Bücher von Kaplan oder Koepf können als Leitfaden dienen.

In der Bibliothek wird ein Präsenzregal zu diesem Seminar eingerichtet.

Wenn Sie sich über dieses Seminar hinaus ernsthaft mit Algorithmen beschäftigen wollen, dann nehmen Sie sich ein paar Tage/Wochen/Monate/Jahre, um in Donald Knuths zeitlosem und preisgekröntem Klassiker zu schmökern:

Mögliche Vortragsthemen

Die folgenden Themenvorschläge folgen in etwa dem Buch von Gathen & Gerhard. Je nach Interesse können manche Themen auch auf zwei oder mehr Vorträge ausgedehnt werden, andere Themen können weggelassen oder noch hinzugefügt werden.

  1. Arithmetik in Z und K[X], Rechnermodelle, Komplexitätsklassen, Karatsuba.
  2. Division mit Rest in Z und K[X], Rechnen mit Restklassen, Schnelles Potenzieren.
  3. Euklidischer Algorithmus, Anwendungen, Sätze von Sturm und Cauchy.
  4. Chinesischer Restsatz, Evaluation und Interpolation, modulare Algorithmen.
  5. Matrizen, Gauß-Algorithmus, Koeffizientenexplosion, modulare Algorithmen.
  6. FFT: schnelle Fourier-Transformation, Anwendungen, schnelle Multiplikation.
  7. Newton-Iteration: Taylor-Entwicklung und Konversion, ganzzahlige Wurzeln.
  8. Quadratische Reziprozität, Jacobi-Symbol, Primzahltest nach Solovay-Strassen.
  9. Schnelle Primzahltests: Fermat-Test, Carmichael-Zahlen, Miller-Rabin-Test.
  10. AKS: ein deterministischer Primzahltest in polynomieller Laufzeit.
  11. Faktorisierung von Polynomen über endlichen Körpern.
  12. Faktorisierung ganzer Zahlen: Überblick möglicher Methoden.
  13. Anwendungen in der Public-Key-Kryptographie: Problemstellungen, RSA.
  14. Symmetrische Polynome, Monomordnungen, Division mit Rest.
  15. Gröbner-Basen, Buchberger-Algorithmus, Anwendungen.
  16. Suchen und Sortieren: Problemstellung, Diskussion verschiedener Verfahren.
  17. Endliche Permutationsgruppen, Schreier-Sims-Algorithmus, Anwendungen.
  18. Präsentation durch Erzeuger und Relationen, Todd-Coxeter-Algorithmus, semi-entscheidbare Probleme, unentscheidbare Probleme.

Hinweis: Im WiSe 2010 wird parallel eine Vorlesung Computeralgebra angeboten. Wir werden versuchen, thematische Überschneidungen möglichst zu vermeiden. Das Seminar bietet insbesondere die Möglichkeit, die Schwerpunkte zu wählen und die Themen nach den Interessen der Teilnehmer auszurichten.

Termine im WiSe 2010 – vorläufige Planung

Die folgende Terminplanung ist noch vorläufig und wird schrittweise aktualisiert.

Vorlesungsbeginn am 18. Oktober 2010
S01Michael Eisermann: Arithmetik in Z und K[X], Komplexität, Karatsuba.
S02Michael Eisermann: Potenzieren, euklidischer Algorithmus, chinesischer Restsatz.
S03Andre Zieher: Fourier-Transformation 1
S04Andre Zieher: Fourier-Transformation 2
S05Sven Steiner: Primzahltests, insbesondere AKS
vorlesungsfreie Zeit vom 24. Dezember 2010 bis zum 9. Januar 2011
S06Jonathan Kausch: Todd-Coxeter-Algorithmus und Unentscheidbarkeit
S07Iris Köster & Julia Vinogradska: Schreier-Sims-Algorithmus 1
S08Iris Köster & Julia Vinogradska: Schreier-Sims-Algorithmus 2
Vorlesungsende am 11. Februar 2011

`Can you do Addition?' the White Queen asked.
`What's one and one and one and one and one
and one and one and one and one and one?'
`I don't know,' said Alice. `I lost count.'
Lewis Carroll (1832–1898), Through the Looking Glass