Informationstheoretische Probleme der
Informatik
SoS 2007
|
Vorlesungsinhalt:
|
Folien (Postscript 4 auf 1)
(komplett) |
Folien (Postscript
groß) (komplett) |
| wird laufend ergänzt |
Codes
|
Folien (Postscript 4 auf 1) |
- 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 4 auf 1) |
- Kompressions- und Dekompressionsfunktionen
- optimale Funktionen
- Beschreibungskomplexität
|
Kolmogorov-Komplexität von Wörtern
|
Folien (Postscript 4 auf 1) |
- optimale partiell-rekursive Funktionen
- Approximierbarkeit der Komplexität
- obere und untere Schranken
|
Verbundkomplexität und bedingte Komplexität
|
Folien (Postscript 4 auf 1) |
- Eigenschaften der Bedingten Komplexität und der
Verbundkomplexität
- Verbindung zur Kolmogorov-Komplexität
- obere und untere Schranken
|
Präfix-Kompextität
|
Folien (Postscript 4 auf 1) |
- 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 4 auf 1) |
- X^{\omega} 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
|
