Vorlesung: Mo 14-16, Fr 14-16, SR11
Die Vorlesung hat zwei Schwerpunkte:
1) Die Informationstheorie betrachtet formale Maße für Information.
Zentrale Fragen sind, wieviel Information von einem Spieler an einen anderen übertragen werden
kann, wenn diese durch verschiedene Arten von Kanälen verbunden sind, sowie inwiefern Information
komprimiert werden kann. Dies führt zur Betrachtung fehlerkorrigierender Codes, die vielfältige
Einsatzgebiete besitzen.
Diese probabilistische Theorie wird ergänzt durch die Theorie der Kolmogorov-Komplexität,
welche beschreibt, wieviel Information in einem einzelnen Objekt vorhanden ist.
2) In der Kommunikationskomplexitätstheorie wird obiges Modell erweitert, indem Interaktion zwischen den
Spielern erlaubt wird, sowie die Berechnung von Funktionen auf der Eingabe anstelle der bloßen Transmission
der Eingabe betrachtet wird. Der Fokus liegt zumeist auf unteren Schranken für verschiedene Kommunikationsprobleme.
Die Theorie besitzt viele Anwendungen in weiteren Gebieten der Komplexitätstheorie. In der Vorlesung wird
schwerpunktmäßig die Anwendung von informationstheoretischen Techniken betrachtet.
Themen der Vorlesung sind:
Informationstheorie:
-Entropie und Information
-Kanalkapazitäten
-Kompression
-Fehlerkorrigierende Codes
-Kolmogorov Komplexität
Kommunikationskomplexität:
-Vergleich von randomisierter Kommunikation mit deterministischer Kommunikation
-untere Schranken mit kombinatorischen Techniken
-untere Schranken mit informationstheoretischen Techniken.
-Anwendungen (z.B. auf Schaltkreise, Data-stream Algorithmen, Automaten)
Die Vorlesung setzt den Besuch der Veranstaltungen Theoretische Informatik 1 und 2 voraus.
Fachgespräch
16.4.: .pps, .pdf,
.ps [Einleitung, Entropie]
20.4.: .pps, .pdf,
.ps [Bedingte Entropie, Information, relative
Entropie]
23.4.: .pps, .pdf,
.ps [Relative Entropie:
nichtnegativ, vs. Information, Data-processing inequality, Fano]
27.4.: .pps, .pdf,
.ps [Random Access Codes, Kraft Ungleichung,
Schranken für optimale fehlerlose Codes]
30.4.: .pps, .pdf,
.ps [Huffman Coding,
Kanäle und Kapazitäten]
4.5.: .pps, .pdf,
.ps [Kanäle und Kapazitäten fort., Codes und Raten, Typische Sequenzen, Kompression]
7.5.: .pps, .pdf,
.ps [Gemeinsam Typische Sequenzen, Shannons 2.
Theorem, Maximum Likelihood Decoding]
11.5.: .pps, .pdf,
.ps [Analyse Shannons
Theorem]
14.5.: .pps, .pdf,
.ps [Kapazität mit Feedback,
Source-Channel-Coding, Fehlerkorrigierende Codes]
18.5.: .pps, .pdf,
.ps [Hamming Codes, Lineare Codes, Duale Codes,
Hadamard Code, Lokale Dekodierbarkeit]
21.5.: .pps, .pdf,
.ps [Singleton, Hamming, Gilbert-Varshamov
Schranken, Reed Solomon Codes]
25.5.: .pps, .pdf,
.ps [Dekodierung von Reed Solomon Codes,
Lempel-Ziv Kompression, Optimalität]
1.6.: .pps, .pdf,
.ps [Forts. Lempel Ziv, Kolmogorov Komplexität:
Definition, Invarianz, Nichtkomprimierbarkeit]
4.6.: .pps, .pdf,
.ps [Präfixkomplexität, Nichtberechenbarkeit,
Gödel, Symmetrie]
8.6.: .pps, .pdf,
.ps [Kolmogorov und Entropie, Kraft
Ungleichung,Omega, Einweg Kommunikation, Anwendung auf Automaten, Neciporuk]
11.6.: .pps, .pdf,
.ps [Freie Wahl der Eingabepartition, VLSI-Area
Schranke, Randomisierte Einwegkommunikation]
15.6.: .pps, .pdf,
.ps [Privater und öffentlicher Zufall,
Randomisierung gegen Determinismus, Yao Prinzip]
18.6.: .pps, .pdf,
.ps [Index Funktion, VC-Dimension, Greater Than,
Einweg-Rechtecke, Zweiweg Protokolle]
22.6.: .pps, .pdf,
.ps [Rechteckschranke, D(IP), Überdeckungen und
Partitionen, Rangschranke, Nichtdeterminismus]
25.6.: .pps, .pdf,
.ps [Nichtdeterminismus und Determinismus,
Protokolle, Partitionen, Überdeckungen]
29.6.: .pps, .pdf,
.ps [Nichtdeterminismus und Rechteckschranke, Vollständigkeit
von Disjointness, Randomisierung, Greater Than Protokoll]
2.7.: .pps, .pdf,
.ps [Rechteckschranken für randomisierte
Kommunikation, Diskrepanz, R(IP)]
6.7.: .pps, .pdf,
.ps [Schaltkreistiefe vs. Kommunikation,
Khrapchenko]
9.7.: .pps, .pdf,
.ps [Monotone Spiele, lineare untere Schranke für
Matching]
13.7.: .pps, .pdf,
.ps [Freie Partitionen, VLSI AT^2 Schranken, Threshold
Schaltkreise und Größe]
Übungsblätter:
20.4.: .ps
27.4.: .ps
4.5.: .ps
11.5.: .ps
18.5.: .ps
8.6.: .ps
18.6.: .ps
29.6.: .ps
6.7.: .ps
Literatur:
Cover, Thomas: Elements of Information Theory (Wiley)
M. Sudan: Essential Coding Theory
Kushilevitz, Nisan: Communication Complexity (Cambridge)
Arora & Barak: Communication complexity
18.7.07 Hartmut Klauck