Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

Die erste Sitzung des Seminars mit Einführung und Vergabe der Vortragsthemen findet am Donnerstag dem 14. April statt.

Einführung

Wann ist eine Zahl oder Zahlenfolge zufällig? Diese Frage beschäftigt Mathematiker, Naturwissenschaftler und Philosophen seit langem. Mit Begriffen und Techniken der Informatik lässt sich darauf eine schlüssige Antwort geben: Eine Zahl ist zufällig, wenn sie sich nicht oder nur unwesentlich komprimieren lässt, oder formaler, wenn es kein kurzes Programm (irgendeiner Programmiersprache, sagen wir, C) gibt, dass diese Zahl generiert. Beispielsweise ist die Zahl 100...0 (mit 1.000.000 Nullen) nicht zufällig, genauso wenig die Zahl pi=3.14..., denn beide lassen sich mit kleinen Programmen generieren. Hingegen scheint die Binärzahl 111011000000011011110110101011000011 (per Münzwurf generiert) nur schwer durch ein Programm beschreibar, das kürzer ist als die Zahl selbst.

Andererseits kann man Zahlen, die sich nicht gut komprimieren lassen auch als die Zahlen mit dem höchsten Informationsgehalt interpretieren. Daraus ergeben sich Verbindungen zur klassischen Informationstheorie. In diesem Seminar wollen wir uns die Grundlagen der algorithmischen Theorie des Zufalls (auch bekannt unter den Namen algorithmische Informationstheorie oder Kolmogoroff Komplexität) erarbeiten.

Zeit und Raum

Donnerstags 15 - 17 Uhr im Erwin Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308

Dozent

Prof. Dr. Martin Grohe
Sprechstunde im SS11: Dienstags 14-15 Uhr

Literatur

[M] David J.C. MacKay. Information Theory, Inference, and Learning Algorithms.

Cambridge University Press, 2005.

[LV] Ming Li, Paul Vitányi. An Introduction to Kolmogorov Complexity and Its Applications.

Third Edition, Springer 2008.

[C] Christian S. Calude. Information and Randomness.

Second Edition, Springer 2002.

[DH] Rodney G. Downey, Denis R. Hirschfeldt. Algorithmic Randomness and Complexity.

Springer, 2010.

Vorträge

Vortrag 1 (5. Mai 2011)

Source Coding Theorem [M] Kap. 4 (S.66-89).
Matthias Godau.

 

Vortrag 2 (12. Mai 2011)

Symbol Codes
[M] Kap. 5 (S.90-108).
Wilhelm Becker.

 

Vortrag 3 (26. Mai 2011)

Invariance Theorem (pdf)
[LV] Sec. 2.1 (S.93-107).
Marie Schaeffer.

 

Vortrag 4 (9. Juni 2011)

Incompressibility (pdf)
[LV] Sec. 2.2-2.3 (S.108-127).
Stephan Verbücheln.

 

Vortrag 5 (16. Juni 2011)

Random Sequences (pdf)
[LV] Sec. 2.4 (S.127-136).
Daniel Miehe.

 

Vortrag 6 (23. Juni 2011)

Prefix Complexity
[LV] Sec. 3.1, 3.3 (S.189-197, 202-206).
Maria Tammik.

 

Vortrag 7 (30. Juni 2011)

Algorithmic Information Theory (pdf)
[LV] Sec. 2.8, 3.9 (S.179-185, 229-237).
Bernd Kawald.

 

Vortrag 8 (7. Juli 2011)

The Incompressibility Method (Three Examples, Combinatorics) (pdf)
[LV] Sec. 6.1, 6.3
Stefanie Lowski.

 

Vortrag 9 (14. Juli 2011)

The Incompressibility Method (Kolmogorov Random Graphs, Compact Routing)
[LV] Sec. 6.4, 6.5
Michael Fiedler.