![[Translate to English:]](/fileadmin/user_upload/fachbereiche/fb3/infcon/CSLog/CSLog.png)
Summer 2018
Grundlagen der linearen Optimierung
Vorlesung im Sommersemester 2018
Viele praktische Fragestellungen lassen sich als lineare Optimierungsprobleme formulieren, bspw. in der Logistik (Warenfluss und Planung von Produktionsprozessen) oder in der Finanzwelt (Portfoliotheorie und Risikomanagement). In einem linearen Optimierungsproblem sind sowohl die Zielfunktion als auch die Nebenbedingungen, die die Menge der zulässigen Lösungen beschreiben, linear. Die Vorlesung gibt eine Einführung in die Theorie und Praxis der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Vorlesungsthemen sind u.a.: Modellierung und Struktur linearer Programme, Polyedertheorie, Optimalitätskriterien, Dualität, Simplex-Algorithmus, die Ellipsoid-Methode, Schnittebenenverfahren und die Branch-and Bound Methode.
Dozent:
Assistent:
Zeit & Raum:
- VL: Mo 10-12 Uhr in Raum GW1 A1260 (Megow)
- UE: Di 16-18 Uhr in Raum MZH 6190 (Eberle)
- UE: Do 08-10 Uhr in Raum MZH 1470 (Eberle)
Start: Montag, 9. April 2018
Es werden zwei Übungen angeboten. Eine davon ist speziell für Wirtschaftsinformatiker konzipiert mit verstärktem Anwendungsbezug. Weiteres dazu wird in der ersten Vorlesung am 9.4.2018 besprochen.
Literatur:
- [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
- [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.
- [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006. (studip)
| Datum | Thema |
|---|---|
| 9. April | Einführung, Lineare Optimierungsprobleme, Graphische Repräsentation |
| 16. April | Standardform, Geometrie linearer Programme |
| 23. April | Grundversion des Simplex Algorithus |
| 3. Mai | Degenerierte Basislösungen, Kreiseln des Simplex, Tableau-Methode |
| 7. Mai | Zwei-Phasen Simplex, Laufzeitverhalten |
| 14. Mai | Dualität, Dualitätssätze, Komplementärer Schlupf |
| 28. Mai | Minimale Spannbäume (Prim, Kruskal), Kürzeste Wege (Dijkstra) |
| 4. Juni | Flüsse und Schnitte in Netzwerken, max-flow min-cut Theorem |
| 11. Juni | Ellipsoid Methode, Separieren und Optimieren |
| 18. Juni | Einführung ganzzahliger LPs, Schnittebenenverfahren |
| 25. Juni | Branch and Bound/ and Cut Verfahren |
| 2. Juli | ---entfällt--- |
Approximation Algorithms
Advanced Course in Summer 2018
A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.
Lecturers:
- Prof. Dr. Nicole Megow
- Dr. Ruben Hoeksma
Time & Room:
- Mon 14-16 in room MZH 1090
- Thu 10-12 Uhr in room MZH 1110
Start: Thursday, April 5, 2018
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
- [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
- [V] Approximation Algorithms, Vijay V. Vazirani online version
| Date | Topic |
|---|---|
| 05/04/18 | Introduction, greedy algorithms: k-center problem and load balancing |
| 09/04/18 | Greedy algorithms: scheduling with due dates, set cover problem |
| 12/04/18 | set cover (cont.), metric TSP (double tree and Christofides' Alg.), hardness of approximation for TSP (gap reduction) |
| 19/04/18 | local search, load balancing, k-median |
| 23/04/18 | PTASs, bin packing, load balancing |
| 26/04/18 | PTAS for ETSP |
| 07/05/18 | Linear programming and rounding, scheduling with release dates |
| 14/05/18 | LP rounding, Prize-collecting steiner treex |
| 17/05/18 | LP Duality, Exercise 3 |
| 24/05/18 | Exercise 3, LP-rounding, uncapacitated facility location |
| 28/05/18 | Random sampling, Max SAT, Max CUT |
| 31/05/18 | Randomized rounding, the best of two algorithms, Max SAT |
| 04/06/18 | Scheduling by alpha-points, randomized alpha points, 1|r_j|sum (w_j)C_j |
| 11/06/18 | LP Rounding, prize-collecting steiner tree, uncapacitated facility location, Chernoff bounds, multicommodity flow |
| 14/06/18 | Primal-dual algorithms, set cover, shortest path, knapsack cover |
| 18/06/18 | Primal-dual algorithms, uncapacitated facility location, prize-collecting steiner tree |
| 21/06/18 | Exercise session |
| 25/06/18 | Introduction to online optimization, ski rental, lost cow problem, doubling, list update |
| 28/06/18 | Online list update, summary |
Algorithmen für Big Data
Vorlesung im Sommersemester 2018
In moderner Datenverarbeitung stellt sich zunehmend häfig das Problem, dass große Mengen von Daten anfallen die nur auf günstigen aber langsamen Massenmedien gespeichert werden können. Algorithmisch stellt sich hier das Problem, dass die für eine Berechnung nötigen Daten nicht vollständig in den Hauptspeicher passen. Dieser Kurs beschäftigt sich mit Algorithmen, die trotz solcher Beschränkungen verlässliche Ergebnisse liefern.
Aufbauend auf die im Bachelorstudium erworbenen Kenntnisse soll in diesem Kurs eine solide Basis geschaffen werden, Probleme strukturiert und effizient zu lösen. Ziel des Kurses ist es, Algorithmen kennenzulernen die breite Anwendung in der Praxis finden und ein tiefes Verständnis der verwendeten Mechanismen zu erlangen. Um eine möglichst breite Anwendbarkeit der erlernten Mechanismen und Techniken zu ermöglichen wird in diesem Kurs Wert auf die mathematische Analyse der Algorithmen gelegt.
Dozent: Prof. Dr. Tobias Mömke
Theoretische Informatik 2: Berechenbarkeit und Komplexität
Vorlesung im Sommersemester 2018
Kurzbeschreibung
Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik. Sie besteht aus zahlreichen Teildisziplinen, von denen in dieser Vorlesung hauptsächlich die Theorie der Berechenbarkeit und die Komplexitätstheorie behandelt werden. In der Theorie der Berechenbarkeit geht es um die Definition abstrakter Modelle von Berechnung und um die fundamentale Frage, welche Probleme prinzipiell berechenbar sind und welche nicht. Eine zentrale Rolle spielen dabei Turingmaschinen als elementares Berechnungsmodell, das aber dennoch äquivalent zu komplexeren und praxisnäheren Modellen wie modernen Programmiersprachen ist. Die Komplexitätstheorie betrachtet zusätzlich die zur Berechnung verwendeten Ressourcen wie Laufzeit und Speicherplatz. Eine zentrale Frage ist dann, welche Probleme mit vertretbarem Aufwand berechenbar sind, wobei "vertretbarer Aufwand" meist mit "in polynomieller Zeit" gleichgesetzt wird. Zusätzlich zu den erwähnten Themen werden wir auch einige in Theoretische Informatik 1 offen gebliebene Fragen aus dem Gebiet der formalen Sprachen klären und beispielsweise ein Automatenmodell fär kontextsensitive Sprachen und Typ-0-Sprachen angeben. Im letzteren Fall sind das Turingmaschinen, was eine direkte Verbindung zwischen formalen Sprachen und der Theorie der Berechenbarkeit liefert.
Skript und Folien
... werden zu gegebener Zeit in Stud.IP zugänglich gemacht.
Auf Inhalte, die über das Skript hinausgehen, wird in der Vorlesung explizit hingewiesen. Diese sollten dann mitgeschrieben werden. Hier etwas zum Thema: wie liest man einen mathematischen Text?
Organisation der Tutorien
Nähere Infos zu Terminen, Tutor_innen und Einschreibung gibt es zu gegebener Zeit auf Stud.IP.
Aufgabenblätter
An dieser Stelle In Stud.IP wird jede Woche ein Aufgabenblatt zur Verfügung gestellt. Die Aufgaben werden in Kleingruppen von 2–3 Personen bearbeitet und in den Tutorien gemeinsam besprochen.
Dozent: Prof. Dr. Tobias Mömke
Zeit & Raum: Montags 14:00 – 16:00 in Raum NW1 H 1 - H0020
Literatur:
- Juraj Hromkovič, Theoretische Informatik, Springer Verlag, 2011
- Michael Sipser, Introduction to Theory of Computation. Cengage Learning, 2013 (3rd edition)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, 2011 (3. Auflage)
- Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
- Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999
Advanced Algorithms (engl./dt.)
Master Seminar in Summer 2018
4 CP
In this seminar, we will read (more or less) recent papers in theoretical computer science, particularly, on efficient algorithms, online and approximation algorithms, scheduling, algorithmic game theory/mechanism design and combinatorial optimization under uncertainty. The papers may be less recent if there is interesting follow-up work. Each student gives a presentation (45 min.) followed by a discussion. These presentations will be given in one or two days at the end of the semester. The exact dates will be discussed during the organizational meeting on April 6.
Lecturer: Prof. Dr. Nicole Megow
Important: The first meeting with all organizational details and an overview of topics took place on Friday, April 6, 2018 at 09:00 in room MZH 3150.
If you are interested in this seminar then send me an email as soon as possible.
P vs NP Survival Guide
Master Seminar im Sommersemester 2018
4 ECTS
Das Seminar beschäftigt sich mit dem Thema P vs NP. Die Frage ob P = NP gilt ist äquivalent zur Frage, ob man in einem Straßennetzwerk einen Weg finden kann der alle Städte genau einmal besucht oder zur Frage, ob man in einem Netzwerk von Freunden eine Zahl k von Personen finden kann, die sich alle gegenseitig kennen.
Der fundamentale Charakter dieses bislang ungelösten Problems hat dazu geführt, dass das Clay Mathematics Institute einen Preis von USD 1 000 000 für die Lösung dieses Problems ausgeschrieben hat.
Auf dem Weg dieses Problem zu lösen gibt es jedoch viele Fallen und Sackgassen. Dies führt dazu, dass gelegentlich Nachrichten zur vermeintlichen Lösung dieses Problems in Zeitungen veröffentlicht werden. Bislang war keiner dieser Ansätze korrekt.
In diesem Seminar geht es darum, ein besseres Verständnis zu diesem Problem zu erarbeiten. Eines der Ziele ist es, zumindest einige Fallen als solche zu identifizieren um Fehler zu vermeiden. Es geht um Themen wie zum Beispiel:
- Welche Art von Problemen kann man effizient lösen?
- Gibt es ähnliche Klassen von Problemen bei denen eine Lösung bekannt ist?
- Wie verifiziert man, ob ein P vs NP Beweis korrekt sein kann? Welche Lösungsansätze kann man ausschließen?
- Ist es möglich dass die Frage ob P vs NP unentscheidbar ist?
Dozent: Prof. Dr. Tobias Mömke
Seminarvorträge:
| Zeit | 26.07.2018 Raum MZH 5210 |
|---|---|
| 09:15 | NP-Schwere Beweise Yannis Rohloff |
| 10:15 | Schäfer's Dichotomy Leif Sabellek |
| 11:30 | Natural Proofs Tobias Dellert |
| 13:30 | PCP Theorem (Probabilistically Checkable Proofs) Jens Schlöter |
| 14:30 | Kolmogorov Komplexität und Verifiable Mathematics Maurice Funk |
Interessante Links
Literaturgrundlage:
- Scott Aaronson: P=?NP. Electronic Colloquium on Computational Complexity (ECCC) 24: 4 (2017)
Shared Mobility: Modelle, Algorithmen und Optimierung
Bachelorprojekt Winter/Sommer 2017/18
für Studiengänge Informatik und Wirtschaftsinformatik
Inhalt dieses Projekts ist die Untersuchung von Anforderungen an IT-Unterstützungssysteme im Bereich der Shared Mobility. Es werden Modelle, Algorithmen und Optimierungsmethoden für Fragestellungen in Bike- und Car-Sharing Systemen entwickelt, implementiert, evaluiert und visualisiert.
Nach knapp zwei Semestern intensiver Arbeit ist das Projekt nun zu Ende. Auf dieser Webseite berichten die Studenten von ihrem Projekt.
Lecturers:
- Prof. Dr. Nicole Megow
- Prof. Dr. Tobias Mömke
Assistent:
Projektraum: MZH 3240
Plenum: Fr 10-14 in Raum MZH 3150 (Seminarraum)
Hands-on Tutorial on Optimization (engl./dt.)
Block course in Summer 2018
3 CP
A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems.
We develop a toolkit to model real-world problems as (discrete) linear programs. Some examples of basic optimization problems that are part of this toolkit are scheduling, packing, matching, routing, and network-design. We also explore different ways to find integer solutions such as cutting planes, Branch & Bound, and column generation.
Based on this theoretical background, we focus on translating practical examples into mixed-integer linear programs. We learn how to use professional solvers (such as CPLEX, Gurobi, and FICO Xpress) and tailor the solution process to certain properties of the problem.
Throughout the course, we concentrate on modeling and solving practical problems with some theory parts in between.
Lecturers:
- Prof. Dr. Nicole Megow
- Dr. Franziska Eberle
- Dr. Ruben Hoeksma
This course consists of two phases:
Phase 1:
- One week of lectures and practical labs during Mon Sept 24 – Fri Sept 29 from 9:30 to 12:30 and from 13:30 to 17:30.
Phase 2:
- One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented at the latest in the first week of the winter semester 2018/2019.
There are no prerequisites except some basic programming skills to participate.