Namen, Daten, Zahlen

• Termin: Mi, 9.00 - 11.00 Uhr und Fr, 9.00 - 11.00 Uhr, HS1
• Beginn: 14.10.1998
• Dozent: Joachim Buhmann
• Übungsbetreuung: John Held, Björn Stenger
• Übungstermin: Mo 11.00 - 13.00, Beginn am 19.10, Raum A121
• Literatur
• Übungsaufgaben

                          NEU: A Mathematical Theory of Communication (C.E. Shannon)

                                                                                       (der klassische Artikel von 1948, der die Grundlagen der Informationstheorie gelegt hat)

Informationen zur Vorlesung

STICHWORTLISTE:

• Vorlesung vom 14.10.98
• I.1 Einleitung:
• Querbezüge zur Kommunikationstheorie, Informatik, Physik, W-Theorie, Statistik

und Wirtschaftstheorie.
• I.2 Themen-Überblick
• Begriffe aus der elementaren W-Theorie
• Entropie, relative Entropie, wechselseitige Information
• stochastische Prozesse
• Datenkompression & Codes, Vektorquantisierung
• Kolmogoroff-Komplexität
• Kanalkapazität
• Ratenverzerrungstheorie
• Statistik
• I.3 Grundlagen der Wahrscheinlichkeitsrechnung
• Elementarereignis, Ereignis, Ereignisraum
• Ereignisalgebra
• Wahrscheinlichkeitsraum
• Eigenschaften von Wahrscheinlichkeiten
• I.4 Bedingte Wahrscheinlichkeit
• Bayes'sche Formel
• I.5 Statistische Unabhängigkeit

• Vorlesung vom 16.10.98
• I.6 Zufallsvariable
• Wahrscheinlichkeitsverteilung einer ZV
• I.7 Erwartungswert einer ZV
• Eigenschaften des Erwartungswertes
• Varianz einer ZV
• Kovarianz zweier ZV
• Korrelationskoeffizient
• Schätzfunktion, optimale Schätzfunktion

• Vorlesung vom 19.10.98
• I.8 Gesetz der großen Zahlen (Bernoulli)
• Chebyshev-Ungleichung
• typisches Ereignis
 
• Vorlesung vom 21.10.98
• II.1 Entropie
• Definition, Eigenschaften
• Verbundentropie, bedingte Entropie
• Kettenregel für Entropie
• II.2 Eindeutigkeitssatz
 
• Vorlesung vom 23.10.98
• relative Entropie (Kullback-Leibler Divergenz)
• wechselseitige Information
• Kettenregel für Entropie
• bedingte Information
• Jensen'sche Ungleichung
• Informationsungleichung
• Schranke für Entropie
• Konditionierung reduziert Entropie
• II.3 Datenverarbeitungsungleichung
• Markovkette
• Datenverarbeitungsungleichung
 
• Vorlesung vom 28.10.98
• II.4 Erschöpfende Schätzfunktionen (sufficient statistics)
• Fano's Ungleichung
• II.5 Typische Ereignisse
• Satz von McMillan
• Vorlesung vom 30.10.98
• Mengen mit hoher Wahrscheinlichkeit
• II.6 Datenkompression von Folgen
• III.1 Entropie von stochastischen Prozessen
• III.2 Entropierate
• Entropierate einer stationären Markovkette
• Vorlesung vom 4.11.98
• III.3 Zustandsdiagramme
• IV.1 Datenkompression
• Kompaktifizierung, Kompression
• Quellcode, nichtsingulärer Code, Erweiterung eines Codes,

eindeutig dekodierbare Codes, Präfixcodes, Hierarchie von Codes
• IV.2 Kraftsche Ungleichung
• Vorlesung vom 6.11.98
• Erweiterte Kraftsche Ungleichung
• IV.3 Optimale Codes
• IV.4 Schranken für optimale Codes
• Kraftsche Ungleichung für eindeutig dekodierbare Codes
• Huffman-Codes
• Optimalität des Huffman-Codes
• Vorlesung vom 11.11.98
• IV.5 Shannon-Fano-Elias-Code
• IV.6 Arithmetische Codierung
• Vorlesung vom 13.11.98
• IV.7 Optimalität des Shannon-Codes
• IV.8 Erzeugung diskreter Verteilungen durch faire Münzwürfe
• Vorlesung vom 18.11.98
• IV.9 Pferdewetten und Kompression
• V.1 Kanalkapazität
• diskreter Kanal, Informationskapazität
• Vorlesung vom 20.11.98
• V.2 Symmetrische Kanäle
• V.3 Motivation für den Kanalkodierungssatz
• Definitionen: diskreter gedächtnisloser Kanal, n-te Erweiterung eines Kanals,

