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 BredeZielgruppe:
ab 3. SemesterUmfang:
2 SWSInformatikfachzuordnung:
Theoretische Informatik(2000)Leistungspunkte:
3 benotete PunkteZeit:
freitags 14:00-15:30 UhrOrt:
3.04.1.02Beginn:
14.10.2009Belegung:
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.
