Rekursive Auswertungsprozesse in Haskell · • man kann nachweisen: ack nicht primitiv rekursiv • hat Anwendung in der Komplexit¨atstheorie Praktische Informatik 1, WS 2004/05,

Rekursive Auswertungsprozesse in Haskell

Auswertungsprozess, der durch eine rekursive Funktion bewirkt wird

Beispiel: Auswertung der rekursiven Fakultatsfunktion

0! := 1n! := n ∗ (n− 1)!

fakultaet x = if x <= 1 then 1

else x*(fakultaet (x-1))

Praktische Informatik 1, WS 2004/05, Folien Haskell−2, (12. November2004) Seite 1

Auswertungsprozess, linear rekursiv

bei verzogerter Auswertung

(Nicht jeder Zwischenzustand ist angegeben)

(fakultaet 6)

(6 * (fakultaet (6-1)))

(6 * (5 * (fakultaet (5-1))))

(6 * (5 * (4 * (fakultaet (4-1)))))

(6 * (5 * (4 * (3 * (fakultaet (3-1))))))

(6 * (5 * (4 * (3 * (2 * (fakultaet (2-1)))))))

(6 * (5 * (4 * (3 * (2 * 1)))))

(6 * (5 * (4 * (3 * 2))))

(6 * (5 * (4 * 6)))

(6 * (5 * 24))

(6 * 120)

720


Auswertungsprozess, linear rekursiv

(fakultaet 6) Auswertungsprozess ist linear rekursiv

Charakteristisch: nur eine rekursive Funktionsanwendungin jedem Ausdruck der Reduktionsfolge

Zwischenausdrucke sind unbeschrankt in der Große


Applikative Funktionen

Eine Funktion ist applikativ,wenn

zuerst die Argumente ausgewertet werden,dann der (eigentliche) Rumpf der Funktion

Eine Funktion nennt man strikt,wenn

die Argumente auf jeden Fall ausgewertet werden,der Zeitpunkt jedoch nicht festgelegt ist.

applikativ ⇒ strikt

Wenn f applikativ die applikative Variante von f,dann gilt i.a: f und f applikativ sind semantisch verschieden


Alternative Berechnungen der Fakultatsfunktion

Iteriere folgende Regel:Produkt ⇒ Produkt ∗ ZahlerZahler ⇒ Zahler + 1

Programm:

fakultaet_iter n = fakt_iter 1 1 n

fakt_iter produkt zaehler max =

if zaehler > max

then produkt

else fakt_iter (zaehler * produkt) (zaehler + 1) max

fakt_iter_strikt produkt zaehler max =

strikt_3 produkt zaehler max

(if zaehler > max

then produkt

else fakt_iter_strikt (zaehler * produkt) (zaehler + 1) max)

fakultaet_lin n = fakt_iter_strikt 1 1 n


Endrekursion

Eine Endrekursion ist eine lineare Rekursion.

Zusatzlich muss gelten:

alle rekursiven Aufrufe berechnen den Ruckgabewert

ohne Nachverarbeitung


Auswertungsprozess, endrekursiv

Auswertung von (fakultaet_iter 5) bei verzogerter Auswertung

(fakultaet_iter 5)

(fakt_iter 1 1 5)

(fakt_iter (1*1) (1+1) 5)

(fakt_iter (2*(1*1)) (2+1) 5)

(fakt_iter (3*(2*(1*1))) (3+1) 5)

(fakt_iter (4*(3*(2*(1*1)))) (4+1) 5)

(fakt_iter (5*(4*(3*(2*(1*1))))) (5+1) 5)

(5*(4*(3*(2*(1*1)))))

120

Das ist eine lineare Rekursion, es ist auch eine Endrekursion

Auswertungsprozess zu fakultaet 6 nicht endrekursiv,da fakultaet (...) eingebettet in weitere Berechnung.


Iterativer Auswertungsprozess: Fakultat (2)

Iterativer Auswertungsprozess:

(fakultaet_lin 6)

(fakt_iter_strikt 1 1 6)







720

Iterativer Prozess:

Charakteristisch: Ist eine EndrekursionArgumente sind Basiswerte(bzw. Große des Gesamtausdrucks bleibt beschrankt.)optimierte Ruckgabe des Wertes


Optimierung der Endrekursion

imperative Program-

miersprachen

