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).
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.
C.Fermüller