![[Translate to English:]](/fileadmin/user_upload/fachbereiche/fb3/infcon/CSLog/CSLog.png)
Winter 2017/18
Scheduling Theory
Course in Winter 2017/18
6 ECTS
Scheduling involves the timely allocation of tasks to scarce resources with the objective to minimize some cost function. Such problems appear in various applications, e.g., in production planning, logistics, project management, or when operating computing systems. This lecture will cover: a classification of scheduling models, complexity of scheduling problems, the design and analysis of exact and approximation algorithms, single and parallel machine models, flow shop and open shop problems. The focus lies on the design and mathematical analysis of algorithms using combinatorial techniques, dynamic programming and linear programming.
Lecturer: Prof. Dr. Nicole Megow
Assistent: Dr. Franziska Eberle
Time & Room:
- Lecture: Mon 14-16 in room MZH 1110 (Megow)
- Exercise: Mon 16-18 in room MZH 1110 (Eberle)
Begin:
- The first lecture is on Monday, October 23, 2017.
- The first exercise class is on Monday, October 30, 2017 and starts at 16:00 (sharp).
| Date | Topic |
|---|---|
| 23/10/2017 | Introduction, three field notation, single machine, Smith's rule |
| 30/10/2017 | Single machine: 1|(prec)|L_max (EDF), 1|prec|f_max (Lawler's algorithm) |
| 06/11/2017 | Single machine: 1||sum U_j (Moore Hodgson), parallel machines: P||sum C_j (SPT), R||sum C_j (matching), P|pmtn|C_max (McNaughton Wrap around) |
| 13/11/2017 | no lecture, no exercise |
| 20/11/2017 | Q|pmtn|C_max (Horvath, Lam, Sethi 1977), short intro to linear programming |
| 27/11/2017 | Complexity of scheduling problems |
| 04/12/2017 | Intro approximation algorithms, P|(prec)|C_max: list scheduling, LPT |
| 11/12/2017 | Optimal poly-time alg for P2|prec,p_j=1|C_max, fast single machine relaxation for P|r_j,pmtn|sum w_jC_j |
| 18/12/2017 | P|r_j,pmtn|sum w_jC_j preemptive WSPT 2-approx, conversion technique, alpha-points |
| 08/01/2018 | randomized algorithms, 1|r_j|sum w_jC_j randomized scheduling by alpha-points |
| 15/01/2018 | Bin packing, PTAS for makespan minimization |
| 22/01/2018 | FPTAS for makespan minimization, FPTAS for knapsack |
| 29/01/2018 | LP based algorithms (P||sum w_jC_j) |
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
- M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2012.
- J. Y.-T. Leung. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC, 2004.
- F. Jaehn and E. Pesch: Ablaufplanung. Einführung in Scheduling. Springer, 2014.
Optimizing with Uncertainty: An Introduction to Online Algorithms and Algorithmic Game Theory
Course in Winter 2017/18
Traditional optimization theory assumes complete knowledge of information. However, in reality, input might be uncertain - they might be incomplete, revealed over time or might involve choices made by selfish players. In this course, we shall deal with solving optimization problems under such uncertainties.
In the first part of the course, we shall develop the notion of online computation - an area which deals with developing algorithms that make decisions on the basis of input that is built over time. We shall introduce formal models of measuring the efficiency of such algorithms and develop algorithms for various flavors of online optimization problems. These problems find applications in areas such as planning, logistics, communication or machine learning.
In the second part, we learn to handle situations where we are not all-powerful, but instead have to deal with other decision makers as well. We learn to design mechanisms that take into account the actions of these strategic players and how to analyze the performance of these mechanisms. We encounter this type of problems in transportation and data networks, (online) auctions, and assigning students to schools.
Lecturers:
- Dr. Ruben Hoeksma
- Dr. Syamantak Das
Time & Room:
- Tue : 14:00-16:00 ; MZH 1450
- Thu : 16:00-18:00 ; MZH 1100
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
- [1] Allan Borodin, Ran El-Yaniv. Online Computation and Competitive Analysis,, Cambidge University Press
- [2] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory
(Go to "Resources" → "General Resources" → "Algorithmic Game Theory" → "Algorithmic Game Theory") - [3] Jason D. Hartline. Mechanism Design and Approximation
- Additional resources on Online Optimization
- [4] Sven Krumke and Clemens Thielen, Introduction to Online Optimization[pdf]
- [5] Lecture Notes by Sussane Albers
| Date | Topic |
|---|---|
| 17.10.2017 | Introduction, Ski-Rental |
| 19.10.2017 | Deterministic paging algorithms |
| 24.10.2017 | List Update Problem |
| 26.10.2017 | Exercise session |
| 31.10.2017 | No lecture (Day of German Unity) |
| 02.11.2017 | Makespan minimization on identical parallel machines |
| 07.11.2017 | Makespan minimization under restricted assignments |
| 09.11.2017 | Exercises |
| 14.11.2017 | Randomized Paging Algorithm |
| 16.11.2017 | Randomized Paging Algorithm, Yao's principle |
| 21.11.2017 | Exercises |
| 23.11.2017 | Weighted Completion Time Scheduling |
| 28.11.2017 | Min Cost Matching |
| 30.11.2017 | Min Cost Matching |
| 5.12.2017 | k-server on a line |
| 7.12.2017 | Lower bound for k-server, Summary of Course |
| 12.12.2017 | Introduction AGT: games and equilibria |
| 14.12.2017 | Existence of equilibria and best responses |
| 19.12.2017 | Efficiency: atomic and non-atomic routing games |
| 21.12.2017 | Exercise Session |
| 09.01.2018 | Upper bounds for POA in non-atomic routing |
| 11.01.2018 | Upper bound on POA in atomic routing and smoothness |
| 23.01.2018 | Single item auctions |
| 25.01.2018 | Sponsored search auctions |
| 30.01.2018 | Exercises |
| 01.02.2018 | Revenue maximizing auctions |
Effiziente Algorithmen
Vorlesung im Wintersemester 2017/18
Algorithmen bilden die Basis für die Programmierung von Computern. Die Erfahrung zeigt dass in vielen realen Anwendungen die Änderung der benutzten Algorithmen eine scheinbar unlösbare Aufgabe zu einer in Millisekunden lösbaren Aufgabe machen kann.
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
Zeit & Raum:
- Vorlesung: Montags 10:00 – 12:00 in room MZH 1460
- Übung: Mittwochs 16:00 – 18:00 in room MZH 6210; On November 1 in SFG 2070
Beginn: Die erste Vorlesung findet am Montag, den 23.10.2017 statt.
Literatur:
- Kleinberg, Tardos. Algorithm Design. Pearson, 2006.
Theoretische Informatik 1: Endliche Automaten und formale Sprachen
Vorlesung im Wintersemester 2017/18
Kurzbeschreibung
Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik und stellt eine wichtige Grundlage für viele andere Teilgebiete der Informatik dar. Sie besteht aus mehreren Teildisziplinen, von denen in dieser hauptsächlich die Automatentheorie und die Theorie der formalen Sprachen behandelt werden. Dabei stehen sogenannte Wörter im Mittelpunkt, mit deren Hilfe viele Objekte der Informatik wie z.B. Programme und verschiedene Datenstrukturen beschrieben werden können. Eine formale Sprache ist dann einfach eine Menge von Wörtern. Wir studieren verschiedene Mittel, um formale Sprachen zu beschreiben (insb. Automaten und Grammatiken), untersuchen Eigenschaften von wichtigen Klassen formaler Sprachen und studieren zentrale algorithmische Probleme, die im Zusammenhang mit Wörtern und formalen Sprachen stehen.
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 hier.
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:
- Vorlesung: Montags 14:00 – 16:00 in Raum HS 1010 (Kleiner Hörsaal)
- Montags 16:00 – 18:00, wöchentlich, MZH 1470
- Montags 16:00 – 18:00, wöchentlich, MZH 4140
- Montags 16:00 – 18:00, wöchentlich, GW1 A1260
- Montags 16:00 – 18:00, wöchentlich, GW1 C1070
- Dienstags 08:00 – 10:00, wöchentlich, MZH 1450
- Dienstags 08:00 – 10:00, wöchentlich, MZH 1100
- Dienstags 08:00 – 10:00, wöchentlich, MZH 1100
- Dienstags 08:00 – 10:00, wöchentlich, MZH 1110
- Dienstags 08:00 – 10:00, wöchentlich, GW1 A1260
- Mittwochs 10:00 – 12:00, wöchentlich, MZH 6210
- Mittwochs 10:00 – 12:00, wöchentlich, MZH 1460
- Mittwochs 10:00 – 12:00, wöchentlich, GW1-HS H1000
- Mittwochs 10:00 – 12:00, wöchentlich, MZH 5210
Beginn: Die erste Vorlesung findet am Montag, den 16.10.2017 statt.
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
Diskrete Strukturen: Kombinatorik, Graphen, Färbungen
Bachelor Seminar im Wintersemester 2017/18
4 ECTS
Das Seminar behandelt grundlegende Fragestellungen, Techniken und Resultate zu diskreten Strukturen. Zu den Themen gehören Kombinatorik, Induktion, Graphen, Bäume und Färbungen. Beispiele für Fragestellungen sind:
- Wie färbt man eine Landkarte mit wenigen Farben so dass benachbarte Länder verschiedene Farben haben?
- Wie erhält man eine maximale Anzahl von Paaren (z.B. Zuordnungen von Arbeitnehmern und Arbeitgebern)?
- Welche grundlegenden Möglichkeiten gibt es, kombinatorische Beweise zu führen?
- Wie sortiert man eine Menge von Zahlen?
- Wie zählt man Bäume?
Dozenten:
- Prof. Dr. Nicole Megow
- Prof. Dr. Tobias Mömke
Termin: Der Termin für die Vorbesprechung und Themenvergabe ist Mittwoch, 25. Oktober 2017, 14-15 Uhr, im Raum MZH 3150.
Seminarvorträge:
| Zeit | 19.02.2018 Raum MZH 1460 | 22.02.2018 Raum MZH 5210 |
|---|---|---|
| 08:15 | Bäume Sandra Wohlers | Binomialkoeffizienten, Zählen von Mengen Marieke Hoehne |
| 09:15 | Planare Graphen und Eulersche Formel Nele Schriefer | Färbungsmethoden Dominik Dieckmann |
| 10:30 | Der Satz von Ramsey Rieke Alpers | Zahlpartitionen, Verteilungen und Catalanzahlen Eike Blind |
| 11:30 | Probabilistische Methode Aljoscha Niemann | Landkarten färben Timon Hurink |
| 13:30 | Probabilistische Methode Pascal Rink | Kryptographie Nils Stellmacher |
| 14:30 | Divide-and-Conquer: Sortieren Miriam Zeyn | Satz von Polya Tim Alexander Rienits |
| 15:45 | Rekursionsgleichungen Sebastian Genske | Matching Colin Heathcote |
Literaturgrundlage:
- Lovász, Pelikan, Vesztergombi: Diskrete Mathematik, Springer 2005
- Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg-Teubner, 4. Auflage, 2011
- Steger: Diskrete Strukturen 1, Springer, 2002
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. Mehr Informationen befinden sich hier.
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: M.Sc. Franziska Eberle
Projektraum: MZH 3240
Plenum: Fr 10-14 in Raum MZH 3150 (Seminarraum)