WiSe 15/16: Algorithmen zum Aufzählen und Abzählen (AAA)
Günther Rothe
Comments
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.
Suggested reading
D. E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. (Addison-Wesley, 2011), xv+883pp. ISBN 0-201-03804-8
close16 Class schedule
Regular appointments