Komplexität von Algorithmen und Problemen Klaus Becker 2014

Komplexität von Algorithmen und Problemen

Klaus Becker

2014

2 Fallstudie - Primzahlalgorithmen34608828249085121524296039576741331672262866890023854779048928344500622080983411446436437554415370753366448674763505018641470709332373970608376690404229265789647993709760358469552319045484910050304149809818540283507159683562232941968059762281334544739720849260904855192770626054911793590389060795981163838721432994278763633095377438194844866471124967685798888172212033000821469684464956146997194126921284336206463313859537577200462442029064681326087558257488470489384243989270236884978643063093004422939603370010546595386302009073043944482202559097406700597330570799507832963130938739885080198416258635194522913042562936679859587495721031173747796418895060701941717506001937152430032363631934265798516236047451209089864707430780362298307038193445486493756647991804258775574973833903315735082891029392359352758617185019942554834671861074548772439880729606244911940066680112823824095816458261761861746604034802056466823143718255492784779380991749580255263323326536457743894150848953969902818530057870876229329803338285735419228259022169602665532210834789602051686546011466737981306056247480055071718250333737502267307344178512950738594330684340802698228963986562732597175372087295649072830289749771358330867951508710859216743218522918811670637448496498549094430541277444079407989539857469452772132166580885754360477408842913327292948696897496141614919739845432835894324473601387609643750514699215032683744527071718684091832170948369396280061184593746143589068811190253101873595319156107319196071150598488070027088705842749605203063194191166922106176157609367241948160625989032127984748081075324382632093913796444665700601391278360323002267434295194325607280661260119378719405151497555187549252134264394645963853964913309697776533329401822158003182889278072368602128982710306618115118964131893657845400296860012420391376964670183983594954112484565597312460737798777092071706710824503707457220155015899591766244957768006802482976673920392995410164224776445671222149803657927708412925555542817045572430846389988129960519227313987291200902060882060733762075892299473666405897427035811786879875694315078654420055603469625309399653955932310466430039146465805452965014040019423897552675534768248624631951431493188170905972588780111850281190559073677771187432814088678674286302108275149258477101296451833651979717375170900505673645964696355331369819296000267389583289299126738345726980325998955997501176664201042888546085699446442834195232948787488410595750197438786353119204210855804692460582533832967771946911459901921324984968810021189968284941331573164056304725480868921823442538199590383852412786840833479611419970101792978355653650755329138298654246225346827207503606740745956958127383748717825918527473164970582095181312905519242710280573023145554793628499010509296055849712377978984921839997037415897674154830708629145484724536724572622450131479992681684310464449439022250504859250834761894788889552527898400988196200014868575640233136509145628127191354858275083907891469979019426224883789463551

3 Teil 1

Fallstudie - PrimzahlalgorithmenPraktische Anwendbarkeit von Algorithmen

4 Primzahlen

Primzahlen sind natürliche Zahlen, die nur durch 1 und sich selbst ohne Rest teilbar sind.

Beispiele: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Satz: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.

Beispiel: 260 = 2*2*5*13

Man nennt die Primzahlen, die in einer Produktdarstellung einer gegebenen Zahl vorkommen, auch Primfaktoren der Zahl.

5 Primzahltest

falls n eine Primzahl ist

True

False

istPrimzahl

nnatürliche Zahl

falls n keine Primzahl ist

Das Primzahltestproblem (kurz PRIMES) besteht darin, bei einer vorgegebenen natürlichen Zahl zu überprüfen, ob sie eine Primzahl ist.

6 Primzahlerzeugung

Primzahl p mit p >= n p

erzeugtePrimzahl

nnatürliche Zahl

Das Primzahlerzeugungsproblem besteht darin, eine Primzahl (einer bestimmten Größenordnung) zu erzeugen.

Primzahl aus dem Bereich m..n

p

erzeugtePrimzahl

mnatürliche Zahl

nnatürliche Zahl

7

Primfaktorzerlegung / Faktorisierung

Das Faktorisierungsproblem (kurz FACTORIZE) besteht darin, eine vorgegebene natürliche Zahl in ein Produkt aus Primfaktoren zu zerlegen.

Liste der Primfaktoren von n L

primfaktoren

nnatürliche Zahl

[2, 2, 5, 13]

primfaktoren

260

8 Primzahlalgorithmen

Aufgabe:

Aus der Primzahleigenschaft ergibt sich direkt ein einfacher Algorithmus, mit dem man bei einer natürlichen Zahl n überprüfen kann, ob es sich um eine Primzahl handelt.

Formuliere den Algorithmus in Struktogrammform. Implementiere und teste den Algorithmus. Überlege dir Möglichkeiten zur Verbesserungen des einfachen Algorithmus.

Aufgabe:

