Robuste Lernverfahren und Datenkomprimierung

• Applicant: Professor Dr. Rüdiger Reischuk
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5435325

Klassisch wird der Aufwand zur Lösung algorithmischer Probleme durch die worst-case Komplexität gemessen und es wird gefordert bzw. angenommen, daß das Problems exakt zu lösen ist und die Eingabedaten fehlerfrei vorliegen. Für viele Optimierungsproblemen kann es keine exakten worst-case effizienten Lösungsverfahren geben, falls komplexitätstheoretische Vermutungen wie P 54 .... zutreffen. Deshalb sind auch die average-case Komplexität und approximative Lösungsverfahren von Interesse. Für das Sortieren von Daten, für Informationsübertragung in Netzen sowie beim algorithmischen Lernen Boolescher Funktionen haben wir hierzu in der ersten Projektphase Untersuchungen begonnen und wollen diese weiterführen. Daneben sollen auch online und Sicherheitsaspekte berücksichtigt werden. Bei manchen Anwendungen - etwa bei der Verarbeitung molekularbiologischer Daten - ist die Situation dadurch erschwert, daß die Eingabedaten mit Fehlern behaftet sind. Es sollen algorithmische Methoden entwickelt werden, die unter derartigen inpräzisen Bedingungen dennoch eine effiziente und robuste Problemlösung ermöglichen. Für das Shortest-Common-Superstring-Problem sowie das Lernen relevanter Attribute ist derartiges bereits geschehen. Ein längerfristiges Ziel ist es, bei kombinatorischen Problemen Eigenschaften zu finden, die zu der notwendigen Eingabepräzision korrelieren.

• DFG Programme: Research Grants