Informationstheoretische Probleme der
Informatik
Wintersemester 2012/13
|
Vorlesungsinhalt:
|
Folien 4 auf 1: Postscript, PDF |
Folien groß: Postscript, PDF |
| wird laufend ergänzt |
Codes
|
Folien: Postscript, PDF |
- Ordungen auf X*
- Präfixcodes und Bäume
- Mittlere Codewortlänge
- Maximalität und Vollständigkeit von Codes
- Der Vervollständigungssatz von Ehrenfeucht und Rozenberg
- Entscheidungsprobleme und Decodierverzögerung
|
Ein Allgemeines Modell der Datenkompression
|
Folien: Postscript, PDF |
- Kompressions- und Dekompressionsfunktionen
- optimale Funktionen
- Beschreibungskomplexität
|
Kolmogorov-Komplexität von Wörtern
|
Folien: Postscript, PDF |
- optimale partiell-rekursive Funktionen
- Approximierbarkeit der Komplexität
- obere und untere Schranken
|
Präfix-Komplextität
|
Folien: Postscript, PDF |
- Präfix-Algorithmen
- Eigenschaften rekursiv-aufzählbarer Präfix-Codes
- links berechenbare und berechenbare reelle Zahlen
- Kraft-Chaitin Algorithmus
- obere und untere Schranken
- Berechenbare endliche Maße auf X*
|
Literatur:
- Berstel, Jean; Perrin,
Dominique: Theory of Codes,
Academic Press, 1985
- Li, Ming; Vitanyi, Paul: An Introduction to Kolmogorov Complexity
and Its Applications, Springer, 1993
- Blum, Norbert: Einführung in
formale Sprachen, Berechenbarkeit, Informations- und
Lerntheorie, Oldenbourg, München 2007
|