(a) Bei kleineren Zahlen kann man eine Primfaktorzerlegung oft direkt angeben. Bestimme eine Primfaktorzerlegung von n = 48 und n = 100.

(b) Bei größeren Zahlen sollte man systematisch vorgehen, um die Primfaktoren zu bestimmen. Bestimme eine Primfaktorzerlegung von n = 221 und n = 585.

(c) Entwickle zunächst einen Algorithmus zur Primfaktorzerlegung. Beschreibe in einem ersten Schritt in Worten das Verfahren, das du zur Primfaktorzerlegung von Zahlen benutzt. Beschreibe das Verfahren anschließend mit einem Struktogramm. Entwickle dann ein Programm zur Primfaktordarstellung.

Aufgabe:

Entwickle einen Algorithmus zur Erzeugung von Primzahlen. Implementiere und teste den Algorithmus.

9 Teil 2

Ein einfacher Primzahltest

10 Primzahltest mit Probedivisionen

Übergabe: n = 51

# Probedivisionen

n % 2 -> 1

n % 3 -> 0

Rückgabe: False

ALGORITHMUS istPrimzahl(n):

prim = True

k = 2

SOLANGE k*k <= n und prim:

WENN n % k == 0:

prim = False

k = k+1

Rückgabe: prim

Übergabe: n = 53

# Probedivisionen

n % 2 -> 1

n % 3 -> 2

n % 4 -> 1

n % 5 -> 3

n % 6 -> 5

n % 7 -> 4

Rückgabe: True

11 Ein einfaches Testverfahren

primzahlen = [11,101,1009,10007,100003,1000003,10000019,100000007,1000000007,10000000019,100000000003,1000000000039,10000000000037,100000000000031,1000000000000037,10000000000000061,100000000000000003,1000000000000000003,10000000000000000051,100000000000000000039,1000000000000000000117,...]

def istPrimzahl(n): ...

from time import *

for p in primzahlen: t1 = clock() ergebnis = primzahl(p) t2 = clock() t = t2 - t1 print("Primzahl: ", p, "Rechenzeit: ", t)

Erhöhe systematisch die „Größe“ der Primzahl

Mit Probedivisionen

12 Laufzeitverhalten

>>> Primzahl: 11 Rechenzeit: 5.86666741164e-06Primzahl: 101 Rechenzeit: 8.3809534452e-06Primzahl: 1009 Rechenzeit: 1.50857162014e-05Primzahl: 10007 Rechenzeit: 3.54793695847e-05Primzahl: 100003 Rechenzeit: 0.000101968266917Primzahl: 1000003 Rechenzeit: 0.000324342898329Primzahl: 10000019 Rechenzeit: 0.00104817791088Primzahl: 100000007 Rechenzeit: 0.00332500359683Primzahl: 1000000007 Rechenzeit: 0.0105655886432Primzahl: 10000000019 Rechenzeit: 0.0407208178693Primzahl: 100000000003 Rechenzeit: 0.140259725747Primzahl: 1000000000039 Rechenzeit: 0.447675891768Primzahl: 10000000000037 Rechenzeit: 1.41919042783Primzahl: 100000000000031 Rechenzeit: 4.55093566361Primzahl: 1000000000000037 Rechenzeit: 14.3208156344Primzahl: 10000000000000061 Rechenzeit: 45.2250185429Primzahl: 100000000000000003 Rechenzeit: 144.197546336...

Aufgabe: Schätze ab, wie lange eine Überprüfung einer 100- bzw. 600-stelligen Primzahl mit Hilfe von Probedivisionen in etwa dauert.

13 Zusammenhänge

>>> ...Primzahl: 100000000003 Rechenzeit: 0.140259725747Primzahl: 1000000000039 Rechenzeit: 0.447675891768Primzahl: 10000000000037 Rechenzeit: 1.41919042783Primzahl: 100000000000031 Rechenzeit: 4.55093566361Primzahl: 1000000000000037 Rechenzeit: 14.3208156344Primzahl: 10000000000000061 Rechenzeit: 45.2250185429Primzahl: 100000000000000003 Rechenzeit: 144.197546336...

Gesetzmäßigkeit:Wenn man die Anzahl der Stellen der Ausgangszahl um 2 erhöht, dann erhöht sich die Laufzeit etwa um den Faktor 10. Jede zusätzliche Stelle bei der Ausgangszahl führt also dazu, dass die Laufzeit mit dem Faktor √10 multipliziert wird.

Es handelt sich hier um ein exponentielles Wachstumsverhalten, das man mathematisch mit einer Exponentialfunktion beschreiben kann: Wenn i die Anzahl der Stellen der Ausgangszahl angibt, dann lässt sich die Laufzeit mit einer Funktion wie folgt beschreiben:

