Lehre am Lehrstuhl Theoretische Informatik/ Algorithmik
- Informatik 2 – Algorithmen und Datenstrukturen
- Informatik 3 – Theoretische Informatik
- Algorithmenparadigmen
- Geometrische Algorithmen
- Seminare zu Algorithmen
Für eine Übersicht der angebotenen Vorlesungen im aktuellen und den vergangenen Semestern siehe Lehrveranstaltungen.
Wir stellen nun die oben genannten Vorlesungen kurz vor:
Informatik 2 – Algorithmen und Datenstrukturen
Nach einer Besprechung grundlegender Datentypen (wie Listen, Stacks, Queues und Bäume) werden zunächst Datenstrukturen diskutiert, die zur Repräsentation von Mengen geeignet sind und dabei bestimmte Mengenoperationen unterstützen (wie zum Beispiel Dictionaries, Priority Queues und UNION-FIND-Datenstruktur). Weiterhin gehen wir auf Repräsentationen von Graphen ein, behandeln diverse Graphalgorithmen (wie zum Beispiel Tiefen- und Breitensuche, kürzeste Wege, transitive Hülle, starke Komponenten und minimaler Spannbaum) sowie diverse Sortierverfahren (Mergesort, Heapsort, Quicksort, Bucketsort, Radixsort). Die Vorlesung soll die Fähigkeit schulen, bekannte Datenstrukturen professionell einzusetzen, neue Datenstrukturen bei Bedarf selbst zu entwerfen, die Korrektheit eines Algorithmus sauber zu begründen und seine Laufzeit zu analysieren.
Informatik 3 – Theoretische Informatik
Die Vorlesung liefert eine Einführung in die Theorie der Grammatiken (insbesondere kontextfreie Grammatiken) und Automaten (endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in
die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche Rechenprobleme (überhaupt bzw. mit vertretbarem Aufwand) gelöst werden können. Es wird sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht zufriedenstellend gelöst werden können.
In der Vorlesung ergeben sich fundamentale Einsichten zum Verhältnis zwischen
Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Techniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen soll die Einsicht reifen, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Ziel ist zudem ein tieferes Verständnis von Komplexität. Auf den unteren Ebenen der sogenannten Chomsky-Hierarchie finden sich effizient lösbare Anwendungsprobleme der Textmanipulation und der Textanalyse. Auf den
oberen Ebenen machen wir Bekanntschaft mit dem Phänomen der inhärenten Härte
(oder gar Unentscheidbarkeit) eines Problems.
Algorithmenparadigmen
Die Vorlesung vertieft und ergänzt die Kenntnisse aus der Vorlesung Informatik 2. Konkret betrachten wir unterschiedliche Algorithmenparadigmen, also Schemata zum Entwurf von effizienten Algorithmen. Dazu betrachten wir zunächst die bereits bekannten Paradigma inkrementell, Teile-und-Herrsche und gierig und wenden diese auf verschiedene Probleme an. Darauf aufbauend lernen wir Dynamisches Programmieren kennen, sowie die Methoden Backtracking und Branch-and-Bound. Auch betrachten wir ein Paradigma speziell für geometrische Probleme: das Sweepline-Verfahren.
Geometrische Algorithmen
Geometrische Algorithmen umfassen den Entwurf und die Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst einige grundlegende Probleme betrachtet: Das Berechnen der konvexen Hülle einer Punktmenge, der Schnittpunkte einer Menge von Strecken, oder einer Triangulierung eines einfachen Polygons. Anschließend sehen wir Algorithmen zum Berechnen bekannter geometrische Strukturen, wie Voronoi-Diagramme, Delaunay-Triangulierungen und Arrangements. Ebenfalls betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Range-trees, kd-Bäume und Quadtrees. Dabei kommen vor allem drei Arten von Algorithmen zum Einsatz: inkrementell, teile-und-herrsche, und sweep. Manche von diesen treten als randomisierte Algorithmen auf.