Dozent: Prof. Albers
Termine
Beginn der Vorlesung: 15.10.2009.Beginn des Übungsbetriebs: 27.10.2009.
| VL | Dienstag | 11:00 - 13:00 | RUD 26, 0.307 |
|---|---|---|---|
| Donnerstag | 11:00 - 13:00 | RUD 26, 0.313 | |
| UE | Dienstag | 15:00 - 17:00 | RUD 26, 1.303 |
Leistungsnachweis
- Bestehen der mündlichen Prüfung
- Termin nach Absprache
- Prüfungszulassung: >50% der Übungspunkte + 2 mal Vorrechnen
Zuordnung
- Hauptstudium, Halbkurs oder 1. Teil eines Kurses
- 4 SWS Vorlesung + 2 SWS Übung.
- Theoretische Informatik
Inhalte und Lernziele
Course will be taught in English or German, depending on the audience.Efficient algorithms form a central field in computer science. One research focus over the past years has been the design and analysis of approximation and online algorithms. Here the goal is to develop approximate solutions to problems for which the computation of exact solutions is hard or even impossible.
Online algorithms
Classical algorithm theory assumes that, for a given problem, all data is known in advance. However, in practice, many problems are online, i.e. relevant input arrives incrementally over time. We will design algorithms that can cope with the handicap of not knowing the future. We will study problems in data structuring, the resource management in operating systems, robotics and large networks.Approximation algorithms
Many optimization problems that arise in practice are NP-hard. Assuming that P is not equal NP, these problems cannot be solved optimally in polynomial time. Again, one resorts to approximations. Of particular interest are polynomial time approximation schemes that compute (1+epsilon)-approximations, for any epsilon > 0, in polynomial time. We will study approximation algorithms for classical optimization problems. Emphasis of the course, beside algorithm design, it the careful and thorough mathematical analysis of the various strategies and solutions.Voraussetzungen
- Theoretische Informatik 1
Übungen
- Leitung: Alexander Souza
- Beginn des Übungsbetriebs: 27.10.2009
- Abgabe der bearbeiteten Aufgaben in den Übungsstunden, Rückgabe und Besprechung (mit Vorrechnen) eine Woche später
- Blätter: werden hier veröffentlicht
Nummer Veröffentlichung Abgabe Besprechung Blatt Warm-Up 20.10.09 ohne 27.10.09 
1 20.10.09 27.11.09 3.11.09 2 27.10.09 3.11.09 10.11.09 3 3.11.09 10.11.09 17.11.09 4 10.11.09 17.11.09 24.11.09 5 17.11.09 24.11.09 1.12.09 6 24.11.09 1.12.09 8.12.09 7 1.12.09 8.12.09 15.12.09 8 8.12.09 15.12.09 5.1.10 9 15.12.09 5.1.10 12.1.10 10 5.1.10 12.1.10 19.1.10 11 12.1.10 19.1.10 26.1.10 12 19.1.10 26.1.10 2.2.10 13 26.1.10 2.2.10 9.2.10
Literatur
- A. Borodin und R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, 1998. ISBN 0-521-56392-5
- V.V. Vazirani. Approximation Algorithms. Springer Verlag, Berlin, 2001. ISBN 3-540-65367-8
