Klausur zur Vorlesung Diskrete Strukturen (SS 93)

Professor Dr. H. Pahlings

Bearbeitungszeit: 120 Minuten zuzüglich 10 Minuten Lesezeit

Bitte bearbeiten Sie auf jedem Blatt nur eine Aufgabe und schreiben Sie auf jedes Blatt Ihren Namen. Es sind keine Hilfsmittel zugelassen, insbesondere keine schriftlichen Aufzeichnungen und keine elektronischen Rechengeräte. 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. 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) Charakteristik eines Körpers K. 2 Punkte

(b) Stabilisator eines Elements x einer Menge M, auf der eine Gruppe G operiert. 1 Punkt

(c) Irreduzibilität eines Polynoms über einem Körper K. 2 Punkte

Aufgabe 2. Auf der Menge M = {2, 3, 4, 5, 6, 7, 8} definieren wie mit Hilfe der Eulerschen φ-Funktion eine Relation ⊴ durch

m ⊴ n ⇔ m = n oder φ(m) < φ(n).

(a) Zeichnen Sie das Hasse-Diagramm von (M, ⊴). 3 Punkte

(b) Ist (M, ⊴) ein Verband? (Antwort mit Begründung) 2 Punkte

(c) Es sei μ die zugehörige Möbiusfunktion. Berechnen Sie μ(2, 7). 2 Punkte

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

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

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

Klausur zur Vorlesung Diskrete Strukturen (SS 93) Blatt 2

Aufgabe 4. Es sei C der von den Vektoren 1 0 1 1 0 und 0 1 1 0 1 (als Teilraum von ZZ_{2}^{5}) aufgespannte Gruppencode.

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

(b) Bestimmen Sie Restklassenführer für alle Restklassen von C in ZZ_{2}^{5}. 3 Punkte

(c) Decodieren sie die Worte 0 0 1 0 1 und 1 1 1 0 0. 1 Punkt

Aufgabe 5.

(a) Bestimmen Sie alle Drehungen und Spiegelungen der Ebene, die ein regelmäßiges Fünfeck in sich überführen, und geben Sie sie als Permutationen auf den fünf Ecken an. 3 Punkte

(b) Berechnen Sie unter Benutzung von (a), wieviele verschiedene Typen von Perlenketten mit 5 Perlen es gibt, wenn jede Perle blau, rot, grün oder gelb sein kann? 3 Punkte

Aufgabe 6.

(a) Es sei φ die Eulersche φ-Funktion. Berechnen Sie φ(1000). 2 Punkte

(b) Berechnen Sie die letzten drei Ziffern in der Dezimaldarstellung der Zahl 101^{8805}. 3 Punkte

(c) Welche der Restklassen [7]_{1000}, [5]_{1000} und [14]_{1000} in ZZ/1000ZZ sind invertierbar, welche sind Nullteiler? (Antwort mit Begründung) 2 Punkte

Aufgabe 7. Drei Kometen statten alle 11, 8 bzw. 21 Jahre der Erde einen Besuch ab. Zuletzt waren sie vor 2, 5 bzw. 1 Jahren hier. Wann werden sie das nächste Mal alle gleichzeitig da sein, wann waren sie das letzte Mal alle gleichzeitig da? 7 Punkte

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

(a) Berechnen Sie d ∈ ggT(f_{1}, f_{2}). 4 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^{5} + X^{2} + 1 ∈ ZZ_{2}[X]. Untersuchen Sie mit Hilfe des Berlekamp-Algorithmus, ob f irreduzibel ist. 7 Punkte