![[Translate to English:]](/fileadmin/user_upload/fachbereiche/fb3/infcon/CSLog/CSLog.png)
Winter 2020/21
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.
Algorithmische Diskrete Mathematik
Wintersemester 2020/21, 9CP
03-M-WP-18
Inhalt
- Einführung in Graphentheorie, kombinatorische und lineare Optimierung
- Graphentheorie: Grundbegriffe, Wege in Graphen, Euler- und Hamiltonkreise, Bäume
- Algorithmische Grundlagen (Kodierungslänge, Laufzeit, Polynomialzeitalgorithmen)
- Spannbäume, Matchings, Netzwerkflüsse und -schnitte (kombinatorische Algorithmen)
- Einblick in lineare Optimierung: Modellierung und Struktur linearer Programme, Polyeder, Optimalitätskriterien, Dualität, Simplex-Algorithmus
- Elemente der Komplexitätstheorie
Dozentin: Prof. Dr. Nicole Megow
Assistent: Dr. Franziska Eberle
Ablauf
Die Vorlesungen und Übungen werden online stattfinden. Um Zugang zu erhalten, melden Sie sich bitte auf StudIP für die Veranstaltung an.
Literatur:
- [KV] Korte, Vygen: Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2012.
- [KN] Krumke, Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer-Vieweg, 2012.
- [CLRS] Corman, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd edition, MIT Press, 2009.
- [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006.
- [AMO] Ahuja, Magnanti, Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
- [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
- [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.
Projekt Match-Up
Wintersemester 2020/21, 12CP
03-MP-902.70
Dieses Projekt befasst sich mit anwendungsbezogenen Fragestellungen, welche sich mithilfe von Matchings modellieren lassen. Ein Matching ist eine graphentheoretische Struktur, welche bestimmten Objekten einen eindeutigen Partner zuordnet. Solche Strukturen finden sich bei einer Vielzahl von interessanten Fragestellungen, welche teilweise stark unterschiedliche Ziele verfolgen. Teils soll lediglich möglichst vielen Objekten ein Partner zugewiesen werden, teils gilt es komplizierteren Anforderungen, wie zum Beispiel Fairness, zu genügen. Strukturelle, graphentheoretische Aussagen über Matchings helfen dabei, effiziente Algorithmen für die Lösunge solcher Fragestellungen zu entwickeln.
Im Laufe des Projekts werden verschiedene reale Probleme (Auktionsmärkte, effizientes Cloud Computing, Schul-/Studienplatzvergabe) theoretisch behandelt. Dies beinhaltet unter anderem Modellierung, Algorithmenentwurf, Implementierung, Evaluation und Visualisierung aber auch das Erlernen von spieltheoretischen und graphentheoretischen Konzepten. Teilnehmer erhalten einen Überblick über aktuelle algorithmische Trends und Fragestellungen im Bereich der Matching Probleme. Eigene Modelle für ausgewählte Probleme werden aufgestellt und Lösungsmethoden entwickelt (Heuristiken, Greedy Algorithmen, etc.). Diese werden implementiert und anhand von Praxis- oder sinnvoll eigenständig generierter Daten evaluiert, das heißt mit Optimallösungen bzw. Relaxationen verglichen. Auch Verbesserungspotential durch (unsichere) Vorhersagen durch machinelles Lernen können experimentell evaluiert werden. Ein großer Spielraum besteht auch für die Entwicklung theoretischer Grundlagen in diesem Bereich: Untersuchung der Problemkomplexität, Design von Algorithmen und Analyse des Worst-case Verhaltens (Approximationsalgorithmen), Untersuchung verschiedener Anforderungen wie Fairness, Kostenminimierung, Profitmaximierung.
Dozentin: Prof. Dr. Nicole Megow
Assistent: Lukas Nölke
Nach einem Semester intensiver Arbeit ist das Projekt nun zu Ende. Auf dieser Webseite berichten die Studenten von ihrem Projekt.
Overview: In this project, we consider application-driven problems that can be modeled using so-called matchings. Various real-world problems are examined theoretically. This includes modeling, algorithm design, implementation, evaluation and visualization but also game-theoretic and graph-theoretic concepts.