Approximative Algorithmen

Thema

Eine Einordnung und allgemeine Beschreibung des Vorlesungsgebietes finden Sie im Bereich Algorithmentheorie bei den „Lehrinformationen”.

Vorlesungsinhalt

In dieser Masterstudiumsvorlesung werden
wir der Frage nachgehen, wie wir NP-harten Problemen
algorithmisch begegnen können. Allgemein wird geglaubt,
dass es für diese Klasse von Problemen keine exakten Algorithmen
gibt, die sie in Polynomzeit lösen.

Was ist aber, wenn man sich mit genäherten Lösungen zufrieden gibt?

Und was soll das eigentlich heißen?

Nach einem Einführungsteil werden wir uns im ersten Teil der Vorlesung
mit Techniken zum Entwurf von Approximationsalgorithmen befassen und dann
im zweiten Teil zur eigentlichen Approximationstheorie übergehen, wo wir verschiedene
Komplexitätsklassen kennenlernen werden sowie adäquate Reduktionsbegriffe.

Teilnahmevoraussetzungen

Sie sollten die Grundvorlesungen aus den ersten Semestern Informatik erfolgreich besucht haben. Insbesondere ist das in Veranstaltungen zu Berechenbarkeit und Komplexität und Algorithmen und Datenstrukturen gewonnene Grundverständnis zur Algorithmik hilfreich.

Vorlesung

Dienstag 12-14 Uhr, F 59, Fernau

Übung

Mittwoch 10-12 Uhr, H 405, Casel