Professor Dr. H. Pahlings 5. 10. 93

Nachholklausur zur Vorlesung Diskrete Strukturen

Bearbeitungszeit: 120 Minuten zuzüglich 10 Minuten Lesezeit

Bitte schreiben Sie auf jedes Blatt Ihren Namen, und bearbeiten Sie auf jedem Blatt nur eine Aufgabe. Es sind \underline{keine Hilfsmittel} zugelassen, insbesondere keine schriftlichen Aufzeichnungen und keine elektronischen Rechengeräte. Bitte beachten Sie, daß \underline{ausführliche} \underline{Be}g\underline{ründun}g\underline{en} einen wesentlichen Teil der Lösung einer Aufgabe bilden. Wenn Sie z. B. Bezeichnungen verwenden, die nicht aus dem Aufgabentext stammen, müssen Sie diese erklären. Die Aufgaben können in \underline{beliebi}g\underline{er Reihenfol}g\underline{e} bearbeitet werden. Zum Bestehen der Klausur sind 25 Punkte erforderlich. Viel Erfolg!

Aufgabe 1. Geben Sie für die folgenden Begriffe jeweils eine vollständige Definition an.

(a) Verband. 1 Punkt

(a) Index einer Untergruppe U in einer Gruppe G. 1 Punkt

(c) Primitives Element eines Körpers K. 2 Punkte

Aufgabe 2. Es sei ≤ die kleinste Halbordnung auf der Menge A := {1, 2, 3, 4, 5, 6}, die die Relation R := {(1, 3), (2, 3), (3, 6), (2, 4), (4, 6), (2, 5), (5, 6)} umfaßt, und μ die zugehörige Möbiusfunktion.

(a) Zeichnen Sie das Hasse-Diagramm von (A, ≤). 1 Punkt

(b) Leiten Sie daraus μ(2, 6) her (nicht nur das Ergebnis hinschreiben). 1 Punkt

(c) Stellen Sie die zu (A, ≤) gehörige Inzidenzmatrix auf. 2 Punkte

(d) Berechnen Sie daraus die Matrix [μ(i, j)]. 2 Punkte

(e) Ist (A, ≤) ein Verband? (Antwort mit Begründung) 1 Punkte

Aufgabe 3. Es sei φ die Euler’sche Funktion und μ die zahlentheoretische Moebius-Funktion.

(a) Berechnen Sie φ(n) und μ(n) für n = 250. 2 Punkte

(b) Berechnen Sie die natürliche Zahle z mit 0 ≤ z < 250 und 7^{8002} ≡ z mod 250. 3 Punkte

Nachholklausur zur Vorlesung Diskrete Strukturen (5. 10. 93) Blatt 2

Aufgabe 4. Es sei φ = π_{2}(π′_{1} + π_{3}) + π_{3}(π_{1} + π′_{3}) eine Schaltfunktion in P_{3}.

(a) Berechnen Sie die disjunktive Normalform von φ. 3 Punkte

(b) Berechnen Sie die konjunktive Normalform von φ. 3 Punkte

Aufgabe 5. Es sei R = ZZ_{2}[X] / (X^{3}+X^{2}+X). Berechnen Sie alle Einheiten in R und zu jeder Einheit das dazu inverse Element. 7 Punkte

Aufgabe 6. Ein regelmäßiges Tetraeder soll so gefärbt werden, daß nicht die Flächen, sondern nur die (sechs) Kanten mit je einer Farbe angemalt werden. Wie viele (bis auf Drehungen) verschiedene Tetraeder kann man erhalten, wenn drei verschiedene Farben zur Verfügung stehen?

7 Punkte

Aufgabe 7. Die kleine Lisa muß die beiden Käfige ihrer Meerschweinchen und Wüstenmäuse regelmäßig alle 4 bzw. alle 15 Tage reinigen. Heute ist Dienstag, und sie freut sich, daß die Meerschweinchen erst morgen und die Mäuse erst am Dienstag in der nächsten Woche wieder dran sind. Einmal schon mußte sie an einem Sonntag beide Käfige reinigen, und sie fragt sich, wieviele Tage das schon her ist und wieviele Tage es noch dauert, bis wieder so ein Sonntag kommt.

7 Punkte

Aufgabe 8. In ZZ_{2}[X] seien die Polynome f_{1} = X^{8} + X^{6} + 1 und f_{2} = X^{7} + X^{6} + X^{4} + 1 gegeben.

(a) Berechnen Sie mit Hilfe des Euklidischen Algorithmus d ∈ ggT(f_{1}, f_{2}). 5 Punkte

(b) Stellen Sie d in der Form a·f_{1} + b·f_{2} mit a, b ∈ ZZ_{2}[X] dar. 2 Punkte

Aufgabe 9. Es sei f = X^{6} − X^{5} + X^{4} − X^{3} − 1 ∈ ZZ_{3}[X]. Zerlegen Sie f mit Hilfe des Berlekamp-Algorithmus in irreduzible Faktoren. 7 Punkte