Endrekursion i.a. nicht optimiert.

d.h. Wert wird durch alle Stufen der Rekur-

sion zuruckgegebenHaskell Endrekursion ist optimiert

am Ende wird Wert unmittelbar zuruckgege-

ben.

Deshalb:

Iterationskonstrukte in imperativen Programmiersprachen:

for ...do, while, oder repeat ...until.


Iteration in Haskell

In Haskell: Iterative Auswertungsprozessenur mittels guter Programmierung

Naive Implementierung, verzogerte Reihenfolge der Auswertung

tendieren zu:

linear rekursiven, nicht endrekursiven bzw. nicht iterativen Prozessen.

Vergleich: Iterativ gegen linear rekursiv:Anzahl Auswertungsschritte bleibt i.a. gleichGroße der Zwischenausdrucke ist kleiner


Baumrekursion

Beispiel Berechnung der Fibonacci-Zahlen

1, 1, 2, 3, 5, 8, 13, 21, . . .

Fib(n) :=

0 falls n = 01 falls n = 1Fib(n− 1) + Fib(n− 2) sonst

fib n = if n <= 0 then 0

else if n == 1 then 1

else fib (n-1) + fib(n-2)


Auswertungsprozess zu fib

fibs: applikative Variante von fib

Der Auswertungs-Prozess ergibt folgende Zwischen-Ausdrucke:

fibs 5

fibs 4 + fibs 3

(fibs 3 + fibs 2) + fibs 3

((fibs 2 + fibs 1) + fibs 2) + fibs 3

(((fibs 1 + fib 0) + fibs 1) + fibs 2) + fibs 3

(((1+0) + fibs 1) + fibs 2) + fibs 3

((1 + fibs 1) + fibs 2) + fibs 3

((1+1) + fibs 2) + fibs 3

(2 + fibs 2) + fibs 3

(2 + (fibs 1 + fibs 0)) + fibs 3

.......


Auswertungsprozess zu fibs: Baum der Aufrufe

5

43

2

1 0

1

3

2 1

1 0

2

1 0

Das ist Baumrekursion

Charakteristisch: Ausdrucke in der Reduktionsfolge• konnen unbegrenzt wachsen• enthalten mehrere rekursive Aufrufe• Aber: nicht geschachtelt

(d.h. die Argumente eines rekursiven Aufrufsenthalten keine rekursiven Aufrufe)


Geschachtelte Rekursion

Ist der allgemeine Fallwird normalerweise selten benotigt, da i.a. nicht effizient berechenbar.

Beispiel: Die Ackermannfunktion

----- Ackermanns Funktion ----

ack 0 y = 1

ack 1 0 = 2

ack x 0 | x >= 2 = x+2

ack x y | x > 0 && y > 0 = ack (ack (x-1) y) (y-1)

Vorstellung neuer syntaktischer Moglichkeiten in Haskell:Auswertung:von oben nach unten wird probiert, welche Definitionsgleichung passt:1) Argumente anpassen2) Bedingung rechts vom | prufen


Optimierte Ackermannfunktion

----- Ackermanns Funktion optimiert ----

ackopt 0 y = 1

ackopt 1 0 = 2

ackopt x 0 = x+2

ackopt x 1 = 2*x

ackopt x 2 = 2^x

ackopt x y | x > 0 && y > 0 = ackopt (ackopt (x-1) y) (y-1)

*Main> logI10 (ackopt 5 3)

19728.301029995662 --(Anzahl DezimalStellen)

-- ( == 2^65536)

• sehr schnell wachsende Funktion• man kann nachweisen: ack nicht primitiv rekursiv• hat Anwendung in der Komplexitatstheorie


Tabelle der Rekursionsprozesse:

linear rekursiv maximal ein rekursiver Unterausdruckendrekursiv linear rekursiv und Gesamtresultat ist Wert des

rekursiven Unterausdrucksiterativ endrekursiv und Argumente sind BasiswerteBaumrekursion mehrere rekursive Unterausdruck, Argument des

rekursiven Ausdrucks ohne weitere Rekursiongeschachtelte

Baumrekursion

mehrere rekursive Unterausdrucke auch in den

Argumenten


Optimierung: Iteration statt Rekursion

Beispiel

Berechnung von (fib 5)

