![[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.