L(i) = c*(√10)i ; mit einer Konstanten c

14 Prognosen

>>> ...Primzahl: 100000000003 Rechenzeit: 0.140259725747Primzahl: 1000000000039 Rechenzeit: 0.447675891768Primzahl: 10000000000037 Rechenzeit: 1.41919042783Primzahl: 100000000000031 Rechenzeit: 4.55093566361Primzahl: 1000000000000037 Rechenzeit: 14.3208156344Primzahl: 10000000000000061 Rechenzeit: 45.2250185429Primzahl: 100000000000000003 Rechenzeit: 144.197546336...

Prognose:Wenn die Zahl 100 Stellen haben soll, also 88 Stellen mehr als eine 12-stellige Zahl, so benötigt man nach der gefundenen Gesetzmäßigkeit 1044-mal so lange wie bei der 12-stelligen Zahl - also etwa 1044 Sekunden.

15 Teil 3

Eine Komplexitätanalyse

16

Problematik von Laufzeitmessungen

Laufzeitmessungen werden in der Praxis durchgeführt, um das Laufzeitverhalten eines Programms unter Realbedingungen zu ermitteln.

Aus systematisch durchgeführten Laufzeitmessungen kann man oft Gesetzmäßigkeiten erschließen, wie die Laufzeit von den zu verarbeitenden Daten abhängt.

Bei Laufzeitmessungen muss man aber sehr genau darauf achten, dass sie unter gleichen Bedingungen erfolgen. Ein Wechsel des Rechners führt in der Regel zu anderen Ergebnissen. Auch Änderungen in der Implementierung wirken sich in der Regel auf die Messergebnisse aus. Selbst bei ein und demselben Rechner und derselben Implementierung können sich die Bedingungen ändern, da oft mehrere Prozesse gleichzeitig ablaufen.

Ergebnisse von Laufzeitmessungen sind also kaum auf andere Systeme (andere Rechner, andere Programmiersprachen) übertragbar. Um diese Schwierigkeit zu überwinden, soll im Folgenden ein anderer Weg zur Beschreibung der Berechnungskomplexität beschritten werden.

17 Kostenabschätzung

Bei der Ausführung des Algorithmus (bei einer vorgegebenen natürlichen Zahl) spielt es eine Rolle, wie viele Operationen ausgeführt werden müssen.

Im dargestellten Algorithmus werden u.a. folgende Operationen ausgeführt:

n % k (Probedivision)

k*k (Produkt)

… <= n (Vergleich)

… und … (logische Operation)

k+1 (Inkrementieren)

Bei der Festlegung eines Kostenmaßes müssen Annahmen über den Aufwand der verschiedenen auszuführenden Operationen gemacht werden. Zwei ganz unterschiedliche Wege kann man dabei bestreiten. Ein Weg besteht darin, unterschiedliche Aufwände von Operationen möglichst genau zu erfassen und im Kostenmaß zu berücksichtigen. Ein anderer Weg beschränkt sich darauf, dominante Operationen auszuwählen und die Kosten nur grob zuzuschätzen. Wir werden hier nur den zweiten Weg beschreiten.


prim = True

k = 2


WENN n % k == 0:

prim = False

k = k+1

Rückgabe: prim

18 Fachkonzept Kostenfunktion

Die Problemgröße ist eine präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem das Zeit- bzw. Speicherverhalten von Lösungalgorithmen maßgeblich beeinflusst wird.

Bei der Beschreibung der Zeitkomplexität mit Hilfe einer Kostenfunktion werden in der Regel eine Reihe von Vereinfachungen vorgenommen sowie Annahmen gemacht. Die Festlegung einer Kostenfunktion kann somit als eine Form der Modellierung angesehen werden, weil hier ein Berechnungsmodell entwickelt werden muss, das den Berechnungsaufwand vereinfachend beschreibt.

Wie bei jeder Modellierung kann das entwickelte Modell mehr oder auch weniger geeignet sein, um die zu beschreibende Wirklichkeit darzustellen. Bei der Modellierung der Zeitkomplexität kommt es darauf an, sinnvolle Annahmen über den Aufwand bestimmter, im Algorithmus vorkommender Operationen zu machen.

Ein Kostenmaß legt fest, in welchem Maße welche Operationen bei der Aufwandsbestimmung berücksichtigt werden. Eine Kostenfunktion ordnet der Problemgröße i die vom Algorithmus benötigten Gesamtkosten K(i) bzgl. des vorgegebenen Kostenmaßes zu.

19 Problemgröße / Kosten

Problemgröße i: Anzahl der Stellen der Ausgangszahl n (als Maß für die Länge von n)

Kosten K:Anzahl der durchzuführenden Probedivisionen


prim = True

k = 2


WENN n % k == 0:

prim = False

k = k+1