fib 3 wird 2 mal berechnetfib 2 wird 3 mal berechnetfib 1 wird 5 mal berechnet

Genauer: Bei Berechnung von fib n fur n ≥ 2

wird fib(1) jeweils (fib n)-mal berechnet

fib n ≈ Φn√

5wobei Φ = 1+

√5

2 ≈ 1.6180

Fazit: fib(n) wachst exponentiell# Reduktionen fur fib(n) ist exponentielld.h. die Laufzeit von fib ist exponentiell


Iterative Version von Fib

Beobachtung: zur Berechnung von fib(n) benotigt man

nur die Werte fib(i) fur 1 ≤ i ≤ n.

Idee: Berechnung einer Wertetabelle fur fib.

Verbesserte Variante: aus fib (n− 1) und fib (n− 2) berechne fib(n)Ohne Doppelberechnung

Rechenvorschrift: (a, b) → (a + b, a)


Iterative Version von fib: Funktionen

fib_lin n = (fib_iter_strikt 1 0 n)

fib_iter a b zaehler = if zaehler <= 0

then b

else fib_iter (a + b) a (zaehler - 1)

fib_iter_strikt a b zaehler =

strikt_3 a b zaehler

(if zaehler <= 0

then b

else fib_iter_strikt (a + b) a (zaehler - 1))


Prozess fur (fib lin 5)

(fib_lin 5)

(fib_iter_strikt 1 0 5)





5


Analyse der fib-Optimierung

Fur (fib_lin n) gilt:• ist operational aquivalent zu fib

• benotigt linear viele Reduktionen abhangig von n• Große der Ausdrucke ist beschrankt• Platzbedarf ist konstant (d.h. unabhangig) von n.

(unter Vernachlassigung der Darstellungsgroße der Zahlen)

erzeugt Iterativen Auswertungsprozess


Terminierung: Halt ein Programm an?

((3n + 1)-Funktion)

drein x = if x == 1 then 1

else if geradeq x

then drein (x ‘div‘ 2)

else drein (3*x+1)

geradeq n = (rem n 2) == 0

Collatz Vermutung:

diese Funktion halt an fur jede positive naturliche Zahl

als Eingabe


Beispielausfuhrungen von drein

Zum Experimentieren verwende dreinlst.

fur 5: 5,16,8,4,2,1fur 27:27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,

364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,

526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,

251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,

719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,

1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,

1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,

80,40,20,10,5,16,8,4,2,1

Die Terminierung dieser Funktion drein wurde gepruft fur alle Zahlen

< 240


Terminierung

Die Theorie zeigt:

Programmiersprachen, die Programme ausschließen, die manchmal

nicht terminieren

sind nicht allgemein.

D.h. nicht aquivalent zur Turingmaschine


Terminierungsnachweise

Normalerweise mit vollstandiger Induktion

bzw. Mit Induktion zu einer fundierten Ordnung.

Beispiel:




Beh: fib(n) terminiert mit einer ganzen Zahl fur n ∈ IN0:

Induktionsbasis ist 0 und 1:

fib 0 und fib 1 terminieren und ergeben Resultat 0 bzw. 1.


Terminierungsnachweis (2)

Induktionsschritt: Fur n > 1 gilt:

fib n reduziert zu fib (n− 1) + fib (n− 2).

Induktionshypothese gilt fur n− 1 und n− 2, also terminiert fib n.

Insgesamt ist damit die Terminierung gezeigt. QED

Ungelost: Die einfachen Ansatze zum Terminierungsbeweis fur die

3n+1-Funktion scheitern, da die Argumente unregelmaßig großer und

kleiner werden.


Ressourcenbedarf von Programmen, Effizienz,

Wachstumsraten und Großenordnungen

wichtige Ressourcen:

• Zeit

• Platz


Weitere Ressourcen / Maße:

• Anzahl benotigter Prozessoren bei parallelen Algorithmen

• Große des Programms

• Kosten fur die Kommunikation

• Anzahl der Aufrufe bestimmter Unterprozeduren (Dienste):Datenbankzugriffe, usw.


Weitere Ressourcen / Maße (2)

Man kann auch noch betrachten:

• Aufwand zur Erstellung des Programms• organisatorischer Aufwand zur Nutzung• Aufwand zum Portieren eines Programms in andere

(Rechner-)umgebungen.• Aufwand fur Verifikation / Anderung eines Programms• Kosten innerhalb eines organisatorischen Rahmens


