[ Lehrveranstaltungen 185/2 ]     [ AG Theoretische Informatik und Logik ]     [ Fachbereich Informatik ]     [ Technische Universität Wien ]

2.0 VU AK der Theoretischen Informatik 2 (185.245, WS 2004)

Thema:
Information und Komplexität
Eine Einführung in die Kolmogorov-Komplexität


Letzte Änderung: 7.2.2005 (CF)

Lehrveranstaltungsleiter: Christian Fermüller

Diese Lehrveranstaltung ist Teil der Magisterstudien Computational Intelligence und Software Engineering & Internet Computung (jeweils Wahllehrveranstaltung im Bereich Theoretische Informatik) sowie Teil des Diplomstudiums Informatik (Wahlfach Artificial Intelligence und Theoretische Informatik).


*** Aktuelles ***

  • Vorlesungsunterlagen (Kopien aus An Introduction to Kolmogorov Complexity and Its Applications von Ming Li und Paul Vitanyi) liegen nun im Sekretriat der AG Theoretische Informatik und Logik, Institut 185 zu den Sekretariatszeiten (Mo 10:30-12:30, Di 11:00-12:00, Do 11:00-12:00) für alle VU-Teilnehmer auf. (Ausserhalb der Sekretariatszeiten ist eine Abholung der Kopien nur nach Vereinbarung per Email an C.Fermüller möglich.)

  • Was ist Kolmogorov-Komplexität?

    Wieviel Information steckt in einem konkreten Objekt?
    (z.B., einem String, einem Programmtext, einem Baum, einer Matrix, ...)?

    Überraschenderweise können weder die klassische (Shannon'sche) Informationstheorie noch übliche Varianten der Komplexitätstheorie diese Frage sinnvoll direkt beantworten!

    Der berühmte russische Mathematiker Andrei Nikolaevich Kolmogorov schuf eine überzeugende mathematische Basis zu folgender naheliegenden Idee:

    Die Komplexität eines Objekt ist die Länge der kürzesten eindeutigen Beschreibung des Objekts.

    Warum und wie diese Idee `funktioniert' und wie sie zu einer sehr eleganten und enorm anwendungsreichen Teildisiziplin der theoretischen Informatik führt, wird Thema dieser VU sein.


    Unterlagen

    Folienkopien:

    Lösungen zu Übungsaufgaben:


    Ein Auswahl relevanter Links:


    Valid HTML 4.01! Viewable With Any Browser C.Fermüller