Dozent: Amin Coja-Oghlan
Termine
Beginn der Vorlesung: 18.10.2002| VL | Dienstag | 09:30 - 11:00 | (RUD 25, 3.113) |
|---|---|---|---|
| Freitag | 09:15 - 10:45 | (RUD 25, 3.113) |
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Voraussetzungen
- Grundstudium (Informatik oder Mathematik)
- Graphen und Algorithmen 1st als Ergänzung sinnvoll
- Die erforderlichen Hilfsmittel aus der Wahrscheinlichkeitstheorie werden in der Vorlesung behandelt.
Inhalte und Lernziele
Zwei verschiedene Aspekte der Thematik "Algorithmen und Zufall" sind Inhalt dieser Vorlesung: In Randomisierten Algorithmen einerseits dient der Zufall als algorithmisches Konzept. Algorithmen, die von "Münzwürfen" gebrauch machen, bieten oft eine bessere Laufzeit oder sind einfacher zu analysieren als deterministische Algorithmen. Die Probabilistische Analyse andererseits hat das Ziel, "harten" (z.B. NP-schweren) Problemen beizukommen. Der Ansatz ist, schnelle Algorithmen zu entwickeln, die zwar nicht für alle Eingaben gut funktionieren, aber doch für "typische" Eingaben.
Folgende Themen sollen in der Vorlesung behandelt werden:- Randomisierte Algorithmen: Einführung
- Randomisiertes Routing
- Martingal-Methoden
- Randomisiertes Runden für lineare oder semidefinite Programme
- Probabilistische Analyse: Einführung
- Analyse von Heuristiken (z.B. Greedy-Methoden) auf "typischen" Eingaben
- Spektraltechniken
- Umgang mit schwer approximierbaren Grössen: Cliquenzahl, Chromatische Zahl etc.
- ...
Empfohlene Literatur
- , Randomized algorithms, Cambridge, 1995.
- , The probabilistic method, Wiley, 2001.
- , The solution of some NP-hard problems in polynomial expected time, J. Algorithms 10 (1989) 451-489.
- , Algorithmic theory of random graphs, Random Structures and Algorithms 10 (1997) 5-42.
- , Approximation algorithms, Springer, 2001.
- , Random graphs, Cambridge, 2002.
- , Random graphs, Wiley, 2001.
- , An introduction to probability theory and its applications, Wiley, 1968.
- , Einführung in Graphen und Algorithmen
English