Optimierung

Optimierung := Reduktion des Ressourcenbedarf von Programmendurch Abanderungen des Programmsohne Funktionalitatsanderung.

Es gibt verschiedene Prioritaten bei Optimierung:

Wettervorhersage Simulationen: ZeitAnwendung mit Datenubertragung: KommunikationJava: Kommunikation,Portierbarkeit


Optimierung (2). Zu beachten ist:

• Wie oft wird dieses Programm benotigt? Lohnt sich der Optimier-

aufwand ?

• optimierte Programme sind oft unubersichtlicher.

• Optimierung wird durch Compiler erledigt

• Optimierung kann die Portierbarkeit verschlechtern

• experimentelle Feststellung des Ressourcenbedarfs ist

fehlerbehaftet und abhangig von (Version der) Programmierumge-

bung


Analyse von Programmen

Wir verwenden fur Haskell-Programme folgende Messungen.

Benutze verzogerte Auswertung

Zeit: Anzahl der Transformationsschritte

Platz: (Gesamt-Speicher): Maximale Große der Ausdrucke

Arbeitsspeicher: Maximale Große der Ausdrucke(ohne die Eingabe)

arithmetische und Boolesche Operationen = 1 Transformationsschritt.


Analyse von Programmen (2)

Angabe des Ressourcenbedarf eines Algorithmus

in Abhangigkeit von der Große der Eingabe.

Notation fur Algorithmus alg bei Eingabe der Große n:

redalg(n) maximale Anzahl der Reduktionen bei verzogerter Aus-

wertung fur alle Eingaben der Große n.

Platzalg(n) Platzbearf: maximale Große der Ausdrucke (des gerich-

teten Graphen) bei verzogerter Auswertung fur alle Ein-

gaben der Große n.

Die Eingaben nicht mitzahlen


Analyse von Programmen (3)

Bei genauerer Analyse einer Problemklasse:

Bezugsgroßen: Turingmaschineoder anderes abstraktes Maschinenmodell

!?: Abhangigkeit vom Maschinenmodell?Aufwand eines Einzelschrittes (abstr. Maschine)?Aufwand der eingebauten Funktionen?

(Multiplikation, Addition, Konversionen,usw.).benotigter Platz fur Zahlen? I.a. nicht konstant.


Beispiel: fib




Bezugsgroße: eingegebene Zahl n

Behauptung: # rekursive Aufrufe fur (fib n) ist ≤ fib(n + 1)Beweis: mit vollstandiger Induktion

redfib(n) ≤ c ∗ fib(n + 1) wobei c eine Konstante ist.fib(n) ≈ 1.6n ⇒ redfib(n) ≈ 1.6n (einfach exponentiell)

andere Bezugsgroße: Große der Darstellung der Zahl n:

n hat size(n) = dlog10(n)e Dezimalstellen.

Zeitbedarf: ≈ 1.6(10size(n)) (doppelt exponentiell).


Beispiel fakultaet

fakultaet x = if x <= 1 then 1

else x*(fakultaet (x-1))

Anzahl der Reduktionen:

fakultaet 1

if 1 <= 1 then ...

if True then ...

1

fakultaet 1 : 3 Reduktionschritte


Beispiel fakultaet 2

fakultaet 2

if 2 <= 1 then ...

if False then ...

2*(fakultaet (2-1))

2*(if (2-1) <= 1 then ... )

2*(if 1 <= 1 then ... )

2*(if True then ... )

2* 1

2



Beispiel fakultaet 3

fakultaet 3

if 3 <= 1 then ...

if False then ...

3*(fakultaet (3-1))

3*(if (3-1) <= 1 then ... )

3*(if 2 <= 1 then ... )

3*(if False then ... )

3*(2*fakultaet (2-1))

