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).
DateTopic
23/10/2017Introduction, three field notation, single machine, Smith's rule
30/10/2017Single machine: 1|(prec)|L_max (EDF), 1|prec|f_max (Lawler's algorithm)
06/11/2017Single 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/2017no lecture, no exercise
20/11/2017Q|pmtn|C_max (Horvath, Lam, Sethi 1977), short intro to linear programming
27/11/2017Complexity of scheduling problems
04/12/2017Intro approximation algorithms, P|(prec)|C_max: list scheduling, LPT
11/12/2017Optimal 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/2017P|r_j,pmtn|sum w_jC_j preemptive WSPT 2-approx, conversion technique, alpha-points
08/01/2018randomized algorithms, 1|r_j|sum w_jC_j randomized scheduling by alpha-points
15/01/2018Bin packing, PTAS for makespan minimization
22/01/2018FPTAS for makespan minimization, FPTAS for knapsack
29/01/2018LP 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.

DateTopic
17.10.2017Introduction, Ski-Rental
19.10.2017Deterministic paging algorithms
24.10.2017List Update Problem
26.10.2017Exercise session
31.10.2017No lecture (Day of German Unity)
02.11.2017Makespan minimization on identical parallel machines
07.11.2017Makespan minimization under restricted assignments
09.11.2017Exercises
14.11.2017Randomized Paging Algorithm
16.11.2017Randomized Paging Algorithm, Yao's principle
21.11.2017Exercises
23.11.2017Weighted Completion Time Scheduling
28.11.2017Min Cost Matching
30.11.2017Min Cost Matching
5.12.2017k-server on a line
7.12.2017Lower bound for k-server, Summary of Course
12.12.2017Introduction AGT: games and equilibria
14.12.2017Existence of equilibria and best responses
19.12.2017Efficiency: atomic and non-atomic routing games
21.12.2017Exercise Session
09.01.2018Upper bounds for POA in non-atomic routing
11.01.2018Upper bound on POA in atomic routing and smoothness
23.01.2018Single item auctions
25.01.2018Sponsored search auctions
30.01.2018Exercises
01.02.2018Revenue 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:

Termin: Der Termin für die Vorbesprechung und Themenvergabe ist Mittwoch, 25. Oktober 2017, 14-15 Uhr, im Raum MZH 3150.

Seminarvorträge:

Zeit19.02.2018
Raum MZH 1460
22.02.2018
Raum MZH 5210
 
08:15Bäume
Sandra Wohlers
Binomialkoeffizienten, Zählen von Mengen
Marieke Hoehne
09:15Planare Graphen und Eulersche Formel
Nele Schriefer
Färbungsmethoden
Dominik Dieckmann
10:30Der Satz von Ramsey
Rieke Alpers
Zahlpartitionen, Verteilungen und Catalanzahlen
Eike Blind
11:30Probabilistische Methode
Aljoscha Niemann
Landkarten färben
Timon Hurink
13:30Probabilistische Methode
Pascal Rink
Kryptographie
Nils Stellmacher
14:30Divide-and-Conquer: Sortieren
Miriam Zeyn
Satz von Polya
Tim Alexander Rienits
15:45Rekursionsgleichungen
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:

Assistent: M.Sc. Franziska Eberle

Projektraum: MZH 3240

Plenum: Fr 10-14 in Raum MZH 3150 (Seminarraum)