Für konkrete algorithmische Probleme soll der mittlere Zweitaufwand zu ihrer Lösung, Approximationsmöglichkeiten sowie Strategien bei fehlerbehafteten Eingabedaten untersucht werden

• Antragsteller: Professor Dr. Rüdiger Reischuk
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5311982

Klassisch wird der Aufwand zur Lösung algorithmischer Probleme durch die worst-case Komplexität gemessen - die maximale Rechenzeit über alle Eingaben einer bestimmten Größe. Darüber hinaus wird in der Regel angenommen, daß das Problem exakt zu lösen ist und daß die Eingabedaten vollkommen fehlerfrei vorliegen. Dies führt bei vielen Problemen zu dem Ergebnis, daß keine effiziente Lösungsverfahren existieren können, falls komplexitätstheoretische Vermutungen wie "P ungleich NP" zutreffen. Oftmals wären Verfahren, die zumindes im Mittel eine schnelle Laufzeit erreichen oder deren Resultat zumindest in der Nähe des Optimums liegt, bereits von großem praktischen Interesse. Neben allgemeinen strukturellen Untersuchungen soll für eine Reihe von Problemklassen vorwiegend kombinatorischer Natur, deren average-case Komplexität und Approximierbarkeit eingehend untersucht werden, unter anderem für das Sortieren von Daten, Problemstellungen in der Stringverarbeitung sowie algorithmisches Lernen. Während diese beiden abgeschwächten Gütekriterien zu einer Verbesserung der Effizienz der Lösungsverfahren führen können, wid die Aufgabenstellung bei manchen Anwendungen - etwa bei der Verarbeitung molekular-biologischer Daten - dadurch erschwert, daß die Eingabedaten mit Fehlern behaftet sind. Diese Situation soll zunächst geeignet modelliert werden. Es sollen dann algorithmische Methoden entwickelt werden, die eine effiziente Problemlösung auch unter derartigen Bedingungen erl

• DFG-Verfahren: Sachbeihilfen