Rückgabe: prim

Übergabe: n = 541

Anzahl der Stellen: 3

Probedivisionen

n % 2 > 0

n % 3 > 0

…

n % 23 > 0

Rückgabe: True

Anzahl der Probedivisionen: 22

20 Kostenabschätzung

Aufgabe:

Für welche Zahlen benötigt man die wenigsten Probedivisionen, für welche die meisten?

Aufgabe:

Betrachte den Fall, dass n eine Primzahl mit i = 3, 4, … Stellen ist. Wie viele Probedivisionen benötigt man mindestens / höchstens, um das mit dem gegebenen Algorithmus festzustellen?

21 Kostenanalyse

best case (bester Fall):

der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen

best case: n ist eine gerade Zahl (mit i Stellen)

Beispiel: n = 998; i = 3

Probedivisionen

n % 2 = 0

Rückgabe: False


Es gilt:

K(i) = 1„gar kein“

Wachstum

22 Kostenanalyse

Worst case: n ist die größte Primzahl mit i Stellen


Probedivisionen:

n % 2 > 0

n % 3 > 0

n % 4 > 0

…

z % 31 > 0 (Beachte: √997 = 31....)

Rückgabe: True


Beachte: 10i-1 < n < 10i

Es gilt: √(10i-1)-1 < K(i) < √(10i)-1

Also: (√10)i-1 -1 < K(i) < (√10)i – 1exponentielles Wachstum

worst case (schlechtester Fall):

der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen

23 Klassifikation von Kostenfunktionen

Eine (Kosten-) Funktion f wächst schneller als eine (Kosten-) Funktion g, wenn der Quotient f(i)/g(i) mit wachsendem i gegen unendlich strebt.

Eine (Kosten-) Funktion f wächst langsamer als eine (Kosten-) Funktion g, wenn der Quotient f(i)/g(i) mit wachsendem i gegen 0 strebt.

Eine (Kosten-) Funktion f wächst genauso schnell wie eine (Kosten-) Funktion g, wenn der Quotient f(i)/g(i) mit wachsendem n gegen eine Konstante c strebt.

Eine (Kosten-) Funktion f wächst höchstens so schnell wie eine (Kosten-) Funktion g, wenn f genauso schnell oder langsamer als g wächst.

Eine (Kosten-) Funktion f wächst mindestens so schnell wie eine (Kosten-) Funktion g, wenn f genauso schnell oder schneller als g wächst.

Die Klasse aller Funktionen, die nicht höchstens so schnell wachsen wie eine vorgegebene (Kosten-) Funktion f, wird mit O(f) bezeichnet. Man liest das so: "Groß O von f".

Die Klasse aller Funktionen, die nicht mindestens so schnell wachsen wie eine vorgegebene (Kosten-) Funktion f, wird mit Ω(f) bezeichnet. Man liest das so: "Groß Omega von f".

24 Wachstumsverhalten

Im worst case (d.h. n ist eine Primzahl) wächst die Kostenfunktion, die die maximale Anzahl von Probedivisionen einer i-stelligen Zahl beschreibt, genauso schnell wie die Exponentialfunktion g(i) = (√10)i.

Es gilt: (√10)i-1 -1 < K(i) < (√10)i – 1

Also: ((√10)i-1 -1) / (√10)i < K(i) / (√10)i < ((√10)i – 1) / (√10)i

Also: (1/√10) - 1/(√10)i < K(i) / (√10)i < 1 - 1/(√10)i

Für i gegen unendlich konvergiert K(i) / (√10)i gegen eine Zahl :

1/√10 < lim (K(i) / (√10)i) < 1

25 Wachstumsprototypen

Prototyp Grundeigenschaft

logarithmisches Wachstum:f(n) = log(n) Wenn n sich verdoppelt, dann wächst f(n) um einen konstanten Betrag.

lineares Wachstum:f(n) = n Wenn n sich verdoppelt, dann verdoppelt sich f(n) ebenfalls.

logarithmisch-lineares Wachstumf(n) = n*log(n)

quadratisches Wachstum:f(n) = n2 Wenn n sich verdoppelt, dann vervierfacht sich f(n).

kubisches Wachstum:f(n) = n3 Wenn n sich verdoppelt, dann verachtfacht sich f(n).

polynomiales Wachstumf(n) = nk Wenn n sich verdoppelt, dann vervielfacht sich f(n) mit 2k.

exponentielles Wachstum:f(n) = bn Wenn n sich um 1 erhöht, dann vervielfacht sich f(n) mit b.

26 Praktische Anwendbarkeit

aus: P. Breuer: Praktische Grenzen der Berechenbarkeit.

Wir nehmen hier an, dass zur Verarbeitung einer Kosteneinheit eine Millisekunde benötigt wird.

