Winter 2022/23
Algorithmentheorie
Wintersemester 2020/21, 4SWS, 6CP
03-BB-602.02
Algorithmen bilden eine der wichtigsten Grundlagen der
Informatik. Anschaulich beschreibt ein Algorithmus eine Vorgehensweise
um ein Problem zu lösen. Somit bilden Algorithmen eine Grundlage der
Programmierung, sind aber unabhängig von der konkreten
Programmiersprache und Umsetzung. Algorithmen sind so vielfältig wie
ihre Anwendungen, darum ist es umso wichtiger die fundamentalen
Prinzipien des effizienten Algorithmenentwurfs und in den wichtigsten
Problembereichen die grundlegenden Lösungsverfahren zu kennen.
Die Vorlesung hat zum Ziel diese fundamentalen Prinzipien des
Algorithmenentwurfs zu vermitteln. Die Prinzipien werden anhand
klassischer Algorithmen für wichtige Probleme illustriert und
eingeübt. Auf der theoretischen Seite werden die Grundlagen
abstrakter Maschinenmodelle, formale Korrektheitsbeweise und
Laufzeitanalyse vermittelt. Das erworbene Wissen ermöglicht es den
Studierenden für ein gegebenes algorithmisches Problem verschiedene
Lösungsansätze bezüglich ihrer Effizienz zu beurteilen, den am besten
geeigneten Ansatz zur Lösung auszuwählen und seine Korrektheit zu
beweisen.
• Algorithmenparadigmen: Greedy, Divide-and-Conquer, Dynamische Programmierung
• Sortierverfahren
• Grundlegende Begriffe der Graphentheorie
• Graphenprobleme: Kürzeste-Wege, minimale aufspannende Bäume, maximale Netzwerkflüsse
Dozenten: Prof. Dr. Nicole Megow
Prof. Dr. Sebastian Siebertz
Die Veranstaltung findet online asynchron statt. Der online
Einführungstermin in der ersten Veranstaltungswoche steht noch nicht fest.
Algorithms and Uncertainty
Master Course in Summer 2020
03-ME-602.99c, 6 ETCS points
Description:
A key assumption of all basic algorithm design classes is that all the data is fully accessible at the start of the computation.
However, from the point of view of many real-world applications of computer science (such as the stock market, cloud scheduling, network design), this assumption is simply not true. In the above examples, our knowledge of the current data is only partial or based on historical estimates.
The class Algorithms and Uncertainty will teach students about the most common models of such uncertain data and how to design and analyze efficient algorithms in these models.
Specifically, we will cover the theory of online algorithms, where the input arrives without any prior information (such as network packets arriving to a router) and also needs to be processed immediately, before the next piece of input arrives. This model is best suited for analyzing critical networking and scheduling systems where devices and algorithms must perform well even in the worst-case scenario.
In the cases where previous history can be used to model the upcoming data, we often employ stochastic optimization. There, the algorithms work with the assumption that data is drawn from some probability distribution known ahead of time.
Nowadays, another source of information is often available: machine learning algorithms can generate predictions which are accurate most of the time. However, there is no guarantee on the quality of the prediction, as the current instance may not be covered by the training set. This statement motivated a very recent research domain that will be covered in this course: how to use untrusted predictions in order to improve guaranteed algorithms.
The course will be taught in English. The course is accessible to any student with basic algorithm classes and basic knowledge of graph theory.
Lecturers:
Dr. Martin Böhm
Prof. Dr. Nicole Megow
Dr. Bertrand Simon
Stud-IP Link: Algorithms and Uncertainty
First lecture: Lecture times and location will be specified in April (The summer semester starts on April 14.)