Kurs:Diskrete Mathematik/7/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	3	3	4	3	0	2	0	8	2	0	1	0	0	0	0	0	0	32

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine endliche Menge ${}M$ mit ${}n$ Elementen.
2. Ein größtes Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Zwei teilerfremde natürliche Zahlen ${}a$ und ${}b$.
4. Ein kantenfreier Graph ${}G=(V,E)$.
5. Eine Paarung in einem Graphen ${}G=(V,E)$.
6. Das chromatische Polynom eines Graphen ${}G$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Teilmengenanzahl einer endlichen Menge.
2. Der Satz über die Äquivalenzrelation zu einer Abbildung ${}f\colon M\rightarrow N$.
3. Der Satz von Ore.

Aufgabe * (3 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}20$ Cent begleichen?

Aufgabe * (3 Punkte)

Die Puzzleteile für ein Puzzle haben eine grob rechteckige Form, wobei die eine Seite erkennbar länger als die andere ist, und auf jeder Seite gibt es entweder eine Einbuchtung oder eine Ausbuchtung. Wie viele Typen von Puzzelteilen gibt es?

Aufgabe * (4 Punkte)

Beweise den Satz über die Anzahl von bijektiven Abbildungen.

Aufgabe * (3 Punkte)

Wie viele Teilquadrate mit positiver Seitenlänge gibt es in einem Quadrat der Seitenlänge ${}5$? Die Seiten der Teilquadrate sollen wie im Bild auf dem „Gitter“ liegen, ein einzelner Punkt gelte nicht als Quadrat.

Aufgabe (0 Punkte)

Aufgabe * (2 Punkte)

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${}G$.

Aufgabe (0 Punkte)

Aufgabe * (8 (1+2+3+2) Punkte)

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$.

Der Algorithmus geht folgendermaßen. Wenn ${}a\neq b$ ist, so ersetzte das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ${}a=b$ ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

1. Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
4. Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Aufgabe * (2 Punkte)

Zeige, dass die auf ${}\mathbb {Z} \times \mathbb {N} _{+}$ durch

$(a,b)\sim (c,d),{\text{ falls }}ad=bc,$

festgelegte Relation eine Äquivalenzrelation ist.

Aufgabe (0 Punkte)

Aufgabe * (1 Punkt)

Bei einem vollständigen ungerichteten Graphen mit ${}4$ Ecken ist jede Ecke mit jeder (anderen) Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)