![[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 澳门皇冠_皇冠足球比分-劲爆体育eren 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
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. 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)