Algorithmen, deren Zeitkomplexität durch eine Kostenfunktion beschrieben wird, die exponentiell oder noch schneller wächst, gelten als praktisch nicht anwendbar.

27 Teil 4

Die Komplexität des Primzahltestproblems

28 Komplexität von Problemen

Zur Beschreibung der Komplexität eines Problems muss man folglich Aussagen über alle möglichen Algorithmen zur Lösung des Problems machen. Man zeigt, dass ein bestimmter Ressourcenverbrauch bei all diesen Algorithmen erforderlich ist und von keinem Algorithmus unterschritten werden kann. Die Schwierigkeit beim Nachweis solcher Aussagen besteht darin, dass man den Nachweis über alle denkbaren - d.h. bis jetzt gefundenen und auch noch nicht bekannten - Algorithmen führen muss.

Die (Zeit-)Komplexität eines Problems beschreibt man durch eine Komplexitätsklasse, die eine untere Schranken für die Komplexität aller Algorithmen, die das Problem lösen, bilden.

29

Komplexität des Primzahltestproblems

Der Primzahltest mit Probedivisionen ist ein Algorithmus mit exponentieller Zeitkomplexität. Dieser Algorithmus ist für große Ausgangszahlen praktisch nicht anwendbar.

Entsprechendes gilt für andere naheliegende Algorithmen, z.B. für das Verfahren mit dem Sieb des Eratosthenes (mit einer passend gewählten Kostenmodellierung).

Es stellt sich die Frage, ob alle Primzahltest-Algorithmen eine exponentielle Zeitkomplexität haben bzw., ob es Primzahltest-Algorithmen mit einer nicht-exponentiellen Zeitkomplexität gibt.

Lange Zeit gab es hierauf keine positive oder negative Antwort.

30 AKS-Primzahltest

Der AKS-Primzahltest wurde im Jahr 2002 von den drei indischen Wissenschaftlern Manindra Agrawal, Neeraj Kayal und Nitin Saxena ein Primzahltest entwickelt.


1. if n ist eine reine Potenz:

2. return ZUSAMMENGESETZT

3. finde das kleinste r mit o_r(n) > log(n)2

4. if 1 < ggT(a,n) < n für ein a ≤ r:


6. if n ≤ r:

7. return PRIM

8. for a=1 to sqrt(phi(r))*log(n) do

9. if (x+a)n ≠ xn+a (mod (xr-1,n)):


11. return PRIM

Quelle: http://de.wikipedia.org/wiki/AKS-Primzahltest

31 AKS-Primzahltest

Info:

Der AKS-Primzahltest hat eine Zeitkomplexität, die nicht schneller als die Potenzfunktion g(i) = i12 wächst.

Folgerung: PRIMES gehört zur Klasse P.

P bezeichnet die Klasse der Probleme, die mit einem Algorithmus mit polynomialer Zeitkomplexität gelöst werden können.

32 Probabilistische Testverfahren

Für praktische Zwecke ist der AKS-Primzahltest wenig geeignet. Das Laufzeitverhalten des AKS-Primzahltest ist für große Primzahlen immer noch sehr schlecht.

In der Praxis benutzt man heute oft probabilistische Testverfahren, da sie sehr effizient arbeiten. Probabilistischen Testverfahren funktionieren nach dem folgenden Prinzip: Bei Übergabe einer natürlichen Zahl n erhält man als Rückgabe entweder "n ist keine Primzahl" oder "n ist wahrscheinlich eine Primzahl". Diese Testverfahren liefern also keine absolute Gewissheit, wenn sie das Ergebnis "n ist wahrscheinlich eine Primzahl" produzieren. Die übergebene Zahl n kann mit einer bestimmten Wahrscheinlichkeit auch keine Primzahl sein. Allerdings ist diese Wahrscheinlichkeit sehr gering, so dass man die Unsicherheit oft in Kauf nimmt.

falls n wahrscheinlich eine Primzahl ist

True

False

istWahrscheinlichPrimzahl

nnatürliche Zahl

falls n keine Primzahl ist

33 Miller-Rabin-Test

import randomdef miller_rabin_pass(a, n): d = n - 1 s = 0 while d % 2 == 0: d = d >> 1 s = s + 1 a_to_power = pow(a, d, n) if a_to_power == 1: return True for i in range(s-1): if a_to_power == n - 1: return True a_to_power = (a_to_power * a_to_power) % n return a_to_power == n - 1def miller_rabin_test(n): for repeat in range(20): a = 0 while a == 0: a = random.randrange(n) if not miller_rabin_pass(a, n): return False return True

34 Miller-Rabin-Test

