Informationstheoretische Probleme der
Informatik
SoS 2011
|
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
|
Verbundkomplexität und bedingte Komplexität
|
Folien: Postscript, PDF |
- Eigenschaften der Bedingten Komplexität und der
Verbundkomplexität
- Verbindung zur Kolmogorov-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 Zahlen
- Kraft-Chaitin Algorithmus
- obere und untere Schranken
- Berechenbare endliche Maße auf X*
- Verbundkomplexität und bedingte Komplexität
|
Komplexität unendlicher Wörter
|
Folien: Postscript, PDF |
- Xω als Cantorscher Raum
- Zufällige Reelle Zahlen
- Kolmogorov-Komplexität unendlicher Wörter
|
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
|
