Kurs:Diskrete Mathematik/20/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	6	6	0	2	2	5	1	4	2	3	3	4	4	3	3	2	3	59

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Untergruppe ${}H$ in einer Gruppe ${}G$.
2. Eine rechtsvollständige Relation  ${}R\subseteq M\times N$. 
3. Ein Supremum zu einer Teilmenge  ${}J\subseteq I$  in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Die Nachbarschaft zu einem Punkt  ${}v\in V$  in einem Graphen  ${}G=(V,E)$. 
5. Der Radius eines zusammenhängenden Graphen  ${}G=(V,E)$. 
6. Eine optimale Knotenüberdeckung eines Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die algebraische Struktur der Restklassenringe ${}R/{\mathfrak {a}}$ zu einem Ideal  ${}{\mathfrak {a}}\subseteq R$  in einem kommutativen Ring ${}R$.
2. Der Satz über die explizite Lösung einer Matrixrekursion im diagonalisierbaren Fall.
3. Der Vier-Farben-Satz.

Aufgabe (6 Punkte)

Man gebe ein Beispiel für eine kombinatorische Formel, die sowohl direkt als auch durch eine inhaltliche Überlegung bewiesen werden kann. Man führe beide Beweise vor.

Aufgabe * (6 (1+1+2+2) Punkte)

Professor Knopfloch möchte mit Dr. Eisenbeis essen gehen und hebt daher beim Bankautomat ${}100$ Euro in Scheinen ab.

1. Was ist die minimale Anzahl von Scheinen und was ist die maximale Anzahl von Scheinen, die er bekommen kann?
2. Ist es möglich, dass er ${}17$ Scheine bekommt?
3. Welche Anzahlen von Scheinen sind möglich?
4. Was ist die kleinste Anzahl von Scheinen, für die es zumindest zwei verschiedene Scheinverteilungen gibt?

Aufgabe (0 Punkte)

Aufgabe * (2 Punkte)

Heute ist Freitag. Welcher Wochentag ist in ${}1000$ Tagen?

Aufgabe * (2 Punkte)

Skizziere sieben Geraden in der Ebene, die sich insgesamt in acht Punkten schneiden.

Aufgabe * (5 Punkte)

Beweise den binomischen Lehrsatz für einen kommutativen Halbring ${}R$.

Aufgabe * (1 Punkt)

Es sei ${}G$ eine Gruppe. Es seien  ${}x,y\in G$  Elemente mit

${}x\cdot y=1\,$

Zeige, dass ${}y$ das Inverse von ${}x$ ist.

Aufgabe * (4 Punkte)

Es seien ${}m$ und ${}n$ teilerfremde natürliche Zahlen. Zeige, dass der Binomialkoeffizient ${}{\binom {m+n}{m}}$ von ${}m+n$ geteilt wird.

Aufgabe * (2 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1071$ und ${}1029$.

Aufgabe * (3 Punkte)

Zeige durch Induktion, dass jede natürliche Zahl  ${}n\geq 2$  eine Zerlegung in Primzahlen besitzt.

Aufgabe * (3 (1+2) Punkte)

Wir betrachten auf den komplexen Zahlen die Relation, bei der zwei Zahlen ${}z,w$ als äquivalent gelten, wenn ihre ${}17$-te Potenz übereinstimmt.

1. Zeige, dass dies eine Äquivalenzrelation ist.
2. Wie viele Elemente beinhalten die Äquivalenzklassen (verwende, dass es ${}17$ komplexe Zahlen mit  ${}z^{17}=1$  gibt)?

Aufgabe * (4 Punkte)

Zu  ${}n,k\in \mathbb {N}$  bezeichne ${}\operatorname {surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge. Zeige, dass die Rekursionsformel

${}\operatorname {surj} (n+1,k)=k\cdot \operatorname {surj} (n,k)+k\cdot \operatorname {surj} (n,k-1)\,$

gilt.

Aufgabe * (4 Punkte)

Erstelle ein Kartenspiel mit insgesamt sieben Symbolen und sieben Karten, wobei auf jeder Karte drei Symbole vorkommen mit der Eigenschaft, dass je zwei Karten genau ein Symbol gemeinsam haben.

Aufgabe * (3 Punkte)

Bestimme die verschiedenen Typen zu den Permutationen auf einer vierelementigen Menge sowie die Anzahl der Permutationen, die diesen Typ besitzen.

Aufgabe * (3 Punkte)

Es sei ${}M$ eine ${}d\times d$- Matrix über dem Körper ${}K$ mit der zugehörigen linear-rekursiven Folge  ${}v_{n}\in K^{d}$  zum Startvektor  ${}v_{0}\in K^{d}$.  Es sei ${}L$ eine invertierbare ${}d\times d$-Matrix und sei

${}N=LML^{-1}\,$

und  ${}w_{0}=L{\left(v_{0}\right)}\in K^{d}$.  Zeige, dass die linear-rekursive Folge ${}w_{n}$ zur Matrix ${}N$ und zum Startvektor ${}w_{0}$ die Beziehung

${}w_{n}=L{\left(v_{n}\right)}\,$

für alle ${}n$ erfüllt.

Aufgabe (2 Punkte)

Skizziere den Nullteilergraphen zum Ring ${}\mathbb {Z} /(10)$ überschneidungsfrei.

Aufgabe (3 Punkte)

Zeige, dass die Verbundenheit zwischen Knotenpunkten in einem Graphen  ${}G=(V,E)$  eine Äquivalenzrelation auf der Knotenmenge ${}V$ ist.