Eines der probabilistischer Testverfahren ist das Miller-Rabin-Verfahren. Beachte, dass die Wiederholungszahl 20 (s.uo) die Fehlerwahrscheinlichkeit beeinflusst. Setzt man diese Wiederholungszahl auf einen größeren Wert, so nimmt die Fehlerwahrscheinlichkeit ab.

Info:

Der Miller-Rabin-Test hat eine Zeitkomplexität, die nicht schneller als die Potenzfunktion g(i) = k*i3 wächst. Die Konstante k beschreibt hier die Anzahl der durchgeführten Wiederholungen.

35 Teil 5

Primzahlerzeugung

36 Ein einfaches Verfahren

ALGORITHMUS primzahl(m, n):

gefunden = False

SOLANGE nicht gefunden:

erzeuge eine Zufallszahl k aus dem Bereich m..n

WENN istPrimzahl(k):

gefunden = True

Rückgabe: k

Primzahl aus dem Bereich m..n

p

erzeugtePrimzahl

mnatürliche Zahl

nnatürliche Zahl

37 Test des Verfahrens

Aufgabe:

Implementiere und teste das Verfahren. Benutze einen schnellen Primzahltest (z.B. den Miller-Rabin-Test).

38 Beurteilung des Verfahrens

Aufgabe:

Wie lange dauert es durchschnittlich, bis man eine Primzahl im vorgegebenen Bereich gefunden hat?

39 Verteilung der Primzahlen

Die Funktion π(x) beschreibe die Anzahl der Primzahlen, die kleiner oder gleich x sind. Primzahlsatz:

Die Funktionen π(x) und g(x) = x/ln(x) sind asymptotisch äquivalent. Für große x gilt: π(x) ist ungefähr gleich x/ln(x).

Genauer: Für x >= 11 gilt: x/ln(x) <= π(x) <= x/ln(x)*(1+3/(2ln(x)))

Blau: π(x)

