Regelmäßig angebotene Veranstaltungen
- Informatik 2 – Algorithmen und Datenstrukturen
- Informatik 3 – Theoretische Informatik
- Algorithmenparadigmen
- Advanced Algorithms
- Computational Geometry (previously 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.
Advanced Algorithms
In the lecture we consider advanced topics in algorithm design and analysis. Specifically we will look at algorithmic approaches to solving NP-hard problems. For this we study approximation algorithms and parametrised algorithms. For both we also need the concept of linear programming, which we also introduce and use to solve these problems. The problems we consider are combinatoric, graph-theoretic and geometric in nature, such as the travelling salesperson problem, knapsack, and clustering.
Computational Geometry
(previously: Geometrische Algorithmen)
Computational Geometry deals with the design and analysis of algorithms and data structures for geometric problems. To this end, we first look at some basic problems, such as calculating the convex hull of a set of points, the intersection points of a set of line segments, or a triangulation of a simple polygon. We then look at algorithms for calculating well-known geometric structures such as Voronoi diagrams, Delaunay triangulations and arrangements. We also look at data structures for efficient queries on geometric data, such as Range Trees, kd-Trees and Quadtrees. Three main types of algorithms are used: incremental, divide-and-conquer, and sweep. Some of these occur as randomized algorithms.