Prof. H. Pahlings, Lehrstuhl D für Mathematik, RWTH Aachen Aufgabenblatt B 1 Vordiplomklausur ”Diskrete Strukturen“, 7. 9. 2001

Ankreuzteil

Aufgabe A1. Es seien s_{n,k} die Stirlingzahlen 1. Art. Dann gilt: s_{n,k} = s_{n−1,k−1} + k·s_{n−1,k} für 1 ≤ k ≤ n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein ∑_{k=0}^{n} s_{n,k} = n!. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein s_{n,n−1} = \binom{n}{2} für n ≥ 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein s_{4,2} hat den Wert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe A2. Es sei ℚ[[x]] der Ring der formalen Potenzreihen über ℚ. Dann gilt: \frac{1+x}{x} ∈ ℚ[[x]]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein \frac{x}{1+x} ∈ ℚ[[x]]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein Ist A = ∑_{i=0}^{∞} a_{i}x^{i}, so ist A^{2} = ∑_{i=0}^{∞} a_{i}^{2}x^{i}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist A = ∑_{i=0}^{∞} a_{i}x^{i}, so ist x^{3}A = ∑_{i=3}^{∞} a_{i−3}x^{i}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A3. Es sei K ein Körper und f ∈ K[x]. Dann gilt: Hat f in K keine Nullstelle, so ist f irreduzibel in K[x]. . . . . . . . . . . . . . . . . □ Ja □ Nein Ist Grad f = 0, so ist f irreduzibel in K[x]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist Grad f = 1, so ist f irreduzibel in K[x]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein x^{4} + x^{2} + 1 ∈ ℤ_{2}[x] ist irreduzibel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A4. Es sei f = x^{4} + 1 ∈ ℤ_{2}[x] und R = ℤ_{2}[x] /f ℤ_{2}[x] . Dann gilt: Die Anzahl der Teiler von f in ℤ_{2}[x] ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Das Inverse von [x^{2} + x + 1]_{f} in R ist [x^{3} + x^{2} + 1]_{f}. . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Die Anzahl der Elemente von R ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A5. Es gibt einen 3-regulären Graphen mit 7 Knoten. . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist G = (V, E) ein zusammenhängender Graph, so ist |V | ≤ |E| + 1. . . . . . □ Ja □ Nein Die Anzahl der Kanten des vollständigen Graphen K_{6} ist . . . . . . . . . . . . . . . . . . . . . . . . . .

Rechenaufgaben ohne Begründung

Aufgabe R1. (4 Punkte) Die Anzahl der injektiven Abbildungen f: {1, 2, 3} → {1, 2, 3, 4, 5} ist . . . . . . . . . . . . . . . . . . . . Die Anzahl der surjektiven Abbildungen f: {1, 2, 3, 4} → {1, 2} ist . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R2. (4 Punkte) Es seien die Permutationen a = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 2 & 4 & 8 & 9 & 3 & 1 & 5 & 6 \end{matrix} ) aus S_{9} und b = (1 4 6 2) (3 7 5) aus S_{7} gegeben. Die Zyklendarstellung von a ist . . . . . . . . . . . . . . . . . . . . . . . . . . Die Ordnung von b ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Zyklendarstellung von b^{−1} ist . . . . . . . . . . . . . . . . . . . . . . . . Die Zyklendarstellung von b^{27} ist . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R3. (4 Punkte) Berechnen Sie einen größten gemeinsamen Teiler d von f = x^{4} + 1 und g = x^{2} + x + 1 in ℤ_{2}[x] und stellen Sie ihn in der Form d = a · f + b · g mit a, b ∈ ℤ_{2}[x] dar. Geben Sie d, a und b an.

d =  a =  b =

Aufgabe R4. (5 Punkte) Es sei φ die eulersche φ-Funktion. Berechnen Sie φ(100). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bestimmen Sie die kleinste Zahl n ∈ ℕ_{0} mit n ≡ 11^{162} mod 100. . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R5. (5 Punkte) Es sei C der binäre zyklische Code der Länge 7 mit Generatorpolynom g = x^{3} + x + 1, also

C = { (c_{i})_{i=0}^{6} | [∑_{i=0}^{6} c_{i}x^{i}]_{x^{7}−1}= [g · h]_{x^{7}−1} für ein h ∈ ℤ_{2}[x] }.

Die Dimension von C ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Anzahl der Codeworte in C ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Die Minimaldistanz von C ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (1, 1, 0, 1, 0, 0, 0) wird decodiert als . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R6. (5 Punkte) Es sei (V, E) der Baum mit der Knotenmenge V = {1, …, 6} und dem Prüfercode (2, 3, 3, 2). Geben Sie die Nachbarn von 2 an, also die Menge {a ∈ V | {a, 2} ∈ E}. . . . . . . . .

Aufgaben mit Lösungsweg

Aufgabe L1. (8 Punkte) Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 1, a_{1} = 0 und a_{n} = a_{n−1}+2 a_{n−2} ∈ ℚ für n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der Folgenglieder a_{n}.

Aufgabe L2. (8 Punkte) Es sei φ die eulersche φ-Funktion. Bestimmen Sie alle ungeraden natürlichen Zahlen n mit φ(n) = 6. Für welche dieser n ist die prime Restklassengruppe ℤ_{n}^{∗} zyklisch? Geben Sie jeweils alle erzeugenden Elemente [a]_{n} dieser Gruppe an.