close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Grümpelturnier Gersbach Wann: 13/14 Juni 2015 Wo

EinbettenHerunterladen
Universität Leipzig
Institut für Informatik
Abt. Automatische Sprachverarbeitung
Algorithmen und Datenstrukturen I
WS 2014/2015 – Serie 1
Ausgabe am
14.10.2014
Prof. G. Heyer, F. Holz
Abgabe bis
28.10.2014
Seite
1/2
Algorithmen und Datenstrukturen I
WS 2014/2015 – Serie 1
1. (10 Punkte) Komplexitätsklassen
Gegeben sind die folgenden 8 Funktionen, bezeichnet als Ta , Tb , . . . , Th :
a) n →
3n
,
n+33
b) n → n cos 2πn + 32n2 ,
√
d) n → 6 n3 ,
e) n →
g) n → (n + 16)(16 − 1),
h) n → log 2n4n − 16n,
10n3
.
log n2 +1
n
c) n → 2 3 ,
√
3
f) n → 3log n + n 2n4 ,
Berechnen Sie für jede Funktion Tx (x = a, . . . , h) die jeweils kleinstmögliche Komplexitätsklasse O(f ), sodass Tx ∈ O(f ), für eine Funktion f von n. Geben sie die Komplexitätsklasse an, z.B. als O(1), O(n2 ), O(n3/2 ) O(n4 log n), O(n2 / log n) oder O(3n ) an, wobei
sie gegebenenfalls andere Konstanten verwenden müssen. Drücken sie die Klassen jeweils
möglichst einfach aus.
Ordnen sie die Funktionen Tx nach aufsteigender Komplexität, d.h. es stehe Tx vor Ty , genau
dann wenn Tx ∈ O(Ty ).
2. (4 Punkte) Laufzeit- und Speicherkomplexität
Gegeben sind folgende Funktionen:
a)
int g(int[] N, int[] M){
for(int i=1; i<=N.length; i++){
A= int[];
B= int[];
for(int j=1; j<=M.length; j++){
if (N[i] == M[j]) { a = A[i-1]+s }
else
{ a = A[i-1]+r }
b = B[i-1]+g;
c = A[i]+g;
B[i]=max(a,max(b,c));
}
A=B;
B={};
}
return A[N.length];
}
Universität Leipzig
Institut für Informatik
Abt. Automatische Sprachverarbeitung
Algorithmen und Datenstrukturen I
WS 2014/2015 – Serie 1
Ausgabe am
14.10.2014
Prof. G. Heyer, F. Holz
Seite
2/2
Abgabe bis
28.10.2014
b) int b(int n, int x) {
int erg = x;
if (n>1) {
for (int i = 1; i <= n; i++) {
erg = erg+i;
}
for (int k=0; k<3; k++) {
erg = erg + b(n/3,erg/9);
}
}
return erg;
}
Geben Sie für die Funktionsaufrufe a(N, M ) und b(n, 0) jeweils die exakte Schranke der
Zeitkomplexität und Speicherplatzkomplexität in Abhängigkeit von n mittels Θ-Notation an.
Begründen sie Ihre Antwort!
Für a) nehmen sie dabei an das beide Listen N und M die gleiche Länge n haben. Beachten
sie, dass hier s, r und g Konstanten sind. Bei b) beginnen sie damit, eine Rekursionsgleichung
für den Zeitbedarf aufzustellen.
3. (6 Punkte) Rekursion, Master-Theorem
Gegeben seien die folgenden Rekursionsgleichungen jeweils für eine Funktion T :
a) T (n) = 27T (n/3) + n3 (n + 1),
b) T (n) = 32T (n/2) + 16n4 (n log 8),
c) T (n) = T (n − 1) · n.
Bestimmen Sie jeweils eine exakte Schranke für das Verhalten von T . Finden Sie also eine
Funktion f , sodaß T ∈ Θ(f ). In den Fällen, wo die polynomiale Version des Master-Theorems
anwendbar ist, benutzen Sie dieses zum Finden von f und geben a, b und k an.
4. (8 Punkte) Suchverfahren
Gegeben sei folgende in einem Feld abgespeicherte, aufsteigend sortierte Zahlenfolge:
Feldindex
Feldinhalt
0
10
1
11
2
12
3
13
4
14
5
15
6
16
7
17
8
18
9
19
10
30
11
31
12
32
13
33
14
34
15
35
Feldindex
Feldinhalt
16
36
17
37
18
38
19
39
20
60
21
61
22
62
23
63
24
64
25
65
26
66
27
67
28
68
29
69
30
70
31
71
Geben Sie für die Suchverfahren
• Sequentielle Suche
• Binäre Suche
• Einfache Sprungsuche (mit optimaler Sprungweite; Kosten eines Sprunges und eines
sequentiellen Vergleichs seien gleich)
• Interpolationssuche
jeweils den Suchweg bis zum Auffinden des Elements 66 an. Falls bei der Berechnung einer
Feldadresse ein nichtganzahliger Wert entstehen sollte, wird als Feldadresse das größte Ganze
des Wertes genommen, also der Teil nach dem Komma abgeschnitten.
Document
Kategorie
Gesundheitswesen
Seitenansichten
7
Dateigröße
198 KB
Tags
1/--Seiten
melden