Programmierpraktikum (Grundstudium)
Programmierpraktikum Diskrete Optimierung
Prof. Dr. Bernhard Korte
Prof. Dr. Jens Vygen
Dr. Ulrich Brenner
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.
|
Übersicht: alle Semester
Programmierpraktikum Neuroinformatik
Algorithmische Geometrie II