Dozent: Dr. Deryk Osthus
Termine
Beginn der Vorlesung: 21.10.2003| VL | Dienstag | 13:00 - 15:00 | (RUD 26, 0.313) |
|---|---|---|---|
| Donnerstag | 13:00 - 15:00 | (RUD 26, 1.305) |
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Voraussetzungen
- Grundstudium
Inhalte und Lernziele
Diese Vorlesung gibt eine Einführung in das Gebiet der Kombinatorik und ihrer Anwendungen in der Informatik. Untersuchungsgegenstände sind endliche Mengen, Boolesche Funktionen und Graphen. Anwendungsbiete sind zum Beispiel Kodierungstheorie, Informationstheorie und kombinatorische Optimierung.
Typische Fragestellungen sind dabei zum Beispiel:
- Auf wieviele Arten kann man n Objekte auf m Behälter verteilen?
- Gegeben eine Boolesche Funktion, wieviele AND, OR und NOT
Operationen werden benötigt, um sie als Formel darzustellen?
-Wie gute Codes lassen sich aus einer gegebenen Menge von Elementen
konstruieren?
Die ersten zwei Kapitel gibt es als Skript von David Damm.
Empfohlene Literatur
unter anderem- , Extremal Combinatorics with applications in Computer Science, Springer, 2001.
English