Ueb 11
Hochgeladen von
dethleff901Ueb 11
Hochgeladen von
dethleff90111. Aufgabenblatt vom Montag, den 17.
Januar 2011 zur Vorlesung
Mathematik für Informatiker III
(Frank Hoffmann)
Abgabe: bis Montag, den 24. Januar 2011, 1215
1. Endlicher Körper F8 (7 Punkte)
Zur Erinnerung: Die Elemente von F8 lassen sich identifizieren mit Polynomen d2 x2 +
d1 x + d0 ∈ F2 [x] von Maximalgrad ≤ 2. Dieses ist eindeutig bestimmt durch das Tripel
d2 d1 d0 von Koeffizienten und das kann man wiederum als Binärdarstellung einer Zahl
aus {0, 1, . . . , 7} lesen. Wie wird gerechnet in F8 ? Die Addition ist einfach die Addition
von Polynomen. Für die Multiplikation fixieren wir das irreduzible Polynom g(x) =
x3 + x2 + 1. Das Ergebnis von p(x) · q(x) in F8 ist das eindeutig bestimmte Polynom
(p(x) · q(x)) mod g(x).
Bestimmen Sie über F8 die Determinante der Matrix
1 2 3
A= 0 3 4
5 4 2
2. Syndromdecodierung (3 Punkte)
Betrachten Sie den (4, 2, 3)–Code über F3 im Skript S. 84. Decodieren Sie die folgenden
erhaltenen Nachrichten mittels Syndromdecodierung:
2 1 1
1 1 1
v1 = 2 v2 = 1 v3 = 0
0 1 0
3. Blockcode (2 Punkte)
Existiert ein Blockcode C ⊂ {0, 1}6 mit |C| = 8 und einem Hamming–Abstand ≥ 3
zwischen je zwei verschiedenen Codewörtern u, v? Begründen Sie Ihre Antwort!
4. Siebformel (4+4 Punkte)
(a) Sei (Ω, F, P r) ein Wahrscheinlichkeitsraum und A1 , . . . , An Ereignisse. Beweisen
Sie (Tipp: Vollständige Induktion) die sogenannte Siebformel, auch als Inklusions–
Exklusions–Prinzip bekannt:
n
[ n
X X n
\
n+1
P r( Ai ) = P r(Ai ) − P r(Ai ∩ Aj ) + . . . + (−1) P r( Ai )
i=1 i=1 1≤i<j≤n i=1
(b) Wir betrachten zufällige Permutationen x1 , . . . , xn der Elemente 1, . . . , n. Was ist
die Wahrscheinlichkeit, dass wenigstens ein i an der richtigen Stelle steht, das heißt
xi = i gilt? Benutzen Sie die Siebformel und betrachten Sie Ereignisse Ai , die aus
allen Permutationen mit xi = i bestehen.
Tipp: Zum Nachlesen Diskrete Wkt-Rechnung:
http://www.inf.fu-berlin.de/lehre/WS09/mafi1/skript/SKRIPT09_komplett.pdf
