Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum für das Grundstudium
Wintersemester 2007/08
Thema: Intervall-Bäume und Sweepline-Verfahren
Moderne höchstintegrierte Logikchips (VLSI-Chips) bestehen aus vielen Millionen
meist rechteckiger Bauteile, die auf einer gegebenen Chipfläche angeordnet
und durch elektrische Leiter verbunden werden müssen. Bei der Berechnung von
Bauplänen für solche Chips ist es notwendig, riesige Mengen von
(achsenparallelen) Rechtecken
effizient zu verwalten und eine Reihe von Funktionen auf ihnen auszuwerten.
In diesem Programmierpraktikum sollen Algorithmen für einige grundlegende
Probleme, die bei der
Behandlung solcher Rechteckmengen entstehen, implementiert werden. Beispielsweise
sollen Differenzen oder Schnitte der von zwei Rechteckmengen überdeckten
Punktmengen bestimmt werden. Eine andere Aufgabe besteht darin, eine Menge von
Rechtecken durch eine andere Menge zu ersetzen, die die gleiche Fläche
überdeckt, aber möglichst wenige Rechtecke enthält.
Diese Probleme lassen sich effizient mit Algorithmen lösen, die auf
Sweepline-Verfahren beruhen. Die grundlegenden Datenstrukturen, die dabei gebraucht
werden, sind sogenannte Intervall-Bäume, mit denen sich Mengen von Intervallen
verwalten lassen.
Bei allen Problemen ist
eine sehr effiziente Implementierung erforderlich, da die Programme auf echten
Instanzen aus dem VLSI-Design getestet werden sollen und auch auf sehr großen
Mengen noch in vertretbarer Zeit eine Lösung liefern sollen.
Die Veranstaltung richtet sich an Studentinnen und Studenten sowohl der Informatik
als auch der Mathematik. In jedem Fall wird aber ein hohes mathematisches Interesse
vorausgesetzt.
Eine PDF-Datei mit der genauen Aufgabenstellung und weiteren Informationen
kann man hier herunterladen.
Testinstanzen:
Alle Instanzen können grundsätzlich für alle Teilaufgaben
verwendet werden.
Instanz 1
Instanz 2
Instanz 3
Instanz 4
Instanz 5
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner