G. Nebe, M. Künzer 20.03.2007

Diskrete Strukturen, SS 06

Vordiplomsnachklausur

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 der 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. Bei diesen Fragen ist ein nachvollziehbarer Lösungsweg Bestandteil einer vollständigen Lösung. Wer mehr Papier benötigt, bitte melden. Aufgabe 1 (1+2+2+2 Punkte)

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

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

(3) Bestimme |{σ ∈ S_{6} : σ(i) ≠ i für alle i ∈ {1, 2, …, 6}}|.

(4) Bestimme die Anzahl der irreduziblen Polynome von Grad 12 in F_{2}[X].

Aufgabe 2 (2+2+1 Punkte) Sei G := ⟨a := (1, 2, 3), b := (2, 3, 4)⟩ ≤ S_{4}.

(1) Bestimme die Bahnenlänge |G · 1|.

(2) Bestimme die Bahnenlänge | Stab_{G}(1) · 2|.

(3) Bestimme |G|.

Aufgabe 3 (2+2 Punkte)

(1) Bestimme f ≥ 1 minimal so, daß F_{7^{f}} eine primitive 20-te Einheitswurzel besitzt.

(2) Bestimme die Menge aller Elemente von F_{9}^{∗}, welche F_{9}^{∗} erzeugen. In anderen Worten, bestimme

{x ∈ F_{9}^{∗} : ⟨x⟩ = F_{9}^{∗}}. { }

Aufgabe 4 (2 Punkte) Betrachte folgenden Graphen.

1  2

Bestimme darin die Anzahl der Kantenzüge von der Ecke 2 zur Ecke 2 von Länge 4.

Aufgabe 5 (1+1+1+1 Punkte)

(1) Bestimme ein z ∈ Z mit z ≡_{5} 1 , z ≡_{7} 0 , z ≡_{8} 0 .

(2) Bestimme ein z ∈ Z mit z ≡_{5} 0 , z ≡_{7} 1 , z ≡_{8} 0 .

(3) Bestimme ein z ∈ Z mit z ≡_{5} 0 , z ≡_{7} 0 , z ≡_{8} 1 .

(4) Bestimme das z ∈ Z mit 0 ≤ z < 5 · 7 · 8 und mit

\begin{aligned}z & ≡_{5} & 2 \\ z & ≡_{7} & 1 \\ z & ≡_{8} & 4 . \end{aligned}

Aufgabe 6 (2+2 Punkte) Sei C der lineare Code über F_{4} mit der Erzeugermatrix (\begin{matrix}ω & ω^{2} & 1 & ω^{2} & 1 \\ 1 & ω & 1 & 0 & ω \end{matrix}).

(1) Bestimme eine Prüfmatrix für C.

(2) Bestimme den Minimalabstand von C.

Aufgabe 7 (2+1+2+2+1 Punkte) Sei f(X) = X^{2} +ωX +1 ∈ F_{4}[X]. Sei C der zyklische Code der Länge 5 mit Erzeugerpolynom f(X).

(1) Bestimme alle Nullstellen von f(X) in F_{16}.

(Hinweis: Identifiziere ω = γ^{5}. Es gibt zwei Nullstellen.)

(2) Bestimme den designierten Minimalabstand von C bezüglich der primitiven 5-ten Einheitswurzel γ^{3}.

(3) Bestimme eine Prüfmatrix von C und den Minimalabstand d(C).

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

(5) Ist C ein Hammingcode? Begründe!

Aufgabe 8 (2 Punkte) Zeige oder widerlege folgende Aussage. Das Polynom f(X) := X^{9} + X^{7} + X^{4} + X^{3} + X^{2} + X + 1 ∈ F_{2}[X] zerfällt in ein Produkt paarweise verschiedener irreduzibler Faktoren.