Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Algorithm Engineering

Lehre am Lehrstuhl für Algorithm Engineering


Bachelor

Vorlesungen im Bachelor finden auf Deutsch statt, falls nicht explizit auf englische Sprache hingewiesen wird.

 

Einführung in die theoretische Informatik (A1, Pflichtvorlesung, seit WS19/20, jährlich im Wechsel mit Prof. Köbler)

Einführung in grundlegende Konzepte der Theoretischen Informatik. Im Zentrum stehen Automatentheorie (endliche Automaten, Kellerautomaten und Turingmaschinen), formale Sprachen (Chomsky-Hierarchie), Berechenbarkeit (Unentscheidbarkeit des Halteproblems, Satz von Rice) und Komplexität (P-vs.-NP-Problem, NP-Vollständigkeit). Daneben werden zum Umgang mit schwer lösbaren Problemen erste algorithmische Ansätze zur approximativen oder randomisierten Lösung von NP-harten Problemen aufgezeigt. (Zitat aus der SPO.)

 

Algorithmen und Datenstrukturen II (W08-16, seit SS 19, jährlich)

Das Modul Algorithmen und Datenstrukturen II erweitert und vertieft die Inhalte des Pflichtmoduls Algorithmen und Datenstrukturen. Auf algorithmischer Seite geht es zum Beispiel um kürzeste Wege, maximale Flüsse, und String Matching. Hinsichtlich Datenstrukturen werden insbesondere Varianten von Heaps, Suchbäumen und Hashing betrachtet. Allgemein liegt der Fokus auf effizienten Algorithmen und den dafür notwendigen Datenstrukturen.

 

Exact Exponential Algorithms (W06-xx, forschungsorientiert, ab WS 21/22, alle zwei Jahre)

This lecture focuses on exponential-time algorithms for solving getting optimal solutions to NP-hard problems. Most of the lecture is about different algorithmic techniques for coping with the intractability of the considered problems and still getting as fast as possible algorithms. The lecture is based on the book by the same title, authored by Fedor V. Fomin and Dieter Kratsch. The lecture is "forschungsorientiert", i.e., it can be taken by Master students and, hence, it will be given in English.

 


Master

All lectures for Master students are given in English.

 

Parameterized Algorithms (Q10-30, since winter term 2017/18, every two years)

Parameterized algorithms are an approach for coping with the intractability of NP-hard computational problems. The central idea therein is to quantify the structure of input instances by one or more parameters. Then, one seeks algorithms that provably perform well when the chosen parameters are sufficiently small. In this way, we can formalize the intuition that typical instances may have plenty of useful structure, which distinguishes them from the worst case.

There is a rich toolbox of algorithmic techniques that will be covered in the lecture. These include branching algorithms, kernelization, iterative compression, color coding, dynamic programming on tree decompositions, inclusion-exclusion, and others. The algorithmic techniques are complemented by lower bound methods that allow to rule out fast parameterized algorithms or that prove optimality of certain running times under appropriate assumptions.

 

Fine-Grained Analysis of Algorithms (Q10-31, summer term 2018, every two years)

For many fundamental polynomial-time solvable problems like Longest Common Subsequence or All-Pairs Shortest Paths there has been no substantial improvement in worst-case running time for decades. The area of Fine-Grained Analysis of Algorithms seeks to explain this lack of improvement. By careful reductions between problems it has been showed that progress for very different problems is often tightly related. E.g. there is a truly subcubic algorithm for All-Pairs Shortest Paths if and only if a bunch of other problems, like Minimum Weight Triangle, have truly subcubic algorithms. Similarly, many problems can only have faster algorithms if there is a breakthrough for solving the Satisfiability problem.

The lecture covers lower bounds for many fundamental problems. We will discuss the required complexity assumptions, e.g., the hypothesis that there are no truly subquadratic algorithms for the Orthogonal Vectors problem. By means of appropriate reductions we then get the lower bounds or even asymptotic equivalence for some problems. Optionally, we will discuss implications for dynamic problems, where input changes over time, and for certain NP-hard problems.

 

Exact Exponential Algorithms (research-oriented, starting winter term 2021/22, every two years)

See above. This Bachelor lecture is labeled "forschungsorientiert" and Master students may take one such lecture from the pool of Bachelor lectures.

 

Efficient Preprocessing (in planning, Q10-xx, tentative start summer term 2022)

Efficient preprocessing refers to the simplification of input instances before starting the actual computation for solving them. Usually the goal is to shrink the input without changing the result of solving it. This is especially useful in the case of NP-hard problems where algorithms may take exponential time to solve inputs, and where polynomial-time preprocessing may therefore greatly reduce the computational effort.

Most of the lecture focuses on the notion of kernelization from parameterized complexity. We will learn how to design and analyze kernelization algorithms for NP-hard problems but also how to prove lower bounds for kernelization. We will also discuss relaxed variants of kernelization such as Turing kernelization and lossy kernelization. Further topics include preprocessing for tractable problems as well as preprocessing under uncertainty.