Zentor
16-04-2002, 19:49
Also ich wollt etwas üben und hab mir von der Algodat HP die Prüfungsangaben für die Jahresprüfung angeschaut und einige der relevanten Bsp versucht zu lösen. Ohje ganz schön schwer... Naja is wahrscheinlich alles falsch aber würd gern wissen was ihr so herausbekommt:
2000 06 30
1.a)
Sigma(g(n)) Theta(g(n)) O(g(n))
------------|----------|--------|
x
------------|----------|--------|
x
------------|----------|--------|
x x x
------------|----------|--------|
x
------------|----------|--------|
1.b)
Nein, da für n kleiner als 100 Sigma(n) gilt
2.a)
Der Heap ist nur ein gedachter Suchbeim welcher ganz normal als Feld gespeichert ist. Ein
Suchbaum ist eine eigene Datenstrucktur.
2.b) ähnlich wie 2.) vom 2002 01 28
4.)
----------------------------------------------------------------------------------------------------
2000 10 09
1.a)
1.b) für alle n ab beliebigen n0, n0 > 0 ,c>0
0 <= c*n <= 1/10 n log n
c <= 1/10 log n
lim n-> Inf log n = Inf daraus folgt kein konstantes c kann gefunden werden
Aussage falsch
4.)
----------------------------------------------------------------------------------------------------
2000 12 18
1.a)
wahr falsch
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
? ?
-------|--------|
1.b)
Nein weil unter 1000 die Funktion O(n^2) hat und das ist nicht O (n log n) (z.B. bei -1)
2.a)
Merge-Sort(A,p,q)
falls p < q dann {
m = floor((p+q)/2);
Merge-Sort(A,p,m);
Merge-Sort(A,m+1,q);
Merge(A,p,m,q);
}
2.b)
21, 14, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,1,2)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,2,3)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,4,4,5)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,3,5)
8, 14, 17, 21, 28, 36, 15, 18, 5, 2
Merge(A,6,6,7)
8, 14, 17, 21, 28, 15, 36, 18, 5, 2
Merge(A,6,7,8)
8, 14, 17, 21, 28, 15, 18, 36, 5, 2
Merge(A,9,9,10)
8, 14, 17, 21, 28, 15, 18, 36, 2, 5
Merge(A,6,8,10)
8, 14, 17, 21, 28, 2, 5, 15, 18, 36
Merge(A,1,5,10)
2, 5, 8, 14, 15, 17, 18, 21, 28, 36
4.)
----------------------------------------------------------------------------------------------------
2001 01 29
1.a)
A:T(n) = c1*(n+1)+(c2+c3)*n = Theta(n)
B:T(n) = c1*(n+1)+c2*n+c3*n*(n+1)+c4*n*n = Theta(n^2)
C:T(n) = c1+c2*(n+1)+c3*n+c4*n+c5*(n-1) = Theta(n)
D:T(n) = c1+ c2*(k+1)+c3*k = Theta(1) <---- weil hier nach Theta Notation für n gefragt wird nicht k
E:T(n) = ???
2.a)
stabil nicht stabil
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
? ?
-------|--------|
2.b)
314,263,329,298,193,223,253,110
110,263,329,298,193,223,253,314
110,193,329,298,263,223,253,314
110,193,223,298,263,329,253,314
110,193,223,253,263,329,298,314
110,193,223,253,263,329,298,314
110,193,223,253,263,298,329,314
110,193,223,253,263,298,314,329
Listen da hier nur die Zeiger umgeschrieben werden müssen und nicht der ganze Datensatz
4.)
----------------------------------------------------------------------------------------------------
2001 03 09
1.a)
wahr falsch
-------|--------|
x
-------|--------|
?(x) ? was heißt enthält in dem Fall ?
-------|--------|
?(x) ?
-------|--------|
? ?
-------|--------|
x
-------|--------|
? ?
-------|--------|
1.b)
Ja weil die Obergrenze ab einem beliebigen Wert n0>0 gelten muss
Also wenn man n0= 126 nimmt so hat die Funktion log n / 125 +5 sicher O(log n)
2.a)
2.b)
Eine völlig Sortierte Folge
2.c)
kommt auf die Implementierung von Quicksort an
3.)
----------------------------------------------------------------------------------------------------
2001 05 18
1.)
28 n^6 - 12 n^2 + 14 n - 13 log n + 10 = Theta(n^6)
für alle n ab beliebigen n0, n0 > 0 c1,c2>0
0<= c1* n^6 <= 28 n^6 - 12 n^2 + 14n - 13 log n + 10 <= c2* n^6
c1 <= 28 - 12 n^-4 + 14n^-5 - 13 log n * n^-6 + 10* n^-6 <= c2
geht gegen 28 0 0 ? 0
NR : log n * n^-6 L'Hospital: x^-1 * -6 * x^-5 -> 0 (für log zur Basis n)
Also geht der ganze Ausdruck gegen 28 -> z.B. c1 = 1 c2 = 100 ,n entsprechend groß wählen
2.)
(1) falsch weil bei log n unter 10^8 hat die Funktion Sigma(n)
(2) richtig weil O(n^2) für die Funktion sowohl unter log n = 10^8 als auch darüber gilt
(3) falsch weil bei log n über 10^8 hat die Funktion O(n^2)
(4) richtig weil Sigma(n) für die Funktion sowohl unter log n = 10^8 als auch darüber gilt
3.)
6.)
NeuSort(A,i,j):
falls i < j dann {
minpos = i;
maxpos = j;
für a = i...j {
falls A[a].key < A[minpos].key dann {
minpos = a;
}
falls A[a].key > A[maxpos].key dann {
maxpos = a;
}
}
vertausche A[i] mit A[minpos];
vertausche A[j] mit A[maxpos];
i++;
j--;
Neusort(A,i,j)
}
----------------------------------------------------------------------------------------------------
2001 06 22 v1
1.)
O() Sigma() Theta()
-------|--------|--------|
x x x
-------|--------|--------|
x x x
-------|--------|--------|
x
-------|--------|--------|
x
-------|--------|--------|
x
-------|--------|--------|
2.a)
Sort1:Selection Sort
Sort2:Insertion Sort
2.b)
Selection Sort ist nicht stabil weil Elemente von ganz hinten nach vorge getauchst werden können und
dann die Reihenfolge von 2 gleichen Elementen nicht mehr gegeben ist
Insertion Sort ist stabil weil beim Verschieben der Elemente die Anderen nur verschoben und
nicht vertauscht werden, so dass die Reihenfolge von 2 gleichen Elementen erhalten bleibt
2.c)
----------------------------------------------------------------------------------------------------
2001 06 22 v2
1.)
A) T(n) = c1+(11+n)*c2+(10+n)*(c4 + c5) = Theta(n)
B) T(n) = c1*(1+floor(n/1234)) +(1+floor(n/1234))+(c2+c3)=Theta(n)
C) T(n) = c1+(1+floor(ld(k)))*c2+(floor(ld(k)))*(c3+c4) = Theta(1)
D)
----------------------------------------------------------------------------------------------------
2001 10 12
1.a)
Sigma(g(n)) Theta(g(n)) O(g(n))
------------|----------|--------|
x
------------|----------|--------|
x x x
------------|----------|--------|
x
------------|----------|--------|
? ? ?
------------|----------|--------|
1.b)
Darf man negative Zahlen in Primfaktoren zerlegen??? -1 is doch keine Primzahl ???
Hm wenn ja dann stimmt die Aussage nicht weil ja auch die Nicht-primzahlen
unbegrenzt vorhanden sind wenn man sich -unendlich nähert und daher mindestens Sigma(n^2) gelten muss
3.)
----------------------------------------------------------------------------------------------------
2001 12 14
1.a)
1.b)
Ja weil O(n^3) für beide Fälle gilt
3.) ähnlich wie 2.) vom 2000 12 18
4.)
----------------------------------------------------------------------------------------------------
2002 01 28
1.a)
In der O Notation kann man Konstante Faktoren vernachlässigen, da ja später
sowieso alles mit einem konstanten c multipliziert wird also ist beides auf
f(n) = O(1) zu vereinfachen. Somit sind sie ident und die Aussage wahr.
1.b)
2.).... das dauert ja ewig ....
2000 06 30
1.a)
Sigma(g(n)) Theta(g(n)) O(g(n))
------------|----------|--------|
x
------------|----------|--------|
x
------------|----------|--------|
x x x
------------|----------|--------|
x
------------|----------|--------|
1.b)
Nein, da für n kleiner als 100 Sigma(n) gilt
2.a)
Der Heap ist nur ein gedachter Suchbeim welcher ganz normal als Feld gespeichert ist. Ein
Suchbaum ist eine eigene Datenstrucktur.
2.b) ähnlich wie 2.) vom 2002 01 28
4.)
----------------------------------------------------------------------------------------------------
2000 10 09
1.a)
1.b) für alle n ab beliebigen n0, n0 > 0 ,c>0
0 <= c*n <= 1/10 n log n
c <= 1/10 log n
lim n-> Inf log n = Inf daraus folgt kein konstantes c kann gefunden werden
Aussage falsch
4.)
----------------------------------------------------------------------------------------------------
2000 12 18
1.a)
wahr falsch
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
? ?
-------|--------|
1.b)
Nein weil unter 1000 die Funktion O(n^2) hat und das ist nicht O (n log n) (z.B. bei -1)
2.a)
Merge-Sort(A,p,q)
falls p < q dann {
m = floor((p+q)/2);
Merge-Sort(A,p,m);
Merge-Sort(A,m+1,q);
Merge(A,p,m,q);
}
2.b)
21, 14, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,1,2)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,2,3)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,4,4,5)
14, 21, 28, 8, 17, 36, 15, 18, 5, 2
Merge(A,1,3,5)
8, 14, 17, 21, 28, 36, 15, 18, 5, 2
Merge(A,6,6,7)
8, 14, 17, 21, 28, 15, 36, 18, 5, 2
Merge(A,6,7,8)
8, 14, 17, 21, 28, 15, 18, 36, 5, 2
Merge(A,9,9,10)
8, 14, 17, 21, 28, 15, 18, 36, 2, 5
Merge(A,6,8,10)
8, 14, 17, 21, 28, 2, 5, 15, 18, 36
Merge(A,1,5,10)
2, 5, 8, 14, 15, 17, 18, 21, 28, 36
4.)
----------------------------------------------------------------------------------------------------
2001 01 29
1.a)
A:T(n) = c1*(n+1)+(c2+c3)*n = Theta(n)
B:T(n) = c1*(n+1)+c2*n+c3*n*(n+1)+c4*n*n = Theta(n^2)
C:T(n) = c1+c2*(n+1)+c3*n+c4*n+c5*(n-1) = Theta(n)
D:T(n) = c1+ c2*(k+1)+c3*k = Theta(1) <---- weil hier nach Theta Notation für n gefragt wird nicht k
E:T(n) = ???
2.a)
stabil nicht stabil
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
x
-------|--------|
? ?
-------|--------|
2.b)
314,263,329,298,193,223,253,110
110,263,329,298,193,223,253,314
110,193,329,298,263,223,253,314
110,193,223,298,263,329,253,314
110,193,223,253,263,329,298,314
110,193,223,253,263,329,298,314
110,193,223,253,263,298,329,314
110,193,223,253,263,298,314,329
Listen da hier nur die Zeiger umgeschrieben werden müssen und nicht der ganze Datensatz
4.)
----------------------------------------------------------------------------------------------------
2001 03 09
1.a)
wahr falsch
-------|--------|
x
-------|--------|
?(x) ? was heißt enthält in dem Fall ?
-------|--------|
?(x) ?
-------|--------|
? ?
-------|--------|
x
-------|--------|
? ?
-------|--------|
1.b)
Ja weil die Obergrenze ab einem beliebigen Wert n0>0 gelten muss
Also wenn man n0= 126 nimmt so hat die Funktion log n / 125 +5 sicher O(log n)
2.a)
2.b)
Eine völlig Sortierte Folge
2.c)
kommt auf die Implementierung von Quicksort an
3.)
----------------------------------------------------------------------------------------------------
2001 05 18
1.)
28 n^6 - 12 n^2 + 14 n - 13 log n + 10 = Theta(n^6)
für alle n ab beliebigen n0, n0 > 0 c1,c2>0
0<= c1* n^6 <= 28 n^6 - 12 n^2 + 14n - 13 log n + 10 <= c2* n^6
c1 <= 28 - 12 n^-4 + 14n^-5 - 13 log n * n^-6 + 10* n^-6 <= c2
geht gegen 28 0 0 ? 0
NR : log n * n^-6 L'Hospital: x^-1 * -6 * x^-5 -> 0 (für log zur Basis n)
Also geht der ganze Ausdruck gegen 28 -> z.B. c1 = 1 c2 = 100 ,n entsprechend groß wählen
2.)
(1) falsch weil bei log n unter 10^8 hat die Funktion Sigma(n)
(2) richtig weil O(n^2) für die Funktion sowohl unter log n = 10^8 als auch darüber gilt
(3) falsch weil bei log n über 10^8 hat die Funktion O(n^2)
(4) richtig weil Sigma(n) für die Funktion sowohl unter log n = 10^8 als auch darüber gilt
3.)
6.)
NeuSort(A,i,j):
falls i < j dann {
minpos = i;
maxpos = j;
für a = i...j {
falls A[a].key < A[minpos].key dann {
minpos = a;
}
falls A[a].key > A[maxpos].key dann {
maxpos = a;
}
}
vertausche A[i] mit A[minpos];
vertausche A[j] mit A[maxpos];
i++;
j--;
Neusort(A,i,j)
}
----------------------------------------------------------------------------------------------------
2001 06 22 v1
1.)
O() Sigma() Theta()
-------|--------|--------|
x x x
-------|--------|--------|
x x x
-------|--------|--------|
x
-------|--------|--------|
x
-------|--------|--------|
x
-------|--------|--------|
2.a)
Sort1:Selection Sort
Sort2:Insertion Sort
2.b)
Selection Sort ist nicht stabil weil Elemente von ganz hinten nach vorge getauchst werden können und
dann die Reihenfolge von 2 gleichen Elementen nicht mehr gegeben ist
Insertion Sort ist stabil weil beim Verschieben der Elemente die Anderen nur verschoben und
nicht vertauscht werden, so dass die Reihenfolge von 2 gleichen Elementen erhalten bleibt
2.c)
----------------------------------------------------------------------------------------------------
2001 06 22 v2
1.)
A) T(n) = c1+(11+n)*c2+(10+n)*(c4 + c5) = Theta(n)
B) T(n) = c1*(1+floor(n/1234)) +(1+floor(n/1234))+(c2+c3)=Theta(n)
C) T(n) = c1+(1+floor(ld(k)))*c2+(floor(ld(k)))*(c3+c4) = Theta(1)
D)
----------------------------------------------------------------------------------------------------
2001 10 12
1.a)
Sigma(g(n)) Theta(g(n)) O(g(n))
------------|----------|--------|
x
------------|----------|--------|
x x x
------------|----------|--------|
x
------------|----------|--------|
? ? ?
------------|----------|--------|
1.b)
Darf man negative Zahlen in Primfaktoren zerlegen??? -1 is doch keine Primzahl ???
Hm wenn ja dann stimmt die Aussage nicht weil ja auch die Nicht-primzahlen
unbegrenzt vorhanden sind wenn man sich -unendlich nähert und daher mindestens Sigma(n^2) gelten muss
3.)
----------------------------------------------------------------------------------------------------
2001 12 14
1.a)
1.b)
Ja weil O(n^3) für beide Fälle gilt
3.) ähnlich wie 2.) vom 2000 12 18
4.)
----------------------------------------------------------------------------------------------------
2002 01 28
1.a)
In der O Notation kann man Konstante Faktoren vernachlässigen, da ja später
sowieso alles mit einem konstanten c multipliziert wird also ist beides auf
f(n) = O(1) zu vereinfachen. Somit sind sie ident und die Aussage wahr.
1.b)
2.).... das dauert ja ewig ....