![[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
fu?r Studienga?nge Informatik und Wirtschaftsinformatik
Inhalt dieses Projekts ist die Untersuchung von Anforderungen an IT-Unterstu?tzungssysteme im Bereich der Shared Mobility. Es werden Modelle, Algorithmen und Optimierungsmethoden fu?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.