Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum für das Grundstudium
Wintersemester 2004/05
Thema: Steinerbäume
In diesem Programmierpraktikum soll ein Teilproblem aus der Verdrahtung
höchstintegrierter Logikchips behandelt werden: es geht darum, eine
Menge von Anschlusspins verschiedener Bauelemente auf einem Chip
kürzestmöglich miteinander zu verbinden. Die Konstruktion eines
minimalen Spannbaumes führt im allgemeinen nicht zu einer optimalen
Lösung - durch das Einfügen zusätzlicher sogenannter Steinerpunkte kann
man meist eine kürzere Verdrahtungslänge erreichen. Daraus ergibt sich
das Steinerbaumproblem, dass zwar NP-schwer ist, aber in unserem
Anwendungsfall nur auf Instanzen mit wenigen Terminalen (Anschlusspins)
zu lösen ist.
Ziel des Praktikums ist die effiziente Implementierung eines
Algorithmus, der eine Verallgemeinerung des wohlbekannten
Kürzeste-Wege-Algorithmus von Dijkstra darstellt und das
Steinerbaumproblem mittels dynamischer Programmierung auf Graphen mit
beliebigen nichtnegativen Kantengewichten exakt löst. Trotz der geringen
Größe jeder einzelnen Probleminstanz kommt einer effizienten
Implementierung hohe Bedeutung zu, da das Problem auf den größten
derzeit entwickelten Chips millionenfach zu lösen ist.
Studenten, die Interesse an einem Praktikumsplatz haben,
werden gebeten, sich bis
Mittwoch, 28. Juli 2004,
mit
Dirk Müller,
mueller@or.uni-bonn.de,
Tel. 0228 / 73 87 86
in Verbindung zu setzen.
Prof. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen