Forschungsinstitut für Diskrete Mathematik

Programmierpraktikum für das Grundstudium

Sommersemester 2005


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, das 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 wohl bekannten 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.



Die Vorbesprechung zu dieser Veranstaltung findet am

Montag, den 31. Januar 2005 um 10 Uhr c.t.
im Seminarraum des Institutes für Diskrete Mathematik

statt.


Studenten, die Interesse an einem Praktikumsplatz haben, aber nicht an der Vorbesprechung zu dieser Veranstaltung teilnehmen können, werden gebeten, sich mit

Dirk Müller,
mueller (at) or.uni-bonn.de,
Tel. 0228 / 73 87 86

in Verbindung zu setzen.



Zahl der Plätze: 14


Prof. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen