Kurs:Diskrete Mathematik/15/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	2	4	4	6	0	7	0	4	2	0	0	0	0	0	10	0	0	45

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Kommutativität einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M.$

2. Geordnete Menge/Kleinstes Element/Atom/Definition/Begriff
3. Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
4. Ungerichteter Graph/Isomorph/Definition/Begriff
5. Ungerichteter Graph/Äquivalenzrelation/Quotientengraph/Definition/Begriff
6. Ungerichter Graph/Maximale Paarung/Definition/Begriff

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die atomare Darstellung in einem booleschen Verband.
2. Der Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.
3. Der Satz über die Potenzen der Adjazenzmatrix.

Aufgabe * (2 Punkte)

Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?

Aufgabe * (4 Punkte)

Es sei ${}M$ eine ${}n$-elementige Menge. Zeige durch Induktion über ${}k$, dass die Anzahl der ${}k$-elementigen Teilmengen von ${}M$ gleich dem Binomialkoeffizienten

${\binom {n}{k}}$

ist.

Aufgabe * (4 Punkte)

Es sei ${}M$ eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von ${}M$ in die Potenzmenge ${}{\mathfrak {P}}\,(M)$ geben kann.

Aufgabe * (6 (3+3) Punkte)

Wir betrachten eine Rekursionsvorschrift, die zu einen Zahlendreieck (analog zum Pascalschen Dreieck) führt. In der ersten Zeile steht zentral die ${}256$, links und rechts davon stehen unendlich viele ${}1$ (die nicht aufgeführt werden müssen). Die jeweils nächste Zeile entsteht, indem man von zwei benachbarten Zahlen der Vorgängerzeile das geometrische Mittel nimmt und das Ergebnis darunter in der neuen Zeile platziert.

1. Bestimme die ersten Zeilen dieses Zahlendreiecks, bis sämtliche Einträge kleiner als ${}6$ sind.
2. Welche Eigenschaft gilt in jeder Zeile? Warum?

Aufgabe (0 Punkte)

Aufgabe * (7 Punkte)

Beweise das allgemeine Distributivgesetz für einen kommutativen Halbring.

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Zeige, dass es zu ganzen Zahlen ${}d,n$ mit ${}d>0$ eindeutig bestimmte ganze Zahlen ${}k,s$ mit

${}n=kd+s\,$

und mit

${}-{\frac {d}{2}}<s\leq {\frac {d}{2}}\,$

gibt.

Aufgabe * (2 Punkte)

Zeige, dass die Relation auf ${}\mathbb {N} \times \mathbb {N}$, die durch

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

festgelegt ist, eine Äquivalenzrelation ist.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (10 Punkte)

Beweise den Charakterisierungssatz für eulersche Graphen.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)