Seminar über "Exakte Algorithmen"

Im Seminar über "Exakte Algorithmen" werden ausgewählte Aspekte der Algorithmik NP-schwerer Probleme behandelt.

Eine einflussreiche Beobachtung in den 'sechziger Jahren' für die Entwicklung der Informatik, dass es zu einer Vielzahl von Problemen scheinbar keine effizienten Algorithmen gibt und sie daher in der Praxis nicht gelöst werden können, ist ein fortwährender Impuls für die Theorie der Algorithmen und der Komplexiät. Diese Beobachtung wurde von Cook und Levin durch Einführung der Komplexitätsklassen NP und P formalisiert und mündete schließlich in eine der Jahrhundertfragen der Theorie, ob P ungleich NP ist. (Das Clay Mathematics Institute nominierte im Jahr 2000 sieben Fragestellungen, wie zum Beispiel die Riemannsche Vermutung, die Poincaresche Vermutung und das P versus NP Problem, für deren Lösung jeweils eine Millionen Dollar ausgesetzt sind.)

Wie sollten nun die scheinbar nicht effizient lösbaren NP-schweren Probleme behandelt werden? Einige methodische Ansätze zur Behandlung von NP-schweren Optimierungsproblemen sind in den letzten 35 Jahren entwickelt worden, wie zum Beispiel Approximation, randomisierte und Online-Algorithmen, heuristische Verfahren oder exakte Algorithmen. Da sich viele Probleme von großer praktischer Bedeutung als NP-schwer erweisen, wird in der Praxis zu ihrer Lösung meist auf heuristische Verfahren und effizienten Algorithmen mit exponentieller Laufzeit zurückgegriffen. Bei Implementationen auf modernen Computern sind häufig Algorithmen mit einer exponentiellen Laufzeit von z. B. O(1.01ⁿ) im Vergleich zu Algorithmen mit polynomieller Laufzeit von z. B. O(n⁴) zu bevorzugen.

Entwurf und Analyse von schnellen Algorithmen mit nicht-polynomieller Laufzeit sind somit wichtige Aufgaben. Jedes NP-vollständige Problem lässt sich mit ausschöpfender Suche lösen. Den ersten Schritte, auf dem Weg eine effiziente Lösung zu erzielen, stellt somit der Entwurf von Algorithmen, die wesentlich schneller als ausschöpfende Suche, aber dennoch nicht in Polynomzeit das Problem lösen, dar. Der Term 'exakter Algorithmus' ist eine Kurzform des Begriffes 'effizienter Algorithmus mit nicht-polynomieller Laufzeit'.

Das Seminar wendet sich an Studenten des Hauptstudiums, die über Grundkenntnisse aus dem Bereich der Komplexitätstheorie verfügen. Diese können z.B. im Rahmen einer Veranstaltung über Effiziente Algorithmen oder Theoretische Informatik erworben worden sein. Die Vorbesprechung findet am Dienstag, den 11.10.2005, von 17.00 - 18.00 im Raum 616 des Pohlighauses statt.

Bei weiteren Fragen, die sie auf diesen Seiten nicht beantwortet sehen, können Sie sich per E-Mail an Bert Randerath wenden.

Vorbesprechung

Eine Vorbesprechung findet Dienstag, den 11.10.2005, von 17.00 - 18.00 Uhr Raum 616, Pohlighaus, statt.