Kurs:Diskrete Mathematik/24/Klausur
| Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Punkte | 3 | 3 | 2 | 3 | 6 | 2 | 3 | 5 | 2 | 2 | 3 | 6 | 2 | 5 | 5 | 3 | 4 | 4 | 1 | 64 |
Aufgabe * (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Die Assoziativität einer
Verknüpfung
- Eine Ordnungsrelation auf einer Menge .
- Die Äquivalenzklasse zu einem Element in einer Menge mit einer Äquivalenzrelation .
- Ein Automorphismus eines Graphen .
- Das charakteristische Polynom zu einem Graphen .
- Ein Hamiltonkreis in einem Graphen .
Aufgabe * (3 Punkte)
Formuliere die folgenden Sätze.
- Der Satz über das asymptotische Verhalten von fixpunktfreien Permutationen.
- Die Rekursionsformel für die Stirling-Zahlen zweiter Art.
- Die eulersche Polyederformel.
Aufgabe * (2 Punkte)
Professor Knopfloch und Dr. Eisenbeis stehen am Ufer des Rubbenbruchsees und können sich nicht einigen, ob sie mit dem oder gegen den Uhrzeigersinn drumrum laufen sollen. Deshalb läuft Professor Knopfloch gegen den Uhrzeigersinn und Dr. Eisenbeis mit dem Uhrzeigersinn. Das Verhältnis ihrer Geschwindigkeiten ist , und daher läuft Knopfloch fünfmal um den See und Eisenbeis viermal um den See. Wie oft begegnen sie sich (Begegnung ganz am Anfang und am Ende mitzählen)?
Aufgabe * (3 (1+1+1) Punkte)
Die Fußballmannschaft des TSV Wildberg verfügt über drei Torwarte, sieben Verteidigungsspieler, sechs Mittelfeldspieler und vier Angreifer. Im anstehenden Spiel gegen Effringen will sie (neben einem Torwart) mit vier Verteidigern, drei Mittelfeldspielern und drei Angreifern agieren.
- Wie viele Aufstellungsmöglichkeiten gibt es?
- Wie viele Aufstellungsmöglichkeiten gibt es, wenn man zusätzlich noch berücksichtigt, dass einer der eingesetzten Spieler der Kapitän sein soll?
- Wildberg geht in der Minute mit in Führung und entschließt sich, die Verteidigung zu stärken, indem zwei Angreifer durch zwei Verteidiger ersetzt werden. Wie viele Auswechselmöglichkeiten gibt es dafür?
Aufgabe * (6 Punkte)
Es sei eine Menge und es seien , , endliche Teilmengen. Für eine Teilmenge sei
Beweise die Anzahlformel (Siebformel)
Aufgabe * (2 Punkte)
Skizziere möglichst viele wesentlich verschiedene Konfigurationen von fünf Geraden in der Ebene, die sich insgesamt in vier Schnittpunkten treffen.
Aufgabe * (3 Punkte)
Zeige, dass die Anzahl der Permutationen auf einer -elementigen Menge, die ein voller Zyklus sind, gleich ist.
Aufgabe * (5 Punkte)
Es sei eine fixierte natürliche Zahl und
Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)
und
Zeige, dass mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.
Aufgabe * (2 (1+1) Punkte)
Es seien natürliche Zahlen mit .
- Bestimme .
- Bestimme .
Aufgabe * (2 Punkte)
Bestimme für das Polynom
den Grad, den Leitkoeffizienten, den Leitterm und den Koeffizienten zu .
Aufgabe * (3 Punkte)
Zeige, dass die folgende Relation eine Äquivalenzrelation auf ist:
Aufgabe (6 (3+3) Punkte)
Es sei ein Körper und sei
die Menge aller invertierbaren
-Matrizen.
a) Zeige (ohne Bezug zur Determinante), dass mit der Matrizenmultiplikation eine Gruppe bildet.
b) Zeige
(ohne Bezug zur Determinante),
dass die Abbildung
ein Gruppenhomomorphismus ist.
Aufgabe * (2 Punkte)
Zeige, dass es keinen Ringhomomorphismus von nach gibt.
Aufgabe * (5 Punkte)
Es sei eine endliche Menge und eine Permutation auf . Zeige, dass es eine Darstellung
gibt, wobei die Zyklen der Ordnung sind mit disjunkten Wirkungsbereichen.
Aufgabe * (5 (3+2) Punkte)
Zu sei der minimale Eurobetrag, für den man mindestens Euromünzen/Scheine braucht, um diesen Betrag zu begleichen.
- Erstelle eine Tabelle, aus der die Werte für ablesbar sind!
- Was ist ?
Aufgabe * (3 Punkte)
Bestimme die erzeugende Funktion zur Folge der Fibonacci-Zahlen.
Aufgabe (4 Punkte)
Man erläutere grundlegende graphentheoretische Konzepte anhand der Osnabrücker U-Bahn!
Aufgabe * (4 Punkte)
Zeige, dass ein gerichteter Graph auf der Menge genau dann symmetrisch ist, wenn für jede Teilmenge die Beziehung
gilt.
Aufgabe * (1 Punkt)
Man gebe ein Beispiel für eine maximale Paarung in einem Graphen , die nicht optimal ist.