"I would rather have today's algorithms on yesterday's computers than vice versa." -- Philippe Toint
Effiziente Algorithmen sind das mächtigste und vielfältigste Werkzeug der Informatik. Es gibt viele Möglichkeiten, um ein gegebenes Problem zu lösen und die Suche nach einer geeigneten Lösungsidee erfordert Kreativität und eine strukturierte Herangehensweise. Die Mühe lohnt sich, denn eine gute algorithmische Idee und deren effiziente Implementierung ist oftmals viel mehr Wert als pure Rechenkraft.
Doch wie kommt man überhaupt zu einer guten algorithmischen Idee und was macht einen effizienten Algorithmus aus? Wie beweist man, dass ein Algorithmus korrekt ist und wie findet man heraus, wie effizient ein Algorithmus ist? Die Vorlesung "Einführung in die Algorithmik" widmet sich diesen und weiteren Fragen.
Anhand konkreter algorithmischer Probleme (z.B. Sortieren, Suchen, Berechnung kürzester Wege, Minimale Spannbäume,...) werden wir unterschiedliche algorithmische Lösungsansätze kennen lernen und analysieren. Dabei werden wir verstärkt auf das Zusammenspiel der algorithmischen Idee und der passenden Repräsentation der Daten (d.h. der Datenstruktur) eingehen. Algorithmen und Datenstrukturen bilden eine Einheit. Eine gute algorithmische Idee wird nur mit einer passenden Datenstruktur zu einem effizienten Algorithmus und eine geeignete Datenstruktur hat nur dann eine Wirkung, wenn diese optimal ausgenutzt wird.
Ziel der Vorlesung ist die Entwicklung und Schulung einer strukturierten Herangehensweise an algorithmische Probleme. Wir entwickeln dabei gemeinsam effiziente Algorithmen mit passenden Datenstrukturen, beweisen deren Korrektheit und analysieren deren Resourcenbedarf (Laufzeit und Speicherplatz). Dabei werden wir für einige Probleme bis an die Grenzen des Machbaren stoßen und bestmögliche Algorithmen betrachten.
Die Vorlesung richtet sich an BA-Studierende im fünften oder sechsten Semester und legt die Basis für weiterführende Veranstaltungen im Fachgebiet "Algorithm Engineering".
