Freie Universität Berlin
Fachbereich Mathematik und Informatik

Arbeitsgruppe

Theoretische Informatik

Menu


Algorithmen zum Aufzählen und Abzählen

VL 19565   WS 04/05

2-stündig, ECTS Credits: 2

Dozent: Prof. Dr. Günter Rote
Di 14 - 16   SR 006
Beginn: 19.10.2004
Ü 19566
Dozent: Ludmila Scharf
Do 16 - 18   SR 053

Inhalt der Veranstaltung

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.

Zielgruppe

Kombinatorisch interessierte Mathematikstudenten oder Hacker, die gerne das letzte Bit aus dem Programm quetschen.

Scheinerwerb

Um einen Schein zu erwerben, müssen folgende Anforderungen erfüllt werden:
  • Insgesamt sind mindestens 60% der Punkte auf den Übungsblättern zu erreichen.
  • Jeder Teilnehmer muss eine Übungsaufgabe im Tutorium vorrechnen.
Bei Bedarf werden benotete Scheine ausgestellt. Die Note wird voraussichtlich durch eine kurze mündliche Prüfung und die Mitarbeit in den Übungen am Ende des Semesters festgelegt.

   Druckversion