Seminar über Algorithmen
Günter
Rote
S 19576 (WiSe2001)
-
SWS: 2S
-
Zeit: nach Vereinbarung (Vorschlag: Di 16-18)
-
Ort: Takustraße 9, SR 055 (voraussichtlich)
-
Vorbesprechung: Donnerstag 18.10., 16 Uhr c.t.,
SR 055, Takustraße 9
Der im Vorlesungsverzeichnis vorgesehene
Termin (Do 16-18) kollidiert mit meinem Praktikum effiziente Algorithmen
und
muss daher verschoben werden.
Inhalt
Schnelle Algorithmen zur Gitterbasenreduktion und ihre Anwendungen in der
Computeralgebra, zur Approximation, und zur ganzzahligen Optimierung.
Themen
-
Einführung: Gitterbasenreduktion, Begriffe,
Anwendungen, Algorithmen
-
Schnelle Algorithmen für den größten
gemeinsamen Teiler, Kettenbrüche
-
Schönhage und Strassen
-
HALF-GCD-Zugang (Aho, Hopcroft, und Ullman)
-
Algorithmen in höheren Dimensionen
-
Höherdimensionale Kettenbruchentwicklungen
-
Reduktion in drei Dimensionen (Semaev)
-
Der LLL-Algorithmus
Voraussetzungen:
Gitterbasenreduktion gehört zur Geometrie der Zahlen, die zwischen
Geometrie und Zahlentheorie beziehungsweise Algebra angesiedelt ist. Daher
sollte man entweder Talent zur geometrischen Anschauung oder zum algebraischen
Verständnis (vorwiegend lineare Algebra/analytische Geometrie) haben
- am besten beides. Algorithmisches Verständnis (Entwurf und Analyse
von Algorithmen) ist hilfreich.
Perspektiven:
Studien- oder Diplomarbeiten können im Anschluss vergeben werden.