Kurs:Diskrete Mathematik/22/Klausur mit Lösungen

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein gemeinsamer Teiler von natürlichen Zahlen ${}a_{1},\ldots ,a_{k}$.
2. Geordnete Menge/Teilmenge/Infimum/Definition/Begriff
3. Verband/Ordnung/Definition/Begriff
4. Ungerichteter Graph/Kantengraph/Definition/Begriff
5. Ungerichteter Graph/Weg/Definition/Begriff
6. Ein planarer Graph.

Lösung

1. Eine natürliche Zahl ${}t$ heißt gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}t$ jedes ${}a_{i}$ teilt für ${}i=1,\ldots ,k$.
2. Geordnete Menge/Teilmenge/Infimum/Definition/Begriff/Inhalt
3. Verband/Ordnung/Definition/Begriff/Inhalt
4. Ungerichteter Graph/Kantengraph/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Weg/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Planar/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Es sei ${}M$ eine endliche Menge und ${}\varphi \colon M\rightarrow M$ eine Abbildung. Es sei ${}\varphi ^{n}$ die ${}n$-fache Hintereinanderschaltung von ${}\varphi$ mit sich selbst. Zeige, dass es natürliche Zahlen ${}m>n\geq 1$ mit ${}\varphi ^{n}=\varphi ^{m}$ gibt.

Lösung

Da ${}M$ endlich ist, ist auch die Abbildungsmenge ${}\operatorname {Abb} \,{\left(M,M\right)}$ endlich, da es für jedes Element nur ${}{\#\left(M\right)}$ viele Möglichkeiten gibt, wohin es abgebildet werden kann. Die Hintereinanderschaltungen ${}\varphi ^{n}$, ${}n\in \mathbb {N}$, gehören alle zu dieser Abbildungsmenge. Da es keine injektive Abbildung von ${}\mathbb {N} _{+}$ in eine endliche Menge gibt, gibt es Zahlen ${}m\neq n$ mit

${}\varphi ^{m}=\varphi ^{n}\,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

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

Lösung

Der Euklidische Algorithmus liefert:

$10868=1\cdot 9243+1625$

$9243=4\cdot 1625+1118$

$1625=1\cdot 1118+507$

$1118=2\cdot 507+104$

$507=4\cdot 104+91$

$104=1\cdot 91+13$

$91=7\cdot 13+0.$

Der größte gemeinsame Teiler von ${}10868$ und ${}9243$ ist also ${}13$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung