Winter 2018/19

Algorithmen auf Graphen

Bachelorvorlesung im Wintersemester 2018/19
6 CP

Graphen sind ein wichtiges Modellierungswerkzeug in der Informatik und in den verschiedensten modernen Anwendungen. Ob wir einen Routenplaner, ein Smartphone oder Facebook nutzen, so stecken im Hintergrund Graphen und effiziente Verfahren, die graphentheoretische Probleme lösen.

Die Vorlesung gibt eine grundlegende Einführung in die Graphentheorie, die Modellierung von Praxisfragestellungen und Algorithmen zum Lösen dieser. Es werden insbesondere kombinatorische Optimierungsprobleme behandelt, die sich graphentheoretisch formulieren lassen und die mit Hilfe von Polynomialzeitalgorithmen optimal gelöst werden können. Dazu gehören bspw. kürzeste Wege, Rundreiseprobleme (Euler- und Hamiltonkreise), minimale Spannbäume, stabile und maximale Matchings und Flüsse in Netzwerken. Desweiteren werden Grundlagen der Komplexitätsheorie (P, NP, Vollständigkeit, Härte) mit Bezug auf Probleme in Graphen (Färben, Clique, TSP, Hamiltonkreis) behandelt.

Dozentin:

• Prof. Dr. Nicole Megow

Assistent:

• Lukas Nölke

Zeit & Raum:

• Mo 10-12 Uhr in Raum MZH 6190 (Vorlesung)
• Di 10-11:30 Uhr in Raum MZH 1090 (Übung 1)

Start:

• Dienstag, 16. Oktober 2018

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.

Ein- und Austragen von Prüfungsterminen in Stud.IP ist möglich bis zum 15. Februar, 12:00 Uhr.

Die Bearbeitung der Übungsblätter erfolgt in Gruppen von 2-3 Studierenden. Die Abgabe erfolgt in der Vorlesung am Montag eine Woche später.

Proofs from the Book - Das Buch der Beweise (engl./dt.)

Proseminar in Winter 2018/19
4 CP

"Paul Erdős liked to talk about The Book, in which God maintains the perfect proofs for mathematical theorems, following the dictum of G. H. Hardy that there is no permanent place for ugly mathematics. Erdős also said that you need not believe in God but, as a mathematician, you should believe in The Book..." Aigner, Ziegler: Proofs from the BOOK.

Martin Aigner and Günter Ziegler published a book "Proofs from the BOOK" with candidates of such perfect proofs that contain brilliant ideas, clever insights, and wonderful observations. Many topics were suggested by Erdős himself, though he died before the book was written. The collection of problems spans number theory, geometry, analysis, combinatorics, and graph theory.

This seminar deals with a selection of topics from "Proofs from the BOOK". The presentations will be held either on a weekly basis or at the end of the semester in one or two full-day colloquia.

Lecturer:

• Prof. Dr. Nicole Megow

Important: Kick-off Meeting: November 29, 2018, 9:00-12:00 in MZH 3150
Every participant gives a 5-min presentation on her/his topic. I give some general comments on how to give a (the final) scientific talk.

The actual presentations will be given on January 29, 2019, in room MZH 3150.

• 09:30 Jan-Moritz Prade: Applications of Euler’s Formula
• 09:30 Francisca Azocar: Cayley´s formula for the number of trees
• 10:30 Jessica Winter: Five-coloring plane graphs
• 10:30 Lucas Klemmer: A 1.5-Approximation for Path TSP
• 11:30 Alexander Lindermayr: Max Cut
• 13:30 Carl Hammann: Two-sided matching with one-sided preferences

The first meeting with all organizational details and an overview of topics took place on
Thursday, October 18, 2018 at 15:00h in room MZH 3150.

Literature:Aigner, Ziegler: Proofs from THE BOOK, 4. Auflage, Springer, 2009.

Shared Mobility: Modelle, Algorithmen und Optimierung

Masterprojekt Winter 2018

Inhalt dieses Projekts ist die Untersuchung von Anforderungen an IT-Unterstützungssysteme im Bereich der Shared Mobility. Es soll ein Überblick über aktuelle algorithmische Trends und Fragestellungen im Bereich der Shared Mobility, insbesondere E-Car-Sharing, gewonnen werden. Wir werden uns mit dem Aufstellen eigener Modelle für ausgewählte Optimierungsprobleme sowie mit der Entwicklung und Implementierung geeigneter Lösungsmethoden beschäftigen. Mögliche Schwerpunkte umfassen insbesondere, aber nicht ausschließlich, Heuristiken, Kombinatorische Optimierungsalgorithmen und Ganzzahlige Lineare Optimierung. Die entwickelten Lösungsverfahren sollen vor allem theoretisch (Worst-Case-Analyse und Kompetitivitätsanalyse) untersucht und ausgewertet werden, aber auch die Evaluation anhand von Praxisdaten ist möglich. Zur Unterstützung bei der Kalibrierung der Optimierungsprobleme sollen Parameter mittels Machine Learning bestimmt werden.

Nach einem Semester intensiver Arbeit ist das Projekt nun zu Ende. Auf dieser Webseite berichten die Studenten von ihrem Projekt.

Lecturers:

• Prof. Dr. Nicole Megow

Assistent:

• Dr. Franziska Eberle

Projektraum: MZH 3240

Plenum: Fr 10-14 in Raum tba