Veranstaltungen im Wintersemester 1998/99
Vorlesung "Effiziente Algorithmen"
Die Vorlesung beschäftigt sich mit Entwurf und Implementierung effizienter Algorithmen für kombinatorischer Probleme, insbesondere auch kombinatorischer Optimierungsprobleme. Es sollen folgende Themen behandelt werden: Graphenalgorithmen (Minimale Bäume, kürzeste Wege, Netzwerkflüsse, Matching), Approximative Algorithmen und Heuristiken (Bin-Packing, Scheduling, Knapsack-Problem, Traveling-Salesman-Problem), Relaxierungen, Verfahren zur Bestimmung optimaler Lösungen (dynamische Optimierung, Branch & Bound). Grundkenntnisse über Datenstrukturen und lineare Optimierung sind von Nutzen.Termine: Di 9-11, Do 9-11, Raum: AM -104, Beginn: Do, 15.Oktober 1998
Übungen zur Vorlesung "Effiziente Algorithmen"
(zusammen mit M. Oswald)Die Übungen dienen zur Vertiefung des Stoffes der Vorlesung und umfassen insbesondere auch die Implementierung von Algorithmen.
Termin: , Raum: ,
Seminar "Entwicklung von Branch-and-Cut-Algorithmen mit ABACUS"
Branch-and-Cut-Algorithmen gehören zu den erfolgreichsten Ansätzen zur optimalen Lösung NP-schwieriger Optimierungsprobleme. Die Umsetzung theoretischer Vorarbeiten in konkrete Implementierungen gestaltet sich allerdings sehr aufwendig. Mit dem Softwaresystem ABACUS ist mittlerweile ein komfortables Hilfsmittel zur Realisierung derartiger Algorithmen vorhanden. ABACUS wird bereits von mehr als 100 Benutzern eingesetzt und hat sich als sehr nützliches Tool erwiesen. In dieser Veranstaltung sollen die Grundlagen von Branch-and-Cut-Algorithmen sowie anhand konkreter Implementierungen der Umgang mit ABACUS erlernt werden. Grundkenntnisse in C++ und linearer Optimierung sind von Nutzen. Der Termin der Vorbesprechung wird rechtzeitig durch Aushang bekanntgegeben.Vorbesprechung: Donnerstag, 15.10.98, 11 Uhr s.t., INF 293, Seminarraum 215
