Name: Matrikelnummer:

Klausur zur Vorlesung Diskrete Strukturen (13. 7. 2001)

Professor Dr. H. Pahlings, Lehrstuhl D für Mathematik, RWTH Aachen

Ankreuzteil

Aufgabe A1. Es seien s_{n,k} und S_{n,k} die Stirlingzahlen 1. bzw. 2. Art. Dann gilt:

(1) S_{n,k} = S_{n−1,k−1} + k·S_{n−1,k} für 1 ≤ k ≤ n. . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(2) ∑_{k=0}^{n} s_{n,k} = 2^{n}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Was ist S_{4,2}? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe A2. Ist A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ ℚ[[x]] eine formale Potenzreihe, so ist:

(1) A^{2} = ∑_{n=0}^{∞} a_{n}^{2}x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(2) x^{2}A = ∑_{n=2}^{∞} a_{n−2}x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) A genau dann in ℚ[[x]] invertierbar, wenn a_{0} = 1 ist . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A3. Ist K ein Körper und f ∈ K[x] mit Grad f ≥ 1, so gilt:

(1) Gibt es kein c ∈ K mit (x + c) | f, so ist f irreduzibel. . . . . . . . . . . . . . .□ Ja □ Nein

(2) Ist K[x] /f K[x] ein Körper, so ist f irreduzibel. . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) x^{3} + x + 1 ∈ ℤ_{2}[x] ist irreduzibel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe A4.

(1) Wie viele Elemente hat ℤ/9 ℤ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) ℤ/9 ℤ ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Wie viele Elemente hat ℤ_{3}[x] /(x^{2} − 1) ℤ_{3}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(4) ℤ_{3}[x] /(x^{2} − 1) ℤ_{3}[x] ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A5. Es sei C der Code über ℤ_{2} mit der Generatormatrix G = [ \begin{matrix}1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix} ].

(1) Was ist die Dimension von C? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) C ist zyklisch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Die Minimaldistanz von C ist 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A6. Gibt es einen Graphen G = (V, E) mit |V | ≤ 5 und

(1) ∑_{v∈V} d(v) = 9 ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

(2) ∑_{v∈V} d(v) = 22 ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

(3) Adjazenzmatrix A mit A^{2} = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ]? . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Rechenaufgaben ohne Begründung

Aufgabe R1. (7 Punkte)

(1) Wie viele injektive Abbildungen f: {1, 2} → {1, 2, 3, 4} gibt es? . . . . . . . . . . . . . . . . . . . . . .

(2) Wie viele surjektive Abbildungen f: {1, 2, 3, 4} → {1, 2, 3} gibt es? . . . . . . . . . . . . . . . . . . .

(3) Wie viele injektive Abbildungen f: {1, 2, 3, 4} → {1, 2, 3, 4} gibt es? . . . . . . . . . . . . . . . . . . Aufgabe R2. (4 Punkte) Es seien die Permutationen a = (1 2 5) (3 6 7 8 4) und c = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 7 & 5 & 3 & 8 & 1 & 4 & 2 & 6 \end{matrix} ) aus S_{8} gegeben.

(1) Die Zyklendarstellung von c ist . . . . . . . . . . . . . . . . . . . . . .

(2) Die Ordnung von a ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(3) Die Zyklendarstellung von a^{3} ist . . . . . . . . . . . . . . . . . . . .

(4) Die Zyklendarstellung von a^{3001} ist . . . . . . . . . . . . . . . . . . Aufgabe R3. (4 Punkte) Berechnen Sie einen größten gemeinsamen Teiler d der Zahlen 532 und 434 und stellen Sie ihn in der Form d = a · 532 + b · 434 mit a, b ∈ ℤ dar. . . . . . . . . . . . Aufgabe R4. (8 Punkte)

(1) Es sei φ die eulersche φ-Funktion. Berechnen Sie φ(60). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) Wie viele Einheiten (invertierbare Elemente) hat der Ring ℤ/60 ℤ? . . . . . . . . . . . . . . . . . .

(3) Bestimmen Sie die kleinste Zahl n ∈ ℕ_{0} mit n ≡ 7^{162} mod 60. . . . . . . . . . . . . . . . . . . . . . . . . Aufgabe R5. (6 Punkte)

(1) Die Anzahl der irreduziblen Teiler von x^{2^{5}} − x ∈ ℤ_{2}[x] ist . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) Die Anzahl der irreduziblen Polynome vom Grad 5 über ℤ_{2} ist . . . . . . . . . . . . . . . . . . . . . . . Aufgabe R6. (5 Punkte) Wie viele Ideale hat der Ring ℤ_{2}[x] /(x^{5} + 1) ℤ_{2}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgaben mit Lösungsweg

Aufgabe L1. (8 Punkte) Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 0, a_{1} = 2 und a_{n} = −a_{n−1} + 2 a_{n−2} für alle n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der Folgenglieder a_{n}. Aufgabe L2. (6 Punkte) Geben Sie explizit einen Isomorphismus ψ: ℤ_{220} → ℤ_{4} × ℤ_{5} × ℤ_{11} an und berechnen Sie

ψ( [135]_{220}), ψ( [187]_{220}) und ψ( [135·187]_{220}).

Benutzen Sie dies, um [135]_{220} · [187]_{220} in ℤ_{220} auszurechnen.