Die Dozenten der Informatik-Institute der Technischen Universität
Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem
Vortrag ein:
Dr. Kröller:
Praktische Theorie - Algorithm Engineering zur Lösung geometrischer
und weiterer Probleme
Beginn: 05.04.2012, 12:30 Uhr
Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23,
1. OG, Hörsaal M 161
Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2012-04-05-kroeller.html
Kontakt:
Ein gegebenes Problem kann oft auf verschiedene Weise gelöst werden
- mit implementierten Verfahren, belegt durch Experimente, oder mit
Algorithmen mit beweisbaren Eigenschaften und Garantien. Viel zu
oft wird sich dabei für genau eine dieser beiden Herangehensweisen
entschieden. Im schlimmsten Fall entstehen für beide Seiten Ergebnisse
unter vollständiger Ignoranz der jeweiligen Gegenseite. Beim Algorithm
Engineering (AE) wird diese Separation aufgehoben, und es werden
Algorithmen entwickelt, die gleichermassen theoretisch wie praktisch
valide sind. Nach einem Überblick über AE werden wir beispielhaft über
das Kunstgalerieproblem berichten, einem seit fast 40 Jahren untersuchten
Kernproblem der Algorithmischen Geometrie: Gegeben ein zweidimensionales
Polygon (die "Galerie"), finde eine minimale Anzahl Punkte ("Wächter"),
von denen aus das ganze Polygon gesehen werden kann. Wir stellen einen
Ansatz vor, mit dem erstmals exakte Lösungen berechnet werden können,
basierend auf doppelt-unendlichen ganzzahligen Programmen. Wir zeigen
Ergebnisse einer praktischen Implementierung und skizzieren Erweiterungen
für praktische Anwendungsfälle aus der Gebäudevermessung mittels
Laserscannern. Schliesslich zeigen wir, wie aus einer experimentellen
Arbeit neue theoretische Fragestellungen und bislang unbekannte Einsichten
entstehen können.
Die Dozenten der Informatik-Institute der Technischen Universität
Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem
Vortrag ein:
Dr. Karrenbauer:
Über Algorithm Engineering und diskrete Optimierung
Beginn: 05.04.2012, 09:30 Uhr
Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23,
1. OG, Hörsaal M 161
Webseite:
http://www.ibr.cs.tu-bs.de/cal/kolloq/2012-04-05-karrenbauer.html
Kontakt:
Hinter zahlreichen Anwendungen stecken Optimierungsprobleme, die effizient
gelöst werden müssen. Viele davon sind von Natur aus diskret oder werden
es durch entsprechende Digitalisierung. In diesem Vortrag werde ich einen
Algorithm Engineering Prozess vorstellen, der systematisch ausgehend von
einer Modellierung als ganzzahliges Programm zu Algorithmen führt, die
nicht nur im theoretischen Sinn effizient sondern auch praxistauglich
sind. Dies werde ich an einigen Fallstudien demonstrieren. Dabei
möchte ich mich insbesondere auf die Entwicklung einer Steuerung für
OLED-Displays konzentrieren und darüber hinaus kurz auf weitere Beispiele
aus den Bereichen Bildverarbeitung und Bioinformatik eingehen.
