Kurs:Diskrete Mathematik/15/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Die Kommutativität einer Verknüpfung
$\circ \colon M\times M\longrightarrow M.$
Ein Atom ${}a\in M$ in einer geordneten Menge ${}(M,\preccurlyeq )$ mit einem kleinsten Element ${}0$ .
Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$ .
Die Isomorphie von Abbildungen ${}f_{1}\colon L_{1}\rightarrow M_{1}$ und ${}f_{2}\colon L_{2}\rightarrow M_{2}$ .
Der Quotientengraph zu einer Äquivalenzrelation ${}\sim$ auf einem Graphen ${}G=(V,E)$ .
Eine maximale Paarung ${}P\subseteq E$ in einem Graphen ${}G=(V,E)$ .

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

Der Satz über die atomare Darstellung in einem booleschen Verband.
Der Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.
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 * (2 Punkte)

Berechne

(x+{\mathrm {i} }y)^{n}.

Aufgabe * (6 (3+3) Punkte)

Wir betrachten eine Rekursionsvorschrift, die zu einem 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.

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

Aufgabe * (2 Punkte)

Skizziere vier Geraden in der Ebene, die sich insgesamt in genau drei Punkten schneiden.
Skizziere vier Geraden in der Ebene, die sich in keinem Punkt schneiden.
Skizziere vier Geraden in der Ebene, die sich in einem Punkt schneiden.
Skizziere vier Geraden in der Ebene, die sich insgesamt in sechs Punkten schneiden.

Aufgabe * (7 Punkte)

Beweise das allgemeine Distributivgesetz für einen kommutativen Halbring.

Aufgabe * (2 Punkte)

Berechne

(-x^{2}+x-1)^{3}.

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 * (3 Punkte)

Bestimme das kleinste gemeinsame Vielfache und den größten gemeinsamen Teiler der drei Zahlen

3^{4}\cdot 5^{2},\,2^{4}\cdot 3^{3}\cdot 5^{1}\cdot 7^{1},\,2^{5}\cdot 3^{2}\cdot 5^{2}.

Die Ergebnisse sollen ausgerechnet vorliegen.

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 * (2 Punkte)

Es sei ${}f\colon \mathbb {R} \longrightarrow \mathbb {R}$ , ${}x\longmapsto 2x$ , die Multiplikation mit ${}2$ und ${}g\colon \mathbb {R} \longrightarrow \mathbb {R}$ , ${}x\longmapsto 8x$ , die Multiplikation mit ${}2$ . Zeige, dass ${}f$ und ${}g$ zueinander konjugiert sind.