Kurs:Diskrete Mathematik/11/Klausur mit Lösungen
Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Punkte | 3 | 3 | 3 | 0 | 4 | 0 | 3 | 4 | 0 | 0 | 1 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 25 |
Aufgabe (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Ein kommutativer Ring .
- Eine Relation auf einer Menge .
- Die Folge der euklidischen Reste zu ganzen Zahlen mit .
- Die Automorphismengruppe eines ungerichteten Graphen .
- Der Umfang eines zyklischen Graphen .
- Eine zulässige Färbung eines Graphen .
- Ein Ring heißt kommutativ, wenn die Multiplikation kommutativ ist.
- Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .
- Man nennt die durch die Anfangsbedingungen
und
und die mittels
der Division mit Rest
rekursiv bestimmte Folge die Folge der euklidischen Reste.
- Zu einem
Graphen
nennt man die
Gruppe
aller
Automorphismen
die Automorphismengruppe von .
- Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .
- Eine
Färbung
heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
- Der Satz über die Beziehung zwischen der Addition und endlichen Mengen.
- Der Satz über die Restklassenkörper von .
- Der Rekursionssatz für aufspannende Bäume.
- Es seien und disjunkte endliche Mengen mit bzw. Elementen. Dann besitzt ihre Vereinigung gerade Elemente.
- Es sei . Der Restklassenring ist genau dann ein Körper, wenn eine Primzahl ist.
- Es sei ein schleifenfreier
Multigraph
und eine Kante von . Dann besteht für die Anzahl der
aufspannenden Bäume
der Zusammenhang
Aufgabe (3 Punkte)
Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?
Das Pickelpaar und die drei übrigen einzelnen Pickel können als vier Pickelfelder betrachtet werden, die in beliebiger Reihenfolge beackert werden könnnen. Dafür gibt es Möglichkeiten. Bei jeder dieser Reihenfolge hat man beim Pickelpaar die freie Wahlmöglichkeit, welcher zuerst drankommt. Daher gibt es insgesamt
Möglichkeiten.
Aufgabe (0 Punkte)
Aufgabe (4 (1+1+1+1) Punkte)
Wir betrachten den Binomialkoeffizienten als eine Verknüpfung
wobei bei der Binomialkoeffizient als zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.
- Besitzt diese Verknüpfung ein neutrales Element von links?
- Besitzt diese Verknüpfung ein neutrales Element von rechts?
- Bestimme und .
- Ist diese Verknüpfung assoziativ?
- Es kann kein neutrales Element von links geben, da für
gilt
- ist das neutrale Element von rechts. Für
ist
und dies gilt auch für .
- Es ist
und
- Die Verknüpfung ist nich assoziativ, beispielsweise ist
aber
Aufgabe (0 Punkte)
Aufgabe (3 Punkte)
Es sei ein Monoid, und . Zeige die folgenden Potenzgesetze.
- Wenn
kommutativ
ist, so ist
Lösung Monoid/Potenzgesetze/Fakt/Beweis/Aufgabe/Lösung
Aufgabe (4 Punkte)
Es sei eine Menge und eine Ordnung auf . Zeige durch Induktion über die Aussage: Wenn für Elemente die Beziehung
und
gilt, dann sind alle gleich.
Der Induktionsanfang folgt unmittelbar aus der Antisymmetrie. Es sei also die Aussage für ein gewisses schon bewiesen und es liegen Elemente mit den Abschätzungen
und
vor. Wegen der Transitivität der Ordnung gilt dann auch
und damit gelten auch die Bedingungen in der Induktionsvoraussetzung. Somit ist also
Wegen
und
stimmt auch mit diesem Element überein.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (1 Punkt)
Finde eine Darstellung der für das Zahlenpaar und .
Es ist
Aufgabe (0 Punkte)
Aufgabe (4 Punkte)
Es sei eine Gruppe. Betrachte die Relation auf , die durch
erklärt ist. Zeige, dass eine Äquivalenzrelation ist.
Die Relation ist offenbar reflexiv. Zum Nachweis der Symmetrie sei . Im Fall ist natürlich auch und somit . Im Fall
ergibt sich durch Invertieren der Gleichung
also ebenfalls . Zum Nachweis der Transitivität sei und . Hier gibt es insgesamt vier Fälle. Bei und ist natürlich . Bei und ist , also . Bei und ist , also wieder . Bei und ist
also .
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)