Approximative Algorithmen (Vorlesung)
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.