Grün: x(ln(x)

40 Verteilung der Primzahlen

Aufgabe:

Schätze ab, wie viele Primzahlen es im Bereich 100000..999999 gibt.

Wie viele Zahlen muss man im Durchschnitt testen, um eine Primzahl im angegebenen Bereich zu erhalten?

>>> from math import log>>> ...

Aufgabe:

Beim RSA-Verfahren (1024-Bit-Schlüssel) benutzt man Primzahlen aus dem Bereich 21023 .. 21024 (das sind Zahlen mit etwa 308 bzw. 309 Stellen). Wie viele Primzahlen gibt es in diesem Bereich?

Wie viele Zahlen muss man im Durchschnitt testen, um eine Primzahl im angegebenen Bereich zu erhalten?

41 Teil 6

Primfaktorzerlegung

42 Ein einfaches Verfahren

ALGORITHMUS primfaktoren(n):

faktoren = []

z = n

SOLANGE z > 1:

bestimme den kleinsten Primfaktor p von z mit Probedivisionen

füge p in die Liste faktoren ein

z = z // p

Rückgabe: faktoren

Liste der Primfaktoren von n L

primfaktoren

nnatürliche Zahl

43

Ein einfaches Faktorisierungsverfahren

# Übergabe: n = 51

# Initialisierung

faktoren = [] {faktoren -> []}

z = n {z -> 51}

# Probedivisionen

z % 2 -> 1

z % 3 -> 0

# Aktualisierung

p = z {p -> 3}

faktoren = faktoren + [p] {faktoren -> [3]}

z = z // p {z -> 17}

# Probedivisionen

z % 2 -> 1

z % 3 -> 2

z % 4 -> 1

z % 5 -> 2

# Aktualisierung

p = z {p -> 17}

faktoren = faktoren + [p] {faktoren -> [3, 17]}

z = z // p {z -> 1}

# Rückgabe: [3, 17]


initialisiere die Liste faktoren: faktoren = []

initialisiere die Hilfsvariable z: z = n

SOLANGE z > 1:



z = z // p

Rückgabe: faktoren

def primfaktoren(n): """ >>> primfaktoren(24) [2, 2, 2, 3] """ faktoren = [] z = n while z > 1: # bestimme die kleinsten Primfaktor p von z i = 2 gefunden = False while i*i <= n and not gefunden: if z % i == 0: gefunden = True p = i else: i = i + 1 if not gefunden: p = z # füge p in die Liste der Faktoren ein faktoren = faktoren + [p] z = z // p return faktoren

44 Eine Implementierung

45 Systematische Laufzeitmessungen

Aufgabe:Führe die Messungen durch. Kannst du anhand der Zahlen erste Zusammenhänge erkennen? Kannst du Prognosen erstellen, wie lange man wohl bis zum nächsten Ergebnis warten muss?

testzahlen = [

11,

101,

1009,

10007,

100003,

1000003,

10000019,

100000007,

1000000007,

10000000019,

100000000003,

1000000000039,

10000000000037,

100000000000031,

1000000000000037,

10000000000000061,

100000000000000003,

1000000000000000003,

10000000000000000051,

100000000000000000039,

...]

from faktorisierung import primfaktoren

from time import *

testzahlen = [...]

for z in testzahlen:

t1 = clock()

ergebnis = primfaktoren(z)

t2 = clock()

t = t2 - t1

print("Zahl: ", z)

print("Primfaktoren:", ergebnis)

print("Rechenzeit: ", t)

print()

46 Zusammenhänge und Prognosen

Gesetzmäßigkeit:Wenn man die Anzahl der Stellen der Ausgangszahl um 2 erhöht, dann erhöht sich die Laufzeit um den Faktor 10. Jede zusätzliche Stelle bei der Ausgangszahl führt also dazu, dass die Laufzeit mit dem Faktor √10 multipliziert wird.

Es handelt sich hier um ein exponentielles Wachstumsverhalten, das man mathematisch mit einer Exponentialfunktion beschreiben kann: Wenn k die Anzahl der Stellen der Ausgangszahl angibt, dann erhält man eine Laufzeit vom Typ L(k) = c*(√10)k mit einer Konstanten c.

Prognose:Wenn die Zahl 100 Stellen haben soll, also 88 Stellen mehr als eine 12-stellige Zahl, so benötigt man nach der gefundenen Gesetzmäßigkeit 1044-mal so lange wie bei der 12-stelligen Zahl - also etwa 1044 Sekunden.

...

Zahl: 1000000000039

Primfaktoren: [1000000000039]

Rechenzeit: 0.906267137304

Zahl: 10000000000037

Primfaktoren: [10000000000037]

Rechenzeit: 2.88270213114

Zahl: 100000000000031

Primfaktoren: [100000000000031]


Zahl: 1000000000000037

Primfaktoren: [1000000000000037]


Zahl: 10000000000000061

Primfaktoren: [10000000000000061]


...

47 Kostenanalyse

worst case: n ist die größte Primzahl mit i Stellen


Beachte: 10i-1 < n < 10i

Probedivisionen:

z = n

z % 2 > 0

z % 3 > 0

...

z % 31 > 0; Beachte: √983 = 31.35...

-> z ist Primzahl

Anzahl der Probedivisionen: 31 > √100 = (√10)2

best case: n ist eine Zweierpotenz mit i Stellen

Beispiel: n = 29 = 512; i = 3

Beachte: 10 < 24; n < 10i < 24*i

Probedivisionen:

z = n

z % 2 = 0

p = z; faktoren = faktoren + [p]; z = z//2

z % 2 = 0

p = z; faktoren = faktoren + [p]; z = z//2

...

Anzahl der Probedivisionen: 9 < 4*3

best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen

worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen

average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle

(√10)i-1 -1< = K(i) <= (√10)i -1K(i) <= 4*i

48 Wachstumsverhalten

(√10)i-1 <= K(i) <= (√10)iK(i) <= 4*i

best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen

worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen

lineares Wachstum

exponentielles Wachstum

Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten den festen Betrag 4.

Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten mit dem Faktor √10. Wenn man die Problemgröße um 2 erhöht, dann wachsen die Kosten mit dem Faktor √10*√10, also mit den Faktor 10.

f(i) = 4*i f(i) = (√10)i

49

Anwendbarkeit des Faktorisierungsalg.

Angenommen, der Rechenaufwand beträgt bei 10 Stellen 1 Zeiteinheit.

Dann beträgt der Rechenaufwand bei 100 Stellen 1045 Zeiteiheiten.

Wenn sich die Rechnergeschwindigkeit um den Faktor 1000 verbessert, dann beträgt der Rechenaufwand immer noch 1042 Zeiteiheiten.

Der unten dargestellte Faktorisierungsalgorithmus ist praktisch nicht anwendbar.


initialisiere die Liste faktoren: faktoren = []

initialisiere die Hilfsvariable z: z = n

SOLANGE z > 1:



z = z // p

Rückgabe: faktoren

50

Komplexität d. Faktorisierungsproblems

Problem: Gibt es „schnelle“ Algorithmen zur Primfaktorzerlegung?

Es gibt eine Vielzahl an Faktorisierungsalgorithmen. Bis jetzt ist es nicht gelungen, einen Algorithmus zur Primfaktorzerlegung zu entwickeln, der eine nicht-exponentielle Zeitkomplexität hat.

51

Ein nichtdeterministischer Algorithmen

ALGORITHMUS primfaktoren

Übergabe: natürliche Zahl n

primfaktoren = []

z = n

SOLANGE z > 1:

i = Anzahl der Stellen von z

# rate eine natürliche Zahl k mit i Stellen (als potentieller Primfaktor)

k = 0

WIEDERHOLE i mal:

k = k * 10

z = 0 | z = 1 | z = 2 | z = 3 | z = 4 | z = 5 | z = 6 | z = 7 | z = 8 | z = 9

k = k + z

# überprüfe, ob k tatsächlich Primfaktor von z ist

WENN k > 1 und k < z und z%k == 0 und istPrimzahl(k):

primfaktoren = primfaktoren + [k]

z = z // k

SONST:

primfaktoren = primfaktoren + [z]

z = 1

Rückgabe: primfaktoren

nichtdeterministisch

Orakel

„Jetzt eine 5“

Der Algorithmen liefert die Liste der Primfaktoren, wenn das Orakel jeweils die „richtige“ Ziffer liefert.

52

Ein nichtdeterministischer Algorithmen

ALGORITHMUS primfaktoren

Übergabe: natürliche Zahl n

primfaktoren = []

z = n

SOLANGE z > 1:

i = Anzahl der Stellen von z

# rate eine natürliche Zahl k mit i Stellen (als potentieller Primfaktor)

k = 0

WIEDERHOLE i mal:

k = k * 10

z = 0 | z = 1 | z = 2 | z = 3 | z = 4 | z = 5 | z = 6 | z = 7 | z = 8 | z = 9

k = k + z

# überprüfe, ob k tatsächlich Primfaktor von z ist

WENN k > 1 und k < z und z%k == 0 und istPrimzahl(k):

primfaktoren = primfaktoren + [k]

z = z // k

SONST:

primfaktoren = primfaktoren + [z]

z = 1

Rückgabe: primfaktoren

nichtdeterministisch

Der nichtdeterministische Algorithmus hat eine polynomiale Zeitkomplexität.

53 Die Klassen P und NP

Zur Klasse P gehört das Problem des Primzahltests („PRIMES“).

P bezeichnet die Klasse der Probleme, die mit einem Algorithmus mit polynomialer Zeitkomplexität gelöst werden können.

Jedes Problem aus P gehört auch zu NP.

Zur Klasse NP gehört auch das Problem der Primfaktorzerlegung („FACTORIZE“).

NP bezeichnet die Klasse der Probleme, die mit einem nichtdeterministischen Algorithmus mit polynomialer Zeitkomplexität gelöst werden können.

54 NP-vollständige Probleme

Ein Problem p* heißt NP-vollständig genau dann, wenn es in der Komplexitätsklasse NP liegt (d.h. mit einem nichtdeterministischen Algorithmus mit polynomialer Komplexität gelöst werden kann) und wenn jedes Problem p aus NP auf p* polynomial reduzierbar ist.

NP-vollständige Probleme spielen bei der Klärung der Frage P=NP? eine zentrale Rolle. Wenn es gelingt, ein NP-vollständiges Problem p* mit einem Algorithmus mit polynomialer Komplexität zu lösen, dann ist die Aussage P=NP bewiesen. Denn, NP-Vollständigkeit bedeutet ja, dass jedes Problem p aus NP auf p* polynomial reduzierbar ist. Aus einem polynomialen Algorithmus für p* lässt sich dann ein polynomialer Algorithmus für jedes p aus NP erzeugen.

Zur Klärung der Frage P=NP? konzentriert man sich also auf das Lösen NP-vollständiger Probleme.

NPp*

p

p

p

<=

<=

<=

55 Ein NP-vollständiges Problem

Hamilton-Problem:

Gegeben ist ein Graph mit seinen Knoten und Kanten. Gesucht ist eine Rundreise durch den Graphen, in der jeder Knoten genau einmal vorkommt - nur Start- und Zielknoten kommen genau zweimal vor. Eine solche Rundreise wird auch Hamiltonkreis genannt.

56 P = NP?

Es gibt inzwischen eine Vielzahl von Problemen, die als NP-vollständig nachgewiesen sind. Zu diesen Problemen gehört das Hamilton-Problem.

Alle Versuche, ein NP-vollständiges Problem mit einem polynomialen Algorithmus zu lösen, sind bisher fehlgeschlagen. Die NP-vollständigen Probleme erweisen sich also als "harte Nüsse" und gelten als schwer lösbare Probleme.

Aufgrund der vielen fehlgeschlagenen Versuche, einen polynomialen Lösungsalgorithmus für ein NP-vollständiges Problem zu finden, vermutet man, dass die Frage P=NP? negativ zu beantworten ist.

Sollte es dennoch gelingen, ein NP-vollständiges Problem mit einem polynomialen Algorithmus zu lösen, so lässt sich jedes andere Problem aus deer Klasse NP (als auch das Faktorisierungsproblem) mit einem polynomialen Algorithmus lösen.

Documents

Komplexität von Algorithmen und Problemen Klaus Becker 2014