Blatt0 - TU Ilmenau

TU Ilmenau, Fakultät IA
Institut TI, FG Komplexitätstheorie und Effiziente Algorithmen
Prof. Dr. (USA) M. Dietzfelbinger, Dr. M. Brinkmeier, Dr. E. Hübel,
http://www.tu-ilmenau.de/fakia/afs ws07.html
K
Algorithmen und Datenstrukturen, SS08
Übungsblatt Stunde 0
für die 15. Woche 2008
Aufgabe 1 (Euklidscher Algorithmus)
Gegeben sind zwei ganze Zahlen a und b, die höchsten n Bits besitzen.
Gesucht ist der größte gemeinsame Teiler ggT (a, b).
a
für b = 0
ggT (a, b) :=
ggT (b, a mod b) für b > 0
1. Wie groß ist die Anzahl der rekursiven Aufrufe?
2. Wie groß ist die Operationskomplexität (in O -Notation), d.h. wie viele arithmetische
(modulo) Operationen werden ausgeführt?
3. Wie groß ist die Bit-Komplexität (in O -Notation), d.h. wie viele Bitoperationen werden
ausgeführt?
Aufgabe 2 (Schnelle modulare Exponentiation)
Gegeben sind drei ganze Zahlen a, b und m mit höchsten n Bits. Gesucht ist ab mod m.
Der folgende Algorithmus löst diese Aufgabe, ist aber nicht praktikabel. Warum?
Algorithmus SM E(a, b, m)
p := 1;
for i := 1 to b do
p := p · a mod m;
return p.
//Es werden b Multiplikationen ausgeführt.
Besser: Rekursion.
Algorithmus f astexp(a, b, m):
if b = 0 then return 1;
if b = 1 then return a mod m;
(*b ≥ 2*) p1 := f astexp(a, b 2b c, m);
if b ungerade then return (((p1 · p1 ) mod m) · a) mod m;
if b gerade then return (p1 · p1 ) mod m.
1. Erklären Sie, weshalb der Algorithmus das korrekte Resultat liefert.
2. Wie groß ist die Anzahl der rekursiven Aufrufe?
3. Wie groß ist die Operationskomplexität (in O -Notation), d.h. wie viele arithmetische
(modulo) Operationen werden ausgeführt?
4. Wie groß ist die Bit-Komplexität (in O -Notation), d.h. wie viele Bitoperationen werden
ausgeführt?
2
Algorithmen und Datenstrukturen, SS08
Übungsblatt Stunde 0
Aufgabe 3 (Maximale Teilsumme)
Gegeben a1 , . . . , an ∈ Z.
P
Finde 1 ≤ i, j ≤ n mit ai + . . . + aj maximal. (Der Fall i > j mit
al = 0 ist erlaubt.)
i≤l≤j
1. Der dumme Algorithmus. Man berechnet si,j für jedes Paar (i, j) einzeln und löst das
Maximumproblem.
Algorithmus DOOF (a1 , . . . , an )
M := 0; ii := 1; jj := 0;
for i := 1 to n do
for j := i to n do
S := ai + . . . + aj ;
if S > M then ii := i; jj := j; M := S;
return ii, jj.
Schätzen Sie den Rechnungsaufwand nach oben und nach unten ab (in Θ -Notation).
2. Der naive Algorithmus. Man greift bei der Summenbildung si,j für j = i, i + 1, . . . , n auf
das vorherige Ergebnis zurück: si,i = ai und si,j+1 = si,j + aj+1 für j = i, . . . , n − 1. Man führt
dies für i = 1, 2, . . . , n durch:
Algorithmus N ORM AL(a1 , . . . , an )
M := 0; ii := 1; jj := 0;
for i := 1 to n do
S := 0;
for j := i to n do
S := S + aj ;
if S > M then ii := i; jj := j; M := S;
return ii, jj.
Schätzen Sie den Rechnungsaufwand nach oben und nach unten ab (in Θ -Notation).
3. Der Divide-And-Conquer-Algorithmus.
Es werden nicht alle Summen si,j ausgerechnet.
Hier nehmen wir (zur Vereinfachung) an, dass die Anzahl n der Zahlen eine Zweierpotenz ist:
n = 2k .
Idee: Für den Abschnitt i..j, der die Summe maximiert, gibt es drei Möglichkeiten:
1. Fall: ( links der Mitte“) i ≤ j ≤ 12 n.
”
2. Fall: ( rechts der Mitte“) 21 n + 1 ≤ i ≤ j ≤ n.
”
3. Fall: ( die Mitte überspannend“) i ≤ 12 n und 21 n + 1 ≤ j.
”
Entwickeln Sie einen entsprechenden Algorithmus und analysieren Sie ihn.
4.∗ Der Linearzeit-Algorithmus.
Entwickeln Sie einen Linearzeit-Algorithmus !
∗ Etwas
anspruchsvoller.

Download Report