G. Nebe, M. Künzer 21.08.2006

Diskrete Strukturen, SS 06

Scheinklausur

Bearbeitungszeit: 120 Minuten. Zugelassene Hilfsmittel: Ein beliebig beschriebenes Blatt DIN A4 und ein nichtprogrammierbarer Taschenrechner. Es sind insgesamt 36 Punkte erreichbar. Ist ein Kasten bei einer Frage, so bitte die Antwort in den Kasten. Die für diese Antwort benötigten Rechnungen gehen diesenfalls in die Bewertung nicht ein. Eine falsche Antwort gibt 0 Punkte (aber keine negativen Punkte). Bitte zu jeder Bearbeitung einer Frage ohne Kasten deutlich die Aufgabennummer angeben. Wer mehr Papier benötigt, bitte melden. Aufgabe 1 (1+2+2+1 Punkte)

(1) Auf wieviele Arten kann man 4 Kugeln aus 4 Kugeln ziehen, wenn man jeweils wieder zurücklegt und nicht auf die Reihenfolge achtet?

(2) Bestimme die Ordnung des Elements ((1, 3, 2) ∘ (1, 4, 3) ∘ (1, 3))^{2} von S_{4}.

(3) Seien 5 verschiedene Briefe in 5 verschiedene Briefumschläge zu stecken. Wieviele Möglichkeiten gibt es, keinen Brief in den richtigen Umschlag zu stecken? (Hinweis: Permutationen, Fixpunkte.)

(4) Bestimme μ(91).

Aufgabe 2 (6 Punkte) Bestimme das Polynom f(X) ∈ F_{2}[X] von Grad < 6, welches folgenden Kongruenzen genügt, und trage es hier ein: . (Hinweis: Euklid.)

\begin{aligned}f(X) & ≡_{X} & 1 \\ f(X) & ≡_{X^{2}+X+1} & 1 \\ f(X) & ≡_{X^{3}+X+1} & X^{2} \end{aligned}

Aufgabe 3 (4+2 Punkte) Sei m ≥ 1. Sei A_{m} die Menge der Abbildungen von {1, …, 6} nach {1, …, m}. Wir interpretieren A_{m} als die Menge der Perlenfärbungen der 6 Perlen einer Kette mit m möglichen Farben. Auf A_{m} operiere dementsprechend die Gruppe

G := ⟨a := (1, 2, 3, 4, 5, 6), b := (2, 6)(3, 5)⟩ ≤ S_{6}

via (g · f)(x) := f(g^{−1}x), wobei f ∈ A_{m}, g ∈ G und x ∈ {1, …, 6}. Zwei Perlenfärbungen f und f′ sind bis auf Perlenkettenbewegung als gleich anzusehen, falls sie in derselben G-Bahn von A_{m} liegen.

(1) Liste alle Elemente von G auf. (Hinweis: Eine Betrachtung von ^{b}a kann helfen.)

(2) Bestimme die Anzahl der G-Bahnen auf A_{3}, d.h. die Anzahl der auch nach Perlenkettenbewegung verschiedenen Perlenfärbungen mit 3 Farben.

Aufgabe 4 (2 Punkte) Betrachte folgenden bewerteten Graphen G.

[figure: 1; 0.3; 0.2; 0.2; 0.05; 2; 0.1; 0.1; 0.05; 4; 0.2; 0.1; 3]

Bestimme einen minimalen aufspannenden Teilgraphen. Trage diesen mit Farbe in G ein. Aufgabe 5 (2+2 Punkte) Sei C der lineare Code über F_{2} mit der Erzeugermatrix (\begin{matrix}1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}). Sei C′ der lineare Code über F_{2} mit der Erzeugermatrix (\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}).

(1) Bestimme eine Erzeugermatrix von (C|C′).

(2) Bestimme den Minimalabstand von (C|C′).

Aufgabe 6 (2+1 Punkte) Sei f(X) = X^{4} + X + ω ∈ F_{4}[X]. Sei C der zyklische Code der Länge 15 mit Erzeugerpolynom f(X). Betrachte F_{4} als Teilkörper von F_{16} vermöge ω \overline{}γ^{5} = γ^{2} + γ.

(1) Bestimme alle Nullstellen von f(X) in F_{16} unter Verwendung der Tatsache, daß γ^{9} und γ^{13} als Nullstellen bekannt sind.

(2) Bestimme den designierten Minimalabstand von C, d.h. die vermittels aufeinanderfolgender Potenzen einer primitiven 15-ten Einheitswurzel als Nullstellen von f(X) bestimmbare untere Schranke für d(C).

Aufgabe 7 (4+2 Punkte) Sei C der Hammingcode mit den Parametern q = 8 und r = 2 in Standardbezeichnung.

(1) Bestimme eine Prüfmatrix und eine Erzeugermatrix von C.

(2) Vergleiche die Dimension von C mit der Singleton-Schranke im vorliegenden Fall, d.h. für Länge und Minimalabstand wie C.

Aufgabe 8 (3 Punkte) Zeige oder widerlege die folgende Aussage. Sei G eine endliche Gruppe. Ist p eine Primzahl, ist k ≥ 1, und ist p^{k} ein Teiler von |G|, so gibt es in G ein Element von Ordnung p^{k}.