19321101 Vorlesung

WiSe 15/16: Algorithmen zum Aufzählen und Abzählen (AAA)

Günther Rothe

Kommentar

Manche Probleme in der Mathematik oder in anderen Anwendungsgebieten kann man lösen, indem man eine große Zahl von Möglichkeiten systematisch durchprüft und dabei auch die schnellsten Computer in die Knie zwingt. In dieser Vorlesung werdenverschiedene solche Algorithmen besprechen.
Die Anzahl von gewissen kombinatorischen Objekten ist unter anderem in der Physik oder in der Statistik wichtig (abzählen). In anderen Situationen möchte man die Objekte der Reihe nach erzeugen, also aufzählen, zum Beispiel um das beste Objekt zu suchen (Optimierung).

Da die Anzahl der Objekte oft sehr groß ist und gegen die Leistungsgrenze der Rechner stößt, kommt es bei den Algorithmen für diese Aufgaben auch auf effiziente Implementierung an, und man muss gelegentlich versuchen, auch noch das letzte Bit einzusparen.

Themen: Lexikographische Reihenfolge, Rangbestimmung, Bijektionen. Erzeugen mit polynomieller Verzögerung, Gray-codes; isomorphe Strukturen, Automorphismen und Gruppen, Backtracking. Permutationen, Teilmengen, Kombinationen, Partitionen, Spannbäume.
Die Methode der Übergangsmatrizen, Rechnen mit Permutationsgruppen, entgegengesetzte Suche, heuristische Optimierungsmethoden, mechanische Modelle.

Anwendungen: Golomb-Maßstäbe, maximale Packungen und minimale Überdeckungen, Auseinanderfalten von Knoten, Frage- und Antwortspiele, Orientierungen des Würfels mit eindeutigen Senken, Polyominos, Ecken eines Polyeders, Triangulierungen und Pseudotriangulierungen, Kompression von Dreiecksnetzen, geometrische Packungsprobleme.

Schließen

Literaturhinweise

D. E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. (Addison-Wesley, 2011), xv+883pp. ISBN 0-201-03804-8

Schließen

16 Termine

Regelmäßige Termine der Lehrveranstaltung

Mi, 14.10.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 21.10.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 28.10.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 04.11.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 11.11.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 18.11.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 25.11.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 02.12.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 09.12.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 16.12.2015 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 06.01.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 13.01.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 20.01.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 27.01.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 03.02.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Mi, 10.02.2016 08:00 - 10:00

Dozenten:
Univ.-Prof. Dr. Günther Rothe

Räume:
049/T9 Seminarraum (Takustr. 9)

Studienfächer A-Z