Hans-Georg Eßer

esser@i2.informatik.rwth-aachen.de  Aachen, 09.04.1997

Diplomprüfung im Fach “Angewandte Mathematik” über Kryptologie, Informationstheorie, Stochastik I und Topologie bei Prof. Dr. R. Mathar am 09.04.1997

Prüfungsprotokoll

Das folgende Prüfungsprotokoll ist recht kurz und sicherlich unvollständig. Zur Prüfungsatmosphäre: sehr freundlich; Herr Mathar ließ mich in Ruhe nachdenken und gab viele Hilfestellungen.

Folgende Texte waren Prüfungsstoff:

• R. Mathar: Vorlesung Kryptologie, WS 1996/97, V3 Ü2

• R. Mathar: Informationstheorie (Skript zur gleichnamigen Vorlesung an der RWTH Aachen), 2. Auflage 1996, Verlag der Augustinus-Buchhandlung

• H. H. Bock: Vorlesung Stochastik I, WS 1992/93

• E. Görlich: Vorlesung Topologie, SS 1993

Nun zum Inhalt der Prüfung:

Stochastik I Zu Beginn fragte Herr Mathar, welche Themen Herr Bock in seiner Vorlesung behandelt habe. Nachdem ich eine kurze Zusammenfassung gab und Herr Mathar noch ein paar Themen ergänzte, begann die eigentliche Prüfung mit Fragen über Mengensysteme. (“Welche Mengensysteme kennen Sie denn so?”) Nach der Antwort (Ring, Algebra, σ-Algebra, Dynkin-System) Definition von Ring, Algebra und σ-Algebra. Dabei direkt zum Auftakt kleiner Schnitzer bei Ring-Eigenschaften: habe behauptet, daß A ∈ R ⇒ \overline{A} ∈ R, was natürlich nicht gilt. Sollte dann Äquivalenz dieser Behauptung zur eigentlichen Komplement-Stabilität zeigen; dabei fiel mir dann auf, daß das falsch ist. “Wie sieht ein Maß auf einem Ring aus?” Auf Ringen gibt’s nur Inhalte oder Prämaße. Die kann man dann auf geeigneter σ-Algebra zu Maß fortsetzen. “Jetzt mal konkret. Wie machen Sie das im ℝ^{n}?” Elementarinhalt der n-dimensionalen Intervalle; fortsetzen auf Figuren (“wieso lassen sich Figuren als disjunkte Zerlegungen von Intervallen darstellen?”), dann Caratheodory-Fortsetzungssatz; äußeres Maß (Definition hingeschrieben). “Nehmen wir mal einen Kreis K (gefüllt); das ist doch sicher eine Borel-Menge. Wie bestimmen Sie denn das Maß?” Mein erster Ansatz: durch Rechtecke von innen approximieren. Wenn es eine Folge von Figuren F_{n} mit F_{n} → K (isoton) gibt, dann muß auch μ(F_{n}) → μ(K). “Approximieren denn Ihre Rechtecke überhaupt den Kreis?” ?? “Wieviele Punkte liegen denn auf dem Kreisrand?” überabzählbar viele, aber der Rand ist eine Nullmenge! “Und wieviele Punkte des Randes treffen Sie bei Approximation mit diesen Rechtecken?” Nur abzählbar viele (abzählbare Vereinigung von Rechtecken). “Geht das dann mit der Approximation?” (Zögern) “Sie haben die Antwort ja schon gegeben: das ist ja nur eine Nullmenge”. “Anderes Thema. Sie kennen Zufallsvariable?” Meßbare Funktionen... “Wann sind denn ZV stochastisch unabhängig?” Wenn P (X ∈ A, Y ∈ B) = P (X ∈ A)P (Y ∈ B). “Das ist richtig. Wie sieht das denn mit den Verteilungen aus?” lief darauf hinaus, daß die Verteilung st. unabh. ZV gerade das Produkt der Randverteilungen ist.

Informationstheorie “Erzählen Sie mal was über Entropie”. Es gibt drei Zugänge.

1. die Definition H(p_{m}) := − ∑ p_{i} log p_{i}; 2. den axiomatischen Zugang (H maximal unter Gleichverteilung, H(X, Y) = H(X) + H(Y |X), H ändert sich nicht, wenn im stoch. Vektor eine Null hinzugefügt wird); 3. wie im Beispiel 4.1: zwei Beobachter A, B. A hat Experiment beobachtet und B versucht durch Blockfragestrategie das Ergebnis rauszufinden. Dann Blockfragestrategie. Das ganze entspricht Kodes (“was genau sind Kodes?”, Definition von eindeutig dekodierbar gegeben), und das noiseless coding theorem liefert die Konvergenz der erwarteten Kodewortlänge von (geeignet existierenden) Blockkodes der Länge N gegen die normierte Entropie H(X)/ log d. Beschreibung durch H(X_{N} | X_{N−1}, ..., X_{1}) bzw. \frac{1}{N} H(X_{N}) “Dann was anderes. Was sagt Ihnen die Transinformation, wo wird die gebraucht?” (???) “Wenn Sie mal an Kanäle denken...” (??? ???) “und deren Kapazität” Ach ja! Kapazität ist maximale Transinformation, maximiert über alle möglichen Input-Verteilungen (blöd von mir).

Kryptologie “Public-Key-Systeme: Das Rabin-System. Kennen Sie das? Wie funktioniert das?” Wähle zwei große Primzahlen p, q. Setze n := pq. Verschlüssele M durch M(M +g) mod n. Entschlüsseln (suchen einer Wurzel mod n) schwierig, wenn p und q unbekannt. Autorisierter Empfänger kann Wurzeln mod p und mod q bestimmen und daraus eine Gesamtlösung berechnen. “Wenn jemand ein Orakel hätte, daß Wurzeln mod n ausrechnet, was könnte er dann tun?” Vermutlich n faktorisieren? “Ja, wie ist denn da der Zusammenhang?” ??? “Kennen Sie das Euler-Kriterium?” Eine Weile überlegt; das war was mit hoch (p − 1)/2... (Anmerkung: Sei p > 2 prim. Dann gilt: d ist quadratischer Rest mod p ⟺ d^{(p−1)/2} ≡ 1 (mod p))

Topologie Ich hatte Herrn Mathar eine Zusammenfassung der Vorlesung von Herrn Görlich gegeben. Darin blätterte er und sagte dann. “Kompaktheit. Ich lese Ihnen mal zwei Definitionen vor” (gibt mir die Definitionen von Bolzano-Weierstraß-kompakt und folgenkompakt) “sind die äquivalent?” Für allgemeine topologische Räume sicher nicht. “Hat das was mit Trennungseigenschaften zu tun?” Ich vermute, wenn die Räume T2 (Hausdorffsch) sind, fällt das zusammen. “Hatten Sie da einen Satz in der Vorlesung?” Wir hatten verschiedene Sätze über die Zusammenhänge. Die Eigenschaften fallen auf jeden Fall für den ℝ^{n} zusammen. Danach gab ich noch einen kurzen Kommentar, warum wir in der Topologie den Heine-Borel-Kompaktheits-Begriff als (allgemeinen) Kompaktheitsbegriff verwenden; dann gibt es nämlich die schöne Aussage, daß unendliche (!) Produkte kompakter Räume wieder kompakt sind.

Ende der Prüfung nach ca. einer Stunde. Note: 1,7