3*(2*(if 2-1 <= 1 then ...

3*(2*(if 1 <= 1 then ... ))

3*(2*(if True then ... ))

3*(2* 1)

3*2

6



Beispiel fakultaet n

Es sind: 5 ∗ (n− 1) + 3 Reduktionsschritte.

Vermutung: redfakultaet(n) = 5 ∗ (n− 1) + 3

Nachweis mit vollstandiger Induktion:Beh: fakultaet (n-1) (als Ausdruck)

benotigt 5 ∗ (n− 2) + 4 Reduktionsschritte:fur n ≥ 2

Basis: fakultaet (2-1) benotigt 4 Reduktionsschritte


Beispiel fakultaet n: Nachweis

Ind. Schritt:

Nachzuweisen ist: fakultaet (n-1) benotigt 5 ∗ (n− 2) + 4 fur n > 2.

fakultaet (n-1)

if (n-1) <= 1 then ...

if n1 <= 1 then ... -- n1 ist Basiswert > 1

if False then ...

n1*fakultaet (n1-1)

Das sind 4 + 5 ∗ (n1− 2) + 4 + 1 = 5 ∗ (n− 2) + 4 Reduktionsschritte


Beispiel fakultaet n : Nachweis

Anfangs-Reduktions-Schritt

fakultaet n

if n <= 1 then ...

if False then ...

n*fakultaet (n-1)

Das sind 3 + (5 ∗ (n− 2) + 4) + 1 = 5 ∗ (n− 1) + 3


Komplexitaten von Algorithmen

Beachte: breite Streuung des Ressourcenbedarfs ist moglich furdie Menge aller Eingaben einer bestimmten Große.

Z.B. (3n+1)-Funktion mit Bezugsgroße: Anzahl der Stellen

Komplexitaten von Platz und Zeit:

Ressourcenbedarf

im schlimmsten Fall (worst-case)im besten Fall (best-case)

Minimum von # Reduktionenbzw. Minimum der Große der Ausdrucke.

im Mittel (average case)Welche Verteilung?


Komplexitaten von Algorithmen

Ein Algorithmus ist effizient, wenn er wenig Ressourcen benotigt

Ein Algorithmus ist optimal, wenn er”nicht schlechter“ ist als andere

Algorithmen zur gleichen Problemklasse

(Zeit/Platz)-Komplexitat einer Problemklasse:

≡ Ressourcenverbrauch des optimalen Algorithmus.


O-Schreibweise

Verwendung: asymptotische Großenordnung von

numerischen Funktionen

hier fur: redalg(n) und Platzalg(n)

Definition

Seien R, f : IN+ → IR+ zwei Funktionen: Wir schreiben:

R(n) = O(f(n)), wenn es eine Konstante K gibt, so daßR(n) ≤ K ∗ f(n) fur alle genugend großen n.


O-Schreibweise: Bemerkungen

Beachte R(n) = O(f(n)) keine Gleichung

Beachte R(n) = O(f(n)) ist eine Abschatzung nach oben

Die Angabe R(n) = O(f(n)) sollte moglichst optimales f verwenden

Sprechweisen:

R(n) ist von der Großenordnung f(n)

R(n) hat hochstens Großenordnung f(n)


Beispiele und Eigenschaften zu O()

•√

n = O(n)

• p(n) = O(2n) fur alle Polynome p.

• Wenn f(n) = O(c ∗ g(n)), dann auch f(n) = O(g(n)).

• Wenn c > 1 und e > 0 eine Konstante, dann gilt: f(n) = O(cn+e)gdw. f(n) = O(cn)

• Wenn c, d > 1, dann gilt: f(n) = O(logc(n)) gdw. f(n) = O(logd(n))

• Wenn c, d > 1, und c < d, dann gilt: cn = O(dn) , aber nichtdn = O(cn).


Beispiele und Eigenschaften zu O()

• Wenn f(n) = O(g(n)) und g(n) = O(h(n), dann gilt auch

f(n) = O(h(n)).

• Wenn eine Funktion f durch eine Konstante nach oben beschrankt

ist, dann gilt f(n) = O(1).


Beispiel fib

fib Bezugsgroße: n: Eingabed: Große der Darstellung der Zahl n

redfib(n) = O(1.62n)platzfib(n) = O(n)

redfib lin(n) = O(n)platzfib lin(n) = O(n)

redfib lin(d) = O(10d)platzfib lin(d) = O(10d)


Einige Komplexitaten

O(1) konstantO(log(n)) logarithmischO(n) linearO(n ∗ log(n)) fastlinear (oder auch n-log-n)O(n2) quadratischO(n3) kubischO(nk) polynomiellO(2n) exponentiell


Komplexitaten: Veranschaulichung

beispielhafte Tabelle zur intuitiven Veranschaulichung:

Eingabedaten 10 100 1000Algorithmuslog2(n) 0.000003 sec 0.000007 sec 0.00001n 0.00001 sec 0.0001 sec 0.001 secn2 0.0001 sec 0.01 sec 1 secn3 0.001 sec 1 sec 15 min2n 0.001 sec 4 ∗ 1016 Jahre nahezu ∞


Kommentare zu O()

• Viele relevante Optimierungen andern Großenordnung O()

nicht• Verwendung eines schnelleren Rechners:

nur konstante Verbesserung der Zeit, d.h. O() andert sich

nicht.• Die Bestimmung der genauen Komplexitat des Ressourcenbe-

darfs einer Problemklasse ist jeweils ein sehr schweres theore-

tisches Problem.• Oft sind nur gute obere Abschatzungen bekannt• Bekannte untere Schranken sind oft trivial oder zu schwach


Ω-Schreibweise

Ziel:

Großenordnung von numerischen Funktionen nach unten abschatzen.

Seien R, f : IN+ → IR+ zwei Funktionen:

R(n) = Ω(f(n)), wenn es eine Konstante Kgibt, so daßR(n) ≥ K ∗ f(n) fur alle genugend großen n.


Ω-Eigenschaften

Analog zu O(·).

• n = Ω(√

n)•

√n = Ω(1).

• 2n = Ω(p(n)) fur alle Polynome p.• Wenn f(n) = Ω(c ∗ g(n)), dann auch f(n) = Ω(g(n)).• m Wenn c > 1 und e > 0 eine Konstante, dann gilt:

f(n) = Ω(cn+e) gdw. f(n) = Ω(cn)• Wenn c, d > 1, dann gilt: f(n) = Ω(logc(n)) gdw. f(n) =

Ω(logd(n))• Wenn c, d > 1, und c < d, dann gilt: dn = Ω(cn) , aber

nicht cn = Ω(dn).• Wenn f(n) = Ω(g(n)) und g(n) = Ω(h(n), dann gilt auch

f(n) = Ω(h(n)).• Wenn eine Funktion f durch eine Konstante nach unten

beschrankt ist, dann gilt f(n) = Ω(1).


Schnelle Berechnung von Potenzen

bn fur positive ganze Zahlen n.

Die Potenzen sind rekursiv definiert durch:

bn :=

1 falls n = 0b ∗ bn−1 sonst

Direkte Kodierung des Algorithmus ergibt ein rekursives Programm:

potenz b n = if n == 0

then 1

else b * (potenz b (n - 1))

Platz- und Zeitbedarf sind von der Großenordnung O(n)


Optimierung der Potenzberechnung

Idee: Statt b8 = b ∗ b ∗ b ∗ b ∗ b ∗ b ∗ b ∗ b berechne

• b2 := b ∗ b

• b4 = b2 ∗ b2

• b8 = b4 ∗ b4

allgemeine Rechenvorschrift:

bn :=

1 falls n = 0(bn/2)2 falls n gerade und ≥ 2b ∗ bn−1 falls n ungerade


Haskell-Programm zur Potenz

potenz_log b n = if n == 0 then 1

else if geradeq n

then quadrat (potenz_log b (n ‘div‘ 2))

else b * (potenz_log b (n - 1))

geradeq n = (rem n 2) == 0

Platz- und Zeitbedarf abhangig von n ist O(log(n))

z.B. fur n = 1000: 14 Multiplikationen.

tatsachlicher Platz- und Zeitbedarf: O((log(n)3),

wegen Multiplikation von großen Zahlen


Analyse des Algorithmus zum großten

gemeinsamen Teiler

ggT(a, b) (Euklids Algorithmus)

Teile a durch b gibt Rest r,

wenn r = 0, dann ggT(a, b) := b

wenn r 6= 0, dann berechne ggT(b, r).

Beispiel ggT(30,12) = ggT(12,6) = 6

ggt a b = if b == 0

then a

else ggt b (rem a b)


Satz von Lame

SATZ (Lame): Wenn der Euklidische ggt-Algorithmus k Schritte

benotigt,

dann ist die kleinere Zahl der Eingabe ≥ fib(k).

Platz- und Zeitbedarf von ggt: O(log(n))

Begrundung:

Wenn n die kleinere Zahl ist und der Algorithmus k Schritte benotigt,

dann ist n ≥ fib(k) ≈ 1.6180k

Also ist k = O(log(n))


Test auf Primzahl-Eigenschaft

Problem: Gegeben n.

Frage: ist n eine Primzahl?

Methode 1: finde den kleinsten Teiler > 1:

primzahlq n = n == (kleinster_teiler n)

kleinster_teiler n = finde_teiler n 2

finde_teiler n pruef_teiler =

if n < (quadrat pruef_teiler) then n

else if teiltq pruef_teiler n

then pruef_teiler

else finde_teiler n (pruef_teiler + 1)

teiltq a b = 0 == (rem b a)

(worst-case) Zeitbedarf: O(√

n)


Primzahltest: Methode 2

Benutze kleinen Fermatschen Satz.

Satz (Fermat): Wenn p eine Primzahl ist und 1 < a < p,

dann ist ap ≡ a(mod p)

Idee fur Algorithmus:

Teste fur viele verschiedene a: Wenn fur ein a: an 6≡ a(mod n), dann ist

n keine Primzahl.

Bei ausreichend vielen Zahlen a mit an ≡ a(mod n):

mit hoher Wahrscheinlichkeit ist n Primzahl

Aber: Ausnahmen sind moglich


Primzahltest: Programm zu Methode 2

potenzmod b e m =

if e == 0 then 1

else if geradeq e

then rem (quadrat (potenzmod b (e ‘div‘ 2) m))

m

else rem (b * (potenzmod b (e - 1) m))

m

fermat_test_it n rnd =

let a = (rnd ‘mod‘ n)

in (potenzmod a n n) == a

fermat_test n = and (map (fermat_test_it n)

(take 100 (randomInts 2 n))))


Primzahltest: Bemerkungen

Dies ist ein probabilistischer Algorithmus

Eigenschaften

Zeitverbrauch pro Test: O(log n).

Die Antwort:”ist keine Primzahl“ ist immer korrekt,

wahrend”ist eine Primzahl“ nur mit hoher Wahrscheinlichkeit korrekt

Die Ausnahmen nennt man Carmichael-Zahlen.

561,1105,1729,2465,2821,6601,8911,10585,15841,29341, . . . .

Teilbarkeitstest durch die Primzahlen bis 43

schliesst alle Carmichaelzahlen ≤ 106 aus.


Primzahltest: Neuere Ergebnisse

Prufung einer Zahl auf Primzahleigenschaft ist in polynomieller Zeit

moglich

(d.h. in O(log(n)) ).

(siehe: M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P )


Beispiel: Fermatsche Primzahlen

Vermutung von Pierre de Fermat: 22n+ 1 ist immer eine Primzahl

geometrische Konstruierbarkeit mittels Zirkel und Lineal

von gleichseitigen Vielecken ist moglich,

wenn die Anzahl der Seiten die Form

2m ∗ p hat und p eine Fermatsche Primzahl ist

Widerlegung der Vermutung: 22n+ 1 ist keine Primzahl fur n =

5,6,7,8,9


Beispiel: Fermatsche Primzahlen

Main> fermat_prim_test 4

(65537,True) -- ist Primzahl


(4294967297,False)


(18446744073709551617,False)


(340282366920938463463374607431768211457,False)

Aber: einen Teiler zu berechnen dauert sehr (zu) lange.

Mit iterativer Version von potenzmod:

auch n = 10,11,12,13,14 widerlegbar.

Offen: (n = 33,34,35,40,41,44,45,46,47,50, . . .)


Beispiel: Mersennesche Primzahlen

sind von der Form 2p − 1, wobei p selbst eine Primzahl ist.

Mersennesche Primzahlen sindRekordhalter als großte Primzahlen

Es sind Primzahlen fur folgende Werte von p:2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,

3217,4253,4423,9689,9941,11213,19937, . . .

Der aktuelle Rekord ist p = 24036583, d.h. die Mersennesche Primzahl224036583 − 1,

Siehe http://www.mersenne.org/history.htm#found

p = 2281 ist machbar mit Haskell Interpreter (einige Minuten)

mersenne_prim_test 2281


Documents

Rekursive Auswertungsprozesse in Haskell · • man kann nachweisen: ack nicht primitiv rekursiv • hat Anwendung in der Komplexit¨atstheorie Praktische Informatik 1, WS 2004/05,