Seminar (Hauptstudium)
Seminar Algorithmische Komplexität und Anwendungen
Prof. Dr. Michael Clausen
Dr. Meinard Müller
Dr. Frank Kurth
Unter algorithmischer Komplexität oder Kolmogorov-Komplexität einer Zeichenkette versteht man anschaulich die Länge eines kürzesten binären Programms, aus dem sich die Zeichenkette effektiv rekonstruieren läßt. Dieser Komplexitätsbegriff hat seine Wurzeln in der Wahrscheinlichkeitstheorie und der Informationstheorie. Beide Theorien hatten zur Diskussion der Frage "Was ist Zufall?" beigetragen. Allerdings hatte sich gezeigt, daß dabei wichtige Aspekte unberücksichtigt geblieben waren. Entscheidende Fortschritte wurden erst erzielt, als man die Berechenbarkeitstheorie und die Theorie der Algorithmen einbezog. In diesem Seminar geht es um eine elementare Einführung in die Theorie der algorithmischen Komplexität und einige ihrer Anwendungen in der Informatik. Neben der Behandlung grundlegender Eigenschaften der Kolmogorov-Komplexität soll insbesondere auch auf Fragestellungen zum Bezug zur Informationstheorie, zur Komprimierbarkeit und zur Ähnlichkeit von Objekten eingegangen werden.
| Zeit, Ort | Di 9-11, SR A121 |
| Beginn | Di, 19.04.2005 (2. Semesterwoche) |
| Vorbesprechung | Do, 03.02.2005, 11 Uhr, SR A413 |
| Teilnehmerzahl | 11 |
| Vortragsmodus | Jeder Teilnehmer hält aufbauend auf entsprechende Literatur einen Einzelvortrag (maximal 60 Minuten), dem sich eine Diskussion anschließt. Weiterhin sind zwei Wochen vor dem jeweiligen Vortrag die Vortragsfolien (hierauf wird besonderen Wert gelegt!) und eine zweiseitige Zusammenfassung des Vortrags vorzulegen. |
| Voraussetzungen | Vordiplom. Es sind sehr gute Kenntnisse der Theoretischen Informatik (Automatentheorie, formale Sprachen und Komplexitätstheorie) nötig. Insbesondere werden auch sehr gute Studierende im dritten Semester, die die Vorlesung "Informatik III" im Wintersemester 2004/05 bei Prof. M. Clausen besucht haben, ermuntert, an diesem Seminar teilzunehmen. |
| Bereich (alte DPO) | A |
| Bereich (neue DPO) | A |
| Prüfungsmöglichkeiten | Kann bei Prof. Clausen als Teil einer A-Prüfung (Umfang: 2SWS) verwendet werden. |
| Email-Kontakt | meinard@iai.uni-bonn.de frank@iai.uni-bonn.de |
| Literatur | Ming Li & Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications Springer-Verlag 1997 Weitere Literaturangaben werden in der Vorbesprechung ausgegeben. |
| Informationen im WWW | http://www-mmdb.iai.uni-bonn.de |
|
Übersicht: alle Semester
Kompaktseminar (BIT-IPEC) Statistische Modelle in der Signalverarbeitung
Seminar Ausgewählte Verfahren des Maschinellen Lernens