FG 413: Algorithmen III (-Z)


Der Entwurf und die Analyse von Algorithmen ist eng verknüpft mit Einsichten in die Struktur der Objekte, die die Algorithmen als Eingabe erhalten. Das zentrale Thema des Forschungsvorhabens ist es, diese Verknüpfung im Hinblick auf den Einfluss des Zufalls zu untersuchen - wie wirkt sich die Hinzunahme von Zufall auf algorithmische und strukturelle Fragestellungen in der Diskreten Mathematik aus?



Der Zufall ist hierbei gleichermaßen Forschungsobjekt wie Untersuchungsmethode. Im Hinblick auf Strukturerkenntnisse wird einerseits nach Eigenschaften gesucht, die zufällige Objekte mit hoher Wahrscheinlichkeit besitzen, andererseits charakterisieren wir Objekte durch Benutzung des Zufalls. Und auch unter algorithmischen Aspekten setzt sich diese Dualität fort: Einerseits wird untersucht, wie sich Algorithmen auf zufälligen Eingaben verhalten, andererseits werden Verfahren analysiert, deren Entscheidungen zufällige Komponenten aufweisen.



Auf der algorithmischen Seite gilt das Interesse kombinatorischen Optimierungsproblemen. Dadurch treten ganz natürlich Polytope, Graphen und partielle Ordnungen als Forschungsobjekte von Strukturuntersuchungen in den Mittelpunkt. Die Forschergruppe bündelt dabei die individuellen Erfahrungen und Kompetenzen, die die beteiligten Arbeitsgruppen in den letzten Jahren mit unterschiedlichen Ansätzen in dem Spannungsfeld von Algorithmen, Struktur und Zufall gewonnen haben.


Projektleitung
Schacht, Mathias Prof. Ph. D. (Details) (DFG-Forschergruppen)

Laufzeit
Projektstart: 07/2004
Projektende: 07/2008

Zuletzt aktualisiert 2020-10-03 um 16:44