Winter 2022/23

Algorithmentheorie

Wintersemester 2022/23, 3 SWS, 4,5 CP
03-BE-699.11 (03-IBGT-AT) 

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

Dozentin:  Prof. Dr. Nicole Megow

Übungen: Alexander Lindermayr, Jens Schlöter 

StudIP: Link 

Algorithms and Uncertainty

Wintersemester 2022/23, 6 or 9CP
03-IMAT-AU (03-ME-602.99c), StudIP

A key assumption of many powerful optimization methods is that all the data is fully accessible from the beginning.

However, from the point of view of many real-world applications (e.g., in logistics, production or project planning, cloud computing, etc.) this assumption is simply not true. Large data centers allocate resources to tasks without knowledge of exact execution times or energy requirements; transit times in networks are often uncertain; or, parameters such as bandwidth, demands or energy consumption are highly fluctuating. The current trend of data collection and data-driven applications often amplifies this phenomenon. As the amount of available data is increasing tremendously due to internet technology, cloud systems and sharing markets, modern algorithms are expected to be highly adaptive and learn and benefit from the dynamically changing mass of data. 

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 optimization, 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 robust optimization or stochastic optimization. In robust optimization, the aim is to optimize the worst-case of all possible realizations of the input data. Hence, this model is rather conservative. In stochastic optimization however, the algorithms work with the assumption that data is drawn from some probability distribution known ahead of time and typically the goal is to optimize the expected value.

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 error-prone predictions in order to improve guaranteed algorithms.

Lecturers: Prof. Dr. Nicole MegowDr. Felix Hommelsheim

Format: lectures twice a week with integrated, interactive exercise sessions (6 CP), additional seminar style course work (9 CP)

Examination: individual oral exam; as admission to the oral exam it is mandatory to present solutions in the exercise session at least twice during the term.
 

Projekt LastMILE

Last Mile Logistics: Modelle, Algorithmen und Optimierung

Wintersemester 2022/23 (Oktober 22 - März 23), 15CP
03-IBPJ-LAMI Bachelorprojekt für die Studiengänge Informatik und Wirtschaftsinformatik

Dieses Projekt befasst sich mit anwendungsbezogenen Fragestellungen, welche in der „Logistik der letzten Meile“, Last Mile Logistics, auftauchen. Hierbei werden verschiedene Problemstellungen betrachtet wie z.B. Vehicle Routing, Inventory Management, sowie Scheduling- und Zuordnungsprobleme. Zudem sollen neue, innovative Ideen insbesondere für das Last-Mile Routing entwickelt werden. All diese Problemstellungen sollen theoretisch sowie praktisch bearbeitet werden: Dies beinhaltet unter anderem Modellierung, Algorithmenentwurf, Implementierung, Evaluation und Visualisierung aber auch spieltheoretische und graphentheoretische Konzepte. Oft werden dabei klassische Optimierungsverfahren wie Heuristiken, ILP-Solver oder Approximationsalgorithmen benutzt, jedoch sollen auch neue Konzepte wie Lernverfahren (Machine Learning) und Vorhersagen integriert werden.

Dozenten:  Prof. Dr. Nicole Megow und Felix Hommelsheim

Studip  Link for details

Overview (engl.): In this project, we consider application-driven problems that arise in the context of Last-Mile Logistics. Therein we will consider various real-world problems, such as Vehicle Routing, Inventory Management, as well as Scheduling and Assignment problems. Furthermore, new innovative ideas for Last-Mile Routing should be developed and problems arising from these ideas will be considered. All these problems will be considered theoretically and practically: This includes modeling, algorithm design, implementation, evaluation and visualization but also game-theoretic and graph-theoretic concepts. We will apply classical optimization methods such as heuristics, ILP-solver or approximation algorithms, but also modern concepts such as machine learning or predictions.

Updated by: Megow