Seminar Kolmogorovkomplexität Universität Potsdam, Wintersemester 2009/10

Sprechstunden:

  • Nuria Brede (Raum 1.24): immer, wenn die Tür offen steht
  • Dr. Eva Richter (Raum 1.24): immer, wenn die Tür offen steht

Aktuelles:

  • Der Seminartermin wurde auf freitags, 14 Uhr (Raum 3.04.1.02) verschoben.

Veranstalter:

Dr. Eva Richter, Nuria Brede

Zielgruppe:

ab 3. Semester

Umfang:

2 SWS

Informatikfachzuordnung:

Theoretische Informatik(2000)

Leistungspunkte:

3 benotete Punkte

Zeit:

freitags 14:00-15:30 Uhr

Ort:

3.04.1.02

Beginn:

14.10.2009

Belegung:

Die Belegung erfolgt elektronisch entsprechend den Bestimmungen des Instituts für Informatik.

Zielstellung:

Kolmogorovkomplexität ist der zentrale Begriff der algorithmischen Informationstheorie (AIT). Die Kolmogorovkomplexität eines Objektes ist ein Maß dafür, wie aufwendig es ist, dieses Objekt zu beschreiben. Während der klassische Wahrscheinlichkeitsbegriff es nur erlaubt, über die Zufälligkeit von Prozessen zu sprechen, kann man damit auch charakterisieren, wann ein einzelnes Objekt zufällig ist. Je kleiner seine Kolmogorovkomplexität ist, umso mehr Regelmäßigkeiten besitzt es, je größer sie ist, umso zufälliger ist es.

Die Algorithmische Komplexitätstheorie hat zu Fortschritten in vielen Gebieten der Informatik geführt, beispielsweise in der Informationstheorie, der Komlexitätstheorie und der Signalanalyse. So konnten z.B. mit Hilfe der sogenannten Inkomprimierbarkeitsmethode neue untere Schranken für die Laufzeit bestimmter Algorithmen hergeleitet werden und neue Methoden zur Validierung von Zufallszahlgeneratoren entwickelt werden. Die Konzept und Ergebnisse der AIT sind aber auch relevant für andere Fachgebiete wie Logik, Physik und Biologie.

Im Seminar werden wir uns zunächst mit den wichtigsten Grundlagen der AIT wie Komplexität, Präfixkomplexität und ressourcengebundener Komplexität beschäftigen. Bei den Anwendungen werden wir uns hauptsächlich auf die Analyse von Erwarteten Laufzeiten, die Inkomprimierbarkeitsmethode und induktives Schließen konzentrieren.


Datenschutzerklärung · XHTML · CSS  Letzte Änderung:  tim at-Zeichen cs Punkt uni-potsdam Punkt de,  13.04.2010