Zum Inhalt springen

Kurs:Diskrete Mathematik/24/Klausur

Aus Wikiversity



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.

  1. Die Assoziativität einer Verknüpfung
    ∘:M×M⟶M,(x,y)⟼x∘y.
  2. Eine Ordnungsrelation ≼ auf einer Menge I.
  3. Die Äquivalenzklasse zu einem Element x∈M in einer Menge M mit einer Äquivalenzrelation ∼.
  4. Ein Automorphismus eines Graphen  G=(V,E). 
  5. Das charakteristische Polynom zu einem Graphen G.
  6. Ein Hamiltonkreis in einem Graphen (V,E).



Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über das asymptotische Verhalten von fixpunktfreien Permutationen.
  2. Die Rekursionsformel für die Stirling-Zahlen zweiter Art.
  3. 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 5:4, 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.

  1. Wie viele Aufstellungsmöglichkeiten gibt es?
  2. Wie viele Aufstellungsmöglichkeiten gibt es, wenn man zusätzlich noch berücksichtigt, dass einer der eingesetzten Spieler der Kapitän sein soll?
  3. Wildberg geht in der 80. Minute mit 1:0 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 G eine Menge und es seien Ai⊆G, i=1,…,n, endliche Teilmengen. Für eine Teilmenge  J⊆{1,…,n}  sei

AJ=⋂i∈JAi.

Beweise die Anzahlformel (Siebformel)

#(⋃i=1nAi)=∑k=1n(−1)k+1(∑J⊆{1,…,n},#(J)=k#(AJ)).



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 n-elementigen Menge, die ein voller Zyklus sind, gleich (n−1)! ist.



Aufgabe * (5 Punkte)

Es sei n eine fixierte natürliche Zahl und

M={1,…,n}.

Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)

M×M⟶M,(a,b)⟼max⁡(a,b),

und

M×M⟶M,(a,b)⟼min⁡(a,b).

Zeige, dass M mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.



Aufgabe * (2 (1+1) Punkte)

Es seien a,m,n natürliche Zahlen mit  a≥1. 

  1. Bestimme ggT⁡(am,an).
  2. Bestimme kgV⁡(am,an).



Aufgabe * (2 Punkte)

Bestimme für das Polynom

P=−6X9−5X8−4X7+19X6+X2+X

den Grad, den Leitkoeffizienten, den Leitterm und den Koeffizienten zu X6.



Aufgabe * (3 Punkte)

Zeige, dass die folgende Relation eine Äquivalenzrelation auf ℤ ist:

x∼y, falls 6 ein Teiler von x−y ist.



Aufgabe (6 (3+3) Punkte)

Es sei K ein Körper und sei

M={(abcd)∣a,b,c,d∈K,ad−bc≠0}

die Menge aller invertierbaren 2×2-Matrizen.

a) Zeige (ohne Bezug zur Determinante), dass M mit der Matrizenmultiplikation eine Gruppe bildet.


b) Zeige (ohne Bezug zur Determinante), dass die Abbildung

M⟶K×,(abcd)⟼ad−bc,

ein Gruppenhomomorphismus ist.



Aufgabe * (2 Punkte)

Zeige, dass es keinen Ringhomomorphismus von ℂ nach ℝ gibt.



Aufgabe * (5 Punkte)

Es sei M eine endliche Menge und σ eine Permutation auf M. Zeige, dass es eine Darstellung

σ=σ1⋯σk

gibt, wobei die σi Zyklen der Ordnung ≥2 sind mit disjunkten Wirkungsbereichen.



Aufgabe * (5 (3+2) Punkte)

Zu  n∈ℕ  sei f(n) der minimale Eurobetrag, für den man mindestens n Euromünzen/Scheine braucht, um diesen Betrag zu begleichen.

  1. Erstelle eine Tabelle, aus der die Werte für f(n) ablesbar sind!
  2. Was ist f(1000000)?



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 M genau dann symmetrisch ist, wenn für jede Teilmenge  T⊆M  die Beziehung

T⊆M∖Vorg⁡(M∖Vorg⁡(T))

gilt.



Aufgabe * (1 Punkt)

Man gebe ein Beispiel für eine maximale Paarung in einem Graphen G, die nicht optimal ist.