Prof. H. Pahlings, Lehrstuhl D für Mathematik, RWTH Aachen Blatt 1 Vordiplomklausur ”Diskrete Strukturen“, 15. 3. 2002

Ankreuzteil

Aufgabe A1. Welche der folgenden Gleichungen sind richtig?

( \begin{matrix}n + 1 \\ k \end{matrix} ) = ( \begin{matrix}n \\ k \end{matrix} ) + ( \begin{matrix}n \\ k − 1 \end{matrix} ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja  □ Nein
( \begin{matrix}m + n \\ k \end{matrix} ) = ∑_{l=0}^{k} ( \begin{matrix}m \\ k − l \end{matrix} ) ( \begin{matrix}n \\ l \end{matrix} ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja  □ Nein
∑_{k=0}^{n} S_{n,k} = 2^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja  □ Nein
∑_{k=0}^{n} s_{n,k} = n! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja  □ Nein

Aufgabe A2. Es sei |M| = 4 und |N| = 3. Die Anzahl der injektiven Abbildungen f: N → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der injektiven Abbildungen f: M → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: N → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: M → N ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe A3. Ist K ein Körper und f, g ∈ K[x], so gilt: f = g ⟺ f(a) = g(a) für alle a ∈ K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein f ist in K[x] invertierbar ⟺ f(a) ≠ 0 für alle a ∈ K . . . . . . . . . . . . . . . . . . . □ Ja □ Nein {f ∈ K[x] | f(1) = 0} ⊴ K[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein {f ∈ K[x] | Grad f ≤ 3} ⊴ K[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

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

Aufgabe A5. Ist G = (V, E) ein nummerierter Graph mit Adjazenzmatrix A ∈ ℤ^{n×n} und Inzidenzmatrix B ∈ ℤ^{n×m} und V = { v_{1}, …, v_{n} }, so ist der Grad d(v_{i}) die Summe der Einträge der i-ten Zeile von A, . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein die Summe der Einträge der i-ten Spalte von A, . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein die Summe der Einträge der i-ten Spalte von B. . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Rechenaufgaben ohne Begründung

Aufgabe R1. (4 Punkte) Die Anzahl aller Äquivalenzrelationen auf einer 4-elementigen Menge ist . . . . . . . . . . . . . . . . .

Aufgabe R2. (3 Punkte) Es sei a = (1 2) (3 4 5) (6 7 8 9) aus S_{9}. Die Ordnung von a ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Die kleinste natürliche Zahl i mit a^{i} = a^{99} ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Die Zyklendarstellung von a^{125} ist . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R3. (5 Punkte) Es sei φ die eulersche φ-Funktion. Berechnen Sie φ(1000). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Es sei m = 12345678987603. Was sind die letzten drei Ziffern von 7^{m}? . . . . . . . . . . . . . . . . . . .

Aufgabe R4. (4 Punkte) Wie viele Ideale hat der Ring R = ℤ_{2}[x] /(x^{4} + x^{3} + x + 1) ℤ_{2}[x] ? . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe R5. (4 Punkte) Die Anzahl der irreduziblen Polynome vom Grad 7 über ℤ_{2} ist . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgaben mit Lösungsweg

Aufgabe L1. (10 Punkte) Drei Sender geben alle 7, 8, beziehungsweise 11 Minuten ein Signal ab. Zuletzt wurden ihre Signale vor 2, 1, beziehungsweise 3 Minuten empfangen. Wann werden das nächste Mal alle drei Signale gleichzeitig empfangen? Hinweis: Wichtig ist hier eine klare Darstellung der Lösungsmethode. Systematisches Probieren oder nachträgliche Verifikation eines durch Raten gefundenen Ergebnisses gelten nicht als Lösung.

Aufgabe L2. (14 Punkte) Lösen Sie explizit die folgenden gekoppelten Rekursionsgleichungen mittels erzeugender Funktio-

nen. a_{0} = 0, b_{0} = 1,

a_{n} = a_{n−1} + b_{n−1},
b_{n} = 6 a_{n−1} + 2 b_{n−1}.

Hinweis: Auch hier ist die Darstellung der Lösungsmethode wesentlich. Eine nachträgliche Verifikation eines durch Raten gefundenen Ergebnisses, etwa durch vollständige Induktion, gilt nicht als Lösung.