Nachholklausur zu Diskreten Strukturen

(SS 90)

Prof. Dr. Pahlings

Bitte bearbeiten Sie auf jedem Blatt nur eine Aufgabe und schreiben Sie auf jedes Blatt Ihren Namen. Tragen Sie auf das Deckblatt, welches Sie Ihren Lösungen beiheften, Ihren Namen, Ihre Matrikelnummer sowie den Namen Ihres Übungsgruppenleiters ein. Es sind keine Hilfsmittel zugelassen. Die Bearbeitungszeit beträgt 150 Minuten. Zum Bestehen der Klausur müssen mindestens 25 Punkte erreicht werden. Bitte beachten Sie, daß ausführliche Begründungen einen wesentlichen Teil der Lösung einer Aufgabe bilden. Die Aufgaben können in beliebiger Reihenfolge bearbeitet werden. Viel Erfolg!

Wir machen darauf aufmerksam, daß bis zum Ende des auf die Vorlesung folgenden Semesters nicht abgeholte Klausuren (und Übungen) vernichtet werden. Anspruch auf Anrechnen besteht dann nicht mehr. Aufgabe 1. Sei M = {1, 2, 3, 4, 5, 6, ∞} mit einer Relation ≤ definiert durch

a ≤ b ⇔ entweder b = ∞ oder a, b ∈ {1, 2, 3, 4, 5, 6} und a | b

(für a, b ∈ M).

(a) Zeigen Sie, daß ≤ eine Ordnung ist, und zeichnen Sie das zugehörige Hasse-Diagramm.

(b) Ist (M, ≤) ein Verband? Wenn ja, ist dieser Verband distributiv und/oder komplementär? Begründen Sie Ihre Antworten.

(c) Sei μ die zugehörige Moebius-Funktion. Berechnen Sie μ(1, ∞). 8 Pkte.

Aufgabe 2. Sei φ die Euler’sche Funktion und μ die zahlentheoretische Moebius-Funktion. Berechnen Sie φ(n) und μ(n) für n = 199, 187, 150. 6 Pkte.

Aufgabe 3. Sei G die Gruppe der Einheiten (= bzgl. Multiplikation invertierbaren Elemente) des Ringes ZZ/20ZZ. Prüfen Sie nach, ob G zyklisch ist, und berechnen Sie alle Untergruppen von G. 8 Pkte.

Aufgabe 4. Sei C der von den Vektoren 1 0 1 0, 1 1 1 1 (als Teilraum von ZZ_{2}^{4}) aufgespannte Gruppencode.

(a) Berechnen Sie die Minimaldistanz δ(C).

(b) Zeigen Sie, daß C ein zyklischer Code ist.

(c) Berechnen Sie das Genertorpolynom von C. 8 Pkte.

Aufgabe 5. Sei ϕ = (π_{1} + π_{3})π_{1}π_{2} + π_{1}π′_{2} eine Schaltfunktion in P_{3}. Berechnen Sie die konjunktive und disjunktive Normalform von ϕ. 6 Pkte.

Aufgabe 6. Berechnen Sie ein Polynom f ∈ ZZ_{3}[X] kleisten Grades mit

X + 1 | f − 1, X | f + X + 1, X − 1 | f + 1.

(Alle Polynome und die Teilbarkeit aufgefaßt in ZZ_{3}[x].) 6 Pkte.

Aufgabe 7. Sei f = X^{5} + X^{4} + X^{3} + X^{2} + X + 1 ∈ ZZ_{2}[X].

(a) Berechnen Sie d ∈ ggT(f, f′).

(b) Zerlegen Sie f mit Hilfe des Berlekamp-Algorithmus in irreduzible Faktoren. 8 Pkte.

Aufgabe 8. Sei f = X^{3} + X + 1 ∈ ZZ_{2}[X], K = ZZ_{2}[X]/(f) und z := X + (f) ∈ K.

(a) Zeigen Sie, daß K ein Körper ist.

(b) Berechnen Sie die Ordnung von z als Element der multiplikativen Gruppe von K. 6 Pkte.