Kurs:Diskrete Mathematik/20/Klausur mit Lösungen/kontrolle



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




Aufgabe (3 Punkte)


Lösung

  1. Eine Teilmenge heißt Untergruppe von wenn folgendes gilt.
    1. .
    2. Mit ist auch .
    3. Mit ist auch .
  2. Die Relation heißt rechtsvollständig, wenn es zu jedem ein mit gibt.
  3. Geordnete Menge/Teilmenge/Supremum/Definition/Begriff/Inhalt
  4. Ungerichteter Graph/Nachbarn/Definition/Begriff/Inhalt
  5. Ungerichteter Graph/Zusammenhängend/Radius/Definition/Begriff/Inhalt
  6. Graph/Knotenüberdeckung/Optimal/Definition/Begriff/Inhalt


Aufgabe (3 Punkte)


Lösung

  1. Es sei ein kommutativer Ring, ein Ideal und die Quotientenmenge zur durch definierten Äquivalenzrelation auf mit der kanonischen Projektion

    Dann gibt es eine eindeutig bestimmte Ringstruktur auf derart, dass ein Ringhomomorphismus

    ist.
  2. Es sei ein Graph und ein Blatt des Graphen. Dann ist genau dann zusammenhängend, wenn zusammenhängend ist.
  3. Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens vier Farben.


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

Professor Knopfloch möchte mit Dr. Eisenbeis essen gehen und hebt daher beim Bankautomat 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 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?


Lösung

  1. Das Minimum an Scheinen ist (ein Hunderter), das Maximum ist ( Fünfer).
  2. Es ist

    Scheine sind also mit Zehnern und Fünfern möglich.

  3. Es sind die Anzahlen und möglich, mit Scheinen ist es nicht möglich. : ein Hunderter. : zwei Fünfziger. : Es kann höchstens ein Fünfziger vorkommen, mit zwei Zwanzigern bleibt man aber unterhalb von . : Ein Fünfziger und zwei Zwanziger und ein Zehner. : Fünf Zwanziger. Um Scheine zu erreichen kann man sukzessive einen Zwanziger durch zwei Zehner ersetzen. : Zehner. Um Scheine zu erreichen kann man sukzessive einen Zehner durch zwei Fünfer ersetzen.
  4. Bei einem und zwei Scheinen gibt es offenbar nur eine Möglichekeit, mit drei Scheinen geht es gar nicht. Mit vier Scheinen gibt es nur die Möglichkeit , da man ohne den Fünfziger nicht auskommt. Mit Scheinen gibt es die beiden Möglichkeiten entweder fünf Zwanziger oder . Die Antwort ist also .


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

Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .


Lösung

Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:

Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.


Aufgabe (3 (1+2) Punkte)

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

  1. Zeige, dass dies eine Äquivalenzrelation ist.
  2. Wie viele Elemente beinhalten die Äquivalenzklassen (verwende, dass es komplexe Zahlen mit gibt)?


Lösung

  1. Zwei komplexe Zahlen gelten als äquivalent, wenn sie unter der Abbildung

    den gleichen Wert besitzen. In einer solchen Situation liegt stets eine Äquivalenzrelation vor.

  2. Da ein Körper ist, besteht die Äquivalenzklasse zu allein aus , sie ist also einelementig. Die Äquivalenzklasse zu besteht aus den -ten Einheitswurzeln. Für von verschiedene Zahlen ist

    genau dann, wenn

    wenn also eine -te Einheitswurzel ist. Somit besteht die Äquivalenzklasse zu aus der Elementen , wobei die -ten Einheitswurzeln durchläuft.


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