zurück zur Liste

Lösungen

Vollständige Induktion

1. Induktionsanfang A(1): 1 = 12
Induktionsvoraussetzung A(n): 1 + 3 + 5 + ... + (2n - 1) = n2
Induktionsbehauptung A(n+1): 1 + 3 + 5 + ... + (2n - 1) + (2(n+1) - 1) = (n+1)2
Induktionsschritt n → n+1
1 + 3 + 5 + ... + (2n - 1) + (2(n+1) - 1) = (n+1)2
n2 + (2n + 1) = n2 + 2n + 1 mit IV
2. Induktionsanfang [] ++ [] = []
Induktionsvoraussetzung x ++ [] = x
Induktionsbehauptung a:x ++ [] = a:x
Induktionsschritt l → l+1, also x → a:x
a:x ++ [] = a:x
a:(x ++ []) = a:x mit (a)
a:x = a:x mit IV
3. Induktionsanfang rev ([] ++ b) = (rev b) ++ (rev [])
rev b = (rev b) ++ [] mit (2a), (2)
rev b = rev b mit (2a)
Induktionsvoraussetzung rev (a ++ b) = (rev b) ++ (rev a)
Induktionsbehauptung rev ((x:a) ++ b) = (rev b) ++ (rev x:a)
Induktionsschritt l → l+1, also a → x:a
rev ((x:a) ++ b) = (rev b) ++ (rev x:a)
rev (x:(a ++ b)) = (rev b) ++ (rev a) ++ [x] mit (2b), (b)
rev (a ++ b) ++ [x] = (rev b) ++ (rev a) ++ [x] mit (b)
rev (a ++ b) ++ [x] = rev (a ++ b) ++ [x] mit IV
4. Induktionsanfang rev (rev []) = []
rev [] = [] mit (a)
[] = [] mit (a)
Induktionsvoraussetzung rev (rev xs) = xs
Induktionsbehauptung rev (rev x:xs) = x:xs
Induktionsschritt l → l+1, also xs → x:xs
rev (rev x:xs) = x:xs
rev ((rev xs) ++ [x]) = x:xs mit (b)
(rev [x]) ++ (rev (rev xs)) = x:xs mit (3)
(rev [x]) ++ xs = x:xs mit IV
[x] ++ xs = x:xs mit (c)
x:[] ++ xs = x:xs mit (d)
x:([] ++ xs) = x:xs mit (2b)
x:xs = x:xs mit (2a)

Primitiv rekursive Funktionen

Aufstellen der Gleichungen → Einfache Lösungen → Gleichungen mit ψ und χ
pred (0)
pred (n+1) 		= 0
= n 		= clr ()
= p2 (pred (n), n)
eq0 (0)
eq0 (n+1) 		= 1
= 0 		= suc clr ()
= clr (eq0 (n), n)
sub (0, m)
sub (n+1, m) 		= m
= pred (n, m) 		= p1 (m)
= pred p1 (sub (n, m), n, m)
and (0, m)
and (n+1, m) 		= 0
= m 		= clr (m)
= p3 (and (n, m), n, m)
not (0)
not (n+1) 		= 1
= 0 		= suc clr ()
= clr (not (n), n)
ge (0, m)
ge (n+1, m) 		= eq0 (m)
= eq0 (sub (n+1, m)) 		= eq0 (m)
= eq0 (sub (suc p2, p3)) (ge (n, m), n, m)
if (0, m1, m2)
if (n+1, m1, m2) 		= m2
= m1 		= p2 (m1, m2)
= p3 (pred (n, m1, m2), n, m1, m2)

O-Notation

  1. log2 n < √n < n < n(log2 n)2 < n2 < n3 < 1,8n < 3n
  2. (a) Θ(n2)
    (b) Θ(n log2 n)
    (c) Θ(n · 4n)

Algorithmen

  1. Dijkstra: D(a)=0, D(b)=2, D(c)=6, D(d)=8, D(e)=9, D(f)=9, D(g)=8, D(h)=12, D(i)=9
  2. Folgende Kanten sind im kleinsten aufspannenden Baum enthalten: (a,b), (b,c), (c,d), (d,e), (d,i), (e,f), (e,h), (i,g)
  3. Ein Huffman-Code: A = 00, B = 110, C = 0100, D = 0101, I = 101, L = 0110, M = 0111, R = 111, S = 100
  4. Verschiebefunktion:
Wort
Stelle
Verschiebefunktion f 		abacabb
1234567
0112112

a b b a b a b c a b a b c a b b b c a
b
X		 a
 b
 c
 a
 b
 b
f(1) = 0
b
-		 a
X		 b
 c
 a
 b
 b
f(2) = 1
b
-		 a
-		 b
-		 c
X		 a
 b
 b
f(4) = 2
b a
-		 b
-		 c
-		 a
-		 b
-		 b
X
f(7) = 2
b a
-		 b
-		 c
-		 a
-		 b
-		 b
-
Wort gefunden

Graphen und Bäume

  1. AVL-Baum

  2. B-Baum
  3. Rot-Schwarz-Baum in eine (2,4)-Baum umgewandelt:
  4. Suffixbaum von ananas$
  5. Adjazenzliste
    u → v → x
    v → y
    w → y → z
    x → v
    y → x
    z → z
    Adjazenzmatrix
    nach u v w x y z
    u 0 1 0 1 0 0
    v 0 0 0 0 1 0
    von w 0 0 0 0 1 1
    x 0 1 0 0 0 0
    y 0 0 0 1 0 0
    z 0 0 0 0 0 1
    Eine Adjazenzliste ist hier sinnvoller, da bei der Adjazenzmatrix sehr viel Speicherplatz unnötig besetzt ist.
  6. Konvexe Hülle
    besteht aus den Punkten A, D, G und H.
  7. Pre- und Postorder
    (a)

    Preorder : - + 2 * 3 6 / 4 1
    Postorder: 2 3 6 * + 4 1 / -
    (b)

    Preorder : + - * 5 + 6 2 / 7 4 * 2 5
    Postorder: 5 6 2 + * 7 4 / - 2 5 * +
    (c)
    Preorder : * 2 + 7 / 5 5
    Inorder : 2 * (7 + 5 / 5)
    Postorder: 2 7 5 5 / + *