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