Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum für das Grundstudium
Sommersemester 2007
Thema: Effiziente Algorithmen für große Rechteckmengen
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. Außerdem
sollen Zugriffsfunktionen implementiert werden, mit denen sich schnell alle
Rechtecke in einem bestimmten Bereich finden 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.
Eine PDF-Datei mit der genauen Aufgabenstellung und weiteren Informationen
kann man hier herunterladen.
Testinstanzen:
Alle Instanzen können grundsätzlich für Teilaufgaben
verwendet werden.
Instanz 1
Instanz 2
Instanz 3
Instanz 4
Instanz 5
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Dr. U. Brenner