(M,n)-Codes, Fehlerwahrscheinlichkeiten, Rate, Kapazität
• Vorlesung vom 25.11.98
• gemeinsam typische Sequenzen
• Hilfssätze zum Kanalkodierungstheorem
• V.4 Das Kanalkodierungstheorem
• Vorlesung vom 27.11.98
• Beweis des Kanalkodierungstheorems
• Umkehrung des Kanalkodierungstheorems
• Vorlesung vom 2.12.98
• Codierungstheorie
• Block Codes, Hamming-Distanz, Hamming-Gewicht
• Repititionscodes, Parity-Check-Code
• lineare Codes
• Hamming Codes
• (kurz) Gallager-Codes, Faltungs-Codes, Reed-Solomon-Codes, JPL-Code
• Vorlesung vom 9.12.98
• V.6 Feedback-Kapazität
• Feedback-Code, Kanalkapazität unter Rückkopplung
• V.7 Der gemeinsame Quellen-Kanal Codierungssatz
• VI Differentielle Entropie
• VI.2 Typische Mengen stetiger Zufallsvariablen
• typische Ereignisse
• Vorlesung vom 11.12.98
• differentielle Entropie und diskrete Entropie
• Verbund- und bedingte differentielle Entropie
• Entropie einer multivariaten Normalverteilung
• relative differentielle Entropie (KL-Abstand)
• wechselseitige Information
• Eigenschaften der differentiellen Entropie, relativen Entropie und wechselseitigen Information
• Vorlesung vom 16.12.98
• VI.3 Der Gaußsche Kanal
• Informationskapazität des Gaußschen Kanals
• (M,n)-Code für einen Gaußschen Kanal
• Kapazität eines Gaußschen Kanals
• Vorlesung vom 18.12.98
• Abtasttheorem
• bandbreitenbeschränkte Kanäle
• parallele Gaußsche Kanäle
• Vorlesung vom 6.1.99
• VI.4 Kommunikation bei Kanalunsicherheit
• Compound BSC, Beliebig variierender Kanal (AVC), Gilbert-Elliot-Kanal
• VI.5 Kapazität des Compound DMC
• Vorlesung vom 8.1.99
• Kapazität des Gaußschen AVC
• VI.6 Universelle Datenkompression
• Ziv-Lempel Kompression
• Vorlesung vom 13.1.99
• Optimalität der Ziv-Lempel Codierung
• VII Ratenverzerrungstheorie
• Lloyd-Max-Quantisierer
• VII.2 Definitionen
• Verzerrungsfunktion
• Vorlesung vom 15.1.99
• Verzerrung zwischen Folgen, Ratenverzerrungs-Code
• RV-Paar, RV-Region, RV-Funktion
• Informations-RV-Funktion
• VII.3 Berechnung der RV-Funktion
• Bernoulli(p)-Quelle mit Hamming-Verzerrung
• Gaußsche Quelle mit quadratischem Verzerrungsmaß
• parallele Gaußquellen
• Vorlesung vom 20.1.99
• VII.4 Raten-Verzerrungs-Theorem
• Beweis der Umkehrung
• Beweis der Erreichbarkeit der RV-Funktion
• Vorlesung vom 22.1.99
• VII.5 Charakterisierung der RVF
• Blahut-Arimoto-Algorithmus
• VII.6 RV mit Seiteninformation
• VII.7 Das Flaschenhalsprinzip
• Vorlesung vom 27.1.99
• VIII.1 Kolmogorov-Komplexität
• VIII.2 Definition der Kolmogorov-Komplexität
• Vorlesung vom 29.1.99
• obere Schranke an K-Komplexität
• K-Komplexität einer binären Zeichenkette
• VIII.3 Kolmogorov-Komplexität und Entropie
• Vorlesung vom 3.2.99
• K-Komplexität ganzer Zahlen
• algorithmische Zufälligkeit, inkompressible Folgen
• VIII.4 Universelle Wahrscheinlichkeit
•  Chaitins Zahl Omega
•  VIII.5 Occams Rasiermesser
•  Äquivalenz zwischen K-Komplexität und universeller Wahrscheinlichkeit
• Vorlesung vom 5.2.99
• IX Informationstheorie und Statistik
• Methode der Typen (nach Csiszar & Körner)
• Typen, Typklasse
• Vorlesung vom 10.2.99
• Wahrscheinlichkeit von Typklassen
• Anwendungen der Methode der Typen
• a) Gesetz der großen Zahlen
• b) Universelle Quellcodierung
• c) Theorie großer Abweichungen
• Vorlesung vom 12.2.99

         Zusammenfassung der wichtigsten Themen
         Ausblick auf die Vorlesung "Statistische Mustererkennung & Neuronale Netze" im Sommersemester 1999
  - ENDE -

---

Nachfolgeveranstaltungen

• Arbeitsgemeinschaft: Mustererkennung und Computational Learning Theory (WS 97/98)
• Vorlesung: Neuronale Netze und Mustererkennung (SS 99)

---

Folienkopien können bei John Held (A117) ausgeliehen werden.


---

last updated: 12.02.1999, suggestions to held@cs.bonn.edu