close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Lösungen zur DIM Klausur im SS 05 Aufgabe 1 Wie - Basil-ell.de

EinbettenHerunterladen
Lösungen zur DIM Klausur im SS 05
Aufgabe 1
Wie viele verschiedene 5-elementige Teilmengen (genaue Zahlangabe) kann eine Menge mit
15 Elementen haben?
Wie viele verschiedene 5-elementige Listen kann man aus einer Menge von 15 Elementen
bilden?
Wenn man aus einer n-elementigen Menge r k-elementige Listen und s k-elementige
Teilmengen bilden kann, in welchem Verhältnis stehen dann r und s?
Lösung:
a) Die Anzahl der 5-elementigen Teilmengen einer Menge mit 15 Elementen ist
⎛15 ⎞
15!
15! 15 ⋅ 14 ⋅ 13 ⋅ 12 ⋅ 11
=
=
= 7 ⋅ 11 ⋅ 13 ⋅ 3 = 3003
⎜⎜ ⎟⎟ =
1⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5
⎝ 5 ⎠ 5!(15 − 5)! 5!⋅10!
b) Die Anzahl der 5-elementigen Listen (bei der Auswahl spielt die Reihenfolge eine
15!
15!
Rolle) ist
=
= 15 ⋅ 14 ⋅ 13 ⋅ 12 ⋅ 11 = 3003 ⋅ 120 = 360360
(15 − 10)! 10!
⎛n⎞
n!
n!
und s = ⎜⎜ ⎟⎟ =
Somit gibt es k! mehr k-elementige Listen als k( n − k )!
⎝ k ⎠ k!( n − k )!
elementige Teilmengen.
c) r =
Aufgabe 2
Ist die Formel (p → q) → ((p ∧ r) → (q ∧ r)) erfüllbar, eine Tautologie oder eine
Kontradiktion?
Antwort:
Um die Frage zu beantworten, erstellen wir eine Wahrheitstafel.
p
0
0
0
0
1
1
1
1
q
0
0
1
1
0
0
1
1
r (p → q) p ∧ r q ∧ r (p ∧ r) → (q ∧ r) (p → q) → ((p ∧ r) → (q ∧ r))
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
0
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
1
1
1
1
Da der Werteverlauf der Formel stets den Wert 1 ergibt, handelt es sich bei der Formel um
eine Tautologie.
Aufgabe 3
Sei R eine binäre Relation über einer Menge A.
Beweisen Sie: R ist transitiv genau dann, wenn R  R ⊆ R ist.
Beweis:
Ist (x,z) ∈ R  R, dann gibt es ein y so dass xRy und yRz. Da R transitiv ist, gilt mit
xRy und yRz auch xRz, also (x,z) ∈ R. Damit ist R  R ⊆ R.
Sei R  R ⊆ R. Für (x,z) ∈ R  R, gibt es y, so dass xRy und yRz. Da R  R ⊆ R gilt
auch (x,z) ∈ R. Somit ist R transitiv.
Aufgabe 4
Beweisen Sie die Gültigkeit der Aussage
n
4k
∑3
k =0
k +1
=1−
2n + 3
3n +1
Beweis durch vollständige Induktion
Induktionsanfang n = 0:
0
4k
∑3
k =0
k +1
= 0 =1−
0+3
3
=1− = 0
0 +1
3
3
Induktionsvoraussetzung:
n
4k
∑3
k =0
k +1
=1−
2n + 3
3n +1
Induktionsbehauptung:
n +1
4k
∑3
k +1
k =0
= 1−
2( n + 1) + 3
2n + 5
= 1 − n+2
( n +1) +1
3
3
Induktionsschluss:
n +1
4k
∑3
k =0
k +1
4k 4( n + 1)
2n + 3 4( n + 1)
6n + 9 4 n + 4
− 6n − 9 + 4 n + 4
+ n + 2 = 1 − n +1 + n + 2 = 1 − n + 2 + n + 2 = 1 +
=
k +1
3
3
3
3
3
3n + 2
k =0 3
2n + 5
− 2n − 5
=1+
= 1 − n+2
n+2
3
3
n
=∑
Aufgabe 5
2
Zeigen Sie, dass die Relation Z ⊆ 2 ×  eine Äquivalenzrelation ist. Dabei ist Z wie folgt
definiert: (a,b)Z(c,d) falls a + d = b + c.
Beweis:
Es muss gezeigt werden, dass die Relation Z reflexiv, symmetrisch und transitiv ist.
a)
Reflexivität
Es gilt (a.b)Z(a,b) falls a + b = b + a.
Dies ist aber wegen der Kommutativität von + der Fall.
Daher ist die Relation Z reflexiv.
b)
Symmetrie
Es gelte (a,b)Z(c,d).
Dann ist nach Definition a + d = b + c.
Dann gilt auch b + c = a + d wegen der Symmetrie von =
Dann gilt auch c + b = d + a wegen der Kommutativität von +
Nach Definition gilt somit (c,d)Z(a,b).
Somit ist die Relation Z symmetrisch.
c)
Transititvität
Es gelte (a,b)Z(c,d) und (c,d)Z(e,f)
Dann gilt nach Definition a + d = b + c und c + f = d + e
Durch Addition folgt a + d + c + f = b + c + d + e
Somit ist auch a + f = b + e
Nach Definition gilt dann (a,b)Z(e,f).
Somit ist die Relation Z transitiv.
Insgesamt ist also die Relation Z eine Äquivalenzrelation.
Aufgabe 6
a) Beweisen Sie, dass für natürliche Zahlen a und b die Relation a ‘teilt’ b eine partielle
Ordnung ist. a ‘teilt’ b ist dann definiert, wenn es eine natürliche Zahl q gibt, so dass
qa = b gilt.
b) Zeichnen Sie ein Hasse-Diagramm für die partiell geordnete Menge aller
Teiler von 60.
Beweis:
a) Es ist zu zeigen, dass die Relation ‘teilt’ reflexiv, antisymmetrisch und transitiv ist.
i. Reflexivität
Es gilt a ‘teilt’ a, da 1⋅a = a
Somit ist die Relation ‘teilt’ reflexiv
ii. Es gelte a ‘teilt’ b und b ‘teilt’ a
Nach Definition gibt es also eine natürliche Zahl q so dass qa = b und es gibt eine
natürliche Zahl q’, so dass q’b = a.
Mithin ist a = qb = qq’a
Somit muss gelten qq’ = 1.
Da q und q’ natürliche Zahlen sein müssen, folgt daraus q = 1 und q’ = 1.
Daraus folgt a = b.
Somit ist die Relation ‘teilt’ antisymmetrisch.
iii. Es gelte a ‘teilt’ b und b ‘teilt’ c.
Nach Defintion gibt es natürliche Zahlen q und q’, so dass qa = b und q’b = c.
Somit ist auch qq’a = c und qq’ ist eine natürliche Zahl k.
Somit ist also ka = c und daher gilt a ‘teilt’ c.
Somit ist die Relation ‘teilt’ transitiv.
Insgesamt ist also die Relation ‘teilt’ eine Ordnungsrelation.
b)
60
12
4
6
2
20
30
10
15
3
5
1
Aufgabe 7
Sei b die Basis eines Zahlsystems.
a)
b)
c)
d)
Wie viele Ziffern hat dieses Zahlsystem?
Wie wird die Zahl b in diesem System dargestellt?
Wie viele Zahlen lassen sich bei Verwendung von n Stellen darstellen?
Wie lautet bei der Verwendung von 8 Ziffern die Darstellung von –1 im bKomplement und welchen Wert im 10er System hat diese Darstellung?
Antwort:
a)
b)
c)
d)
Im b-System gibt es b Ziffern für die Zahlen 0 ... b – 1
Im b-System hat b die Darstellung 10
Es lassen sich bei der Verwendung von n Stellen insgesamt bn Zahlen darstellen.
Sei X die Repräsentation der Ziffer b – 1 im b-System. Dann ist die Darstellung
von – 1 im b System mit 8 Stellen XXXXXXXX. Das entspricht der Zahl (b8 – 1).
Aufgabe 8
Stellen Sie die Zahl 56,65 als Gleitpunktzahl mit einer Wortlänge von 32 Bit dar.
56 hat die Binärdarstellung 111000. Dies kann man z. B. mit dem in der Vorlesung
behandelten Umrechnungsalgorithmus herleiten.
56
28
14
7
3
1
0
0
0
1
1
1
0,65 hat die Binärdarstellung 0,10 1001 1001 ...
0,65
1,3
0,6
1,2
0,4
0,8
1,6
1,2
0,4
0,8
1,6
...
0
1
0
1
0
0
1
1
0
0
1
Die Binärrepräsentation von 56,65 lautet also
111000,10 1001 1001 1001 1001 ...
Die normalisierte Darstellung ist dann
1,1100010 1001 1001 1001 1001 ... * 25
Bei 32 Bit stehen 1 Bit für das Vorzeichen, 23 Bit für die Mantisse und 8 Bit für den
gerichteten Exponenten zur Verfügung.
Der gerichetet Exponent ist 127 + 5 = 132 = 100001002
Somit lautet die Darstellung von 56,65 als normalisierte Gleitpunktzahl bei der Verwendung
von 32 Bit. Dabei ist zu berücksichtigen, dass das erste Bit der Mantisse nicht dargestellt
wird, da in der normalisierten Darstellung dies immer 1 ist.
0|10000100|11000101001100110011001
V ger.Exp. Mantisse
Aufgabe 9
Seien L1 und L2 zwei kontextfreie Sprachen. Zeigen Sie, dass dann auch die Verkettung
L1L2 = { uv | u ∈ L1 , v ∈ L2 } eine kontextfreie Sprache ist.
Beweis:
Seien Gi = (Ni , Ti , Pi , Si) mit i ∈ {1,2} die kontextfreien Grammatiken, die L1 bzw. L2
erzeugen. Durch Umbenennen erreichen wir, dass N1 ∩ N2 = ∅ gilt. Sei ferner S ein neues
Startsymbol, das nicht in N1 und N2 vorkommt.
Dann wird die Sprache L1L2 erzeugt durch
G = (N1 ∪ N2 ∪ {S}, T1 ∪ T2 , P1 ∪ P2 ∪ {S → S1S2}, S).
Aufgabe 10
a) Wie viele Möglichkeiten gibt es, einen Blumenstrauß mit 20 Rosen zugestalten, wenn
man weiße, rote und gelbe Rosen zur Verfügung hat?
b) Wie viele Rosensträuße obiger Art gibt es mit genau einer roten Rose?
Antwort:
Hierbei handelt es sich um eine ungeordnete Auswahl mit Wiederholung.
⎛ n + k − 1⎞
⎜⎜
⎟⎟
⎝ k ⎠
Die Anzahl der Möglichkeiten ist mit n = 3 und k = 20
⎛ n + k − 1⎞ ⎛ 3 + 20 − 1⎞ ⎛ 22 ⎞
22!
= 11 ⋅ 21 = 231
⎟⎟ = ⎜⎜ ⎟⎟ =
⎜⎜
⎟⎟ = ⎜⎜
⎝ k ⎠ ⎝ 20 ⎠ ⎝ 20 ⎠ 20! ⋅ 2!
Soll ein Strauß nur eine einzige rote Rose enthalten, so kann noch 19 mal unter den weißen
und gelben Rosen gewählt werden, also n = 2 und k = 19
⎛ n + k − 1⎞ ⎛ 2 + 19 − 1⎞ ⎛ 20 ⎞
20!
= 20
⎟⎟ = ⎜⎜ ⎟⎟ =
⎜⎜
⎟⎟ = ⎜⎜
⎝ k ⎠ ⎝ 19 ⎠ ⎝ 19 ⎠ 19! ⋅1!
Document
Kategorie
Gesundheitswesen
Seitenansichten
14
Dateigröße
32 KB
Tags
1/--Seiten
melden