Kolmogorov-Komplexität
Inhalt
Algorithmische Informationstheorie ist, wie es G. Chaitin formuliert hat, das Ergebnis davon, Shannons Informationstheorie und Turings Berechenbarkeitstheorie in einen Cocktail Shaker zu tun und kräftig zu schütteln. Die grundlegende Idee ist es, die Komplexität eines Objekts mittels der Größe eines kleinsten Programms, welches das Objekt berechnet, zu messen. Diese Programmgrößenkomplexität, nach seinem Erfinder Kolmogorov-
Komplexität genannt, hat in der Informatik viele Anwendungen; einige sollen in dieser Vorlesung besprochen werden.
Inhalt:
Wahrscheinlichkeitstheorie, Informationstheorie, Codierungstheorie,
Algorithmische Komplexität, Algorithmische Präfixkomplexität,
Algorithmische Wahrscheinlichkeit, Nichtkomprimierbarkeitsmethode,
Resourcenbeschränkte Komplexität, Kommunikationskomplexität
Infos zur Vorlesung
Die erste Vorlesung findet am Mittwoch, den 30.04.08, statt.
Die Veranstaltung fällt am 11.06.08 aus. Dieser Termin wird
nachgeholt.
Literatur
- Li, Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Texts in Computer Science, 2nd ed., Springer Verlag, 1997
- Calude, Information and Randomness, Texts in Theoretical Computer Science. An EATCS Series, Springer Verlag, 2002
- Cover, Thomas, Elements of Information Theory, Wiley Interscience
- Kushilevitz, Nisan, Communication Complexity, Cambridge University Press, 1997
Vorlesungszeiten
Mittwoch, 14:00 Uhr, O27/121