Effiziente Algorithmen SS 2016

Es gibt kaum einen Bereich der Informatik, der ohne Algorithmen auskommt. Auch im Grundstudium der Informatik sind sie fest verankert: in DAP 2 werden viele grundlegende Algorithmen vorgestellt, davon viele effiziente Algorithmen. In GTI bzw. TIfAI werden Grenzen der Möglichkeit, solche effizienten Algorithmen zu entwickeln, ausgelotet und obwohl das Thema schon seit vielen Jahren intensiv behandelt wird, ist es immer noch sehr aktuell.

Es gibt viele Gründe, sich für diese Vorlesung zu interessieren. Neben den offensichtlichen Vorteilen, welche die Kenntnis effizienter Algorithmen und vor allem Entwurfstechniken für effiziente Algorithmen mit sich bringt, kann man anführen, dass die Algorithmik, ein Teilgebiet der theoretischen Informatik, wegen ihrer immensen praktischen Bedeutung mit gutem Recht als eines der praktischsten Teilgebiete der theoretischen Informatik bezeichnet werden kann. Sie hat darum das Potenzial, manchem, der Theorie eher skeptisch begegnet, einen gelungenen Einstieg in ein großes und spannendes Forschungsgebiet zu bieten.

Man kann Algorithmen auf verschiedene Arten systematisieren und darstellen. Im ersten Teil der Vorlesung werden wir uns mit effizienten Algorithmen im engeren Sinn beschäftigen und diskutieren Probleme, für die es deterministische Algorithmen gibt, die auch im Worst Case eine optimale Lösung in Polynomialzeit berechnen. Lässt sich ein Problem nicht so lösen, findet man häufig trotzdem im Worst Case in polynomieller Zeit Lösungen, die zwar nicht optimal sind, die aber eine optimale Lösung mit garantierter Mindestgüte approximieren. Solche Approximationsalgorithmen, sowohl deterministische als auch randomisierte, sind ebenfalls Gegenstand dieser Vorlesung. Findet man weder optimale Lösungen noch gute Approximationen in zufriedenstellender Zeit, kann man versuchen, heuristische Algorithmen zur Problemlösung einzusetzen. Neben diesen Heuristiken nehmen wir uns in der restlichen Zeit die Freiheit, ausgewählte Themen zu betrachten, die spannend und praktisch relevant sind, die zur Allgemeinbildung in der Informatik gehören und in anderen Vorlesungen vielleicht keine Erwähnung gefunden haben.