Einführung in die Informatik I - fh-muenster · 2018. 11. 29. · Prof. Dr. Nikolaus Wulff Informatik I 11 Optimierter ggT Algorithmus Gesucht ist der ggT(a,b) für0.Setze m=a und

Prof. Dr. Nikolaus Wulff

Einführung in die Informatik I

Algorithmen und deren Programmierung

Prof. Dr. Nikolaus Wulff Informatik I 2

Definition Algorithmus• Ein Algorithmus ist eine präzise formulierte Hand-

lungsanweisung zur Lösung einer gleichartigen Klasse von Problemen.

– Ein Algorithmus besteht meist aus einer Folge von Anweisungen, die von einem Menschen/einer Maschine interpretiert und geeignet abgearbeitet werden können.

– Wenn er immer in einer endlichen Anzahl von Schritten beendet ist, terminiert der Algorithmus.

– Ein deterministischer Algorithmus hat eine eindeutig festgelegte Schrittfolge.

– Ist das Endergebnis, bei vorgegebenen Eingangsdaten, eindeutig bestimmt, so ist der Algorithmus determiniert.


Algorithmen Beispiele

Umgangssprachliche Algorithmen:

• Jedes (gute, genaue) Koch- und Backrezept.

• Bedienungsanleitung eines Telefons.

• Tonfolge einer Melodie an Hand von Noten.

• ...

Mathematische Algorithmen:

• Zerlegung einer natürlichen Zahl in Primfaktoren.

• Finden des größten gemeinsamen Teilers (ggT).

• Lösen von Ax=y per Gauss-Eliminationsverfahren.

• Lösen von f(x)=0 per Newton-Verfahren.


Entwicklung des ggT Algorithmus

• Zur Illustration wird ein Algorithmus zur Bestim-mung des größten gemeinsamen Teilers ggT ent-wickelt.

• Für Zahlen gilt die Beziehung

• Der Algorithmus wurde bereits um ~330 v.Chr. beschrieben:

a ,b∈ℕ

ggT a ,b⋅kgV a ,b=a⋅b

Wenn b aber a nicht misst, und man nimmt bei a, b abwechselnd immer das Kleinere vom Größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die Vorangehende misst...


Euklidischer Algorithmus

Gesucht ist der ggT(a,b) für

0. Setze m=a und n=b.

1. Falls m < n

1* vertausche m und n .

2. Berechne r = m – n.

3. Setze m=n, n=r.

4. Falls r>0 ist, so mache weiter bei 1.

5. Die Zahl m ist der gesuchte ggT(a,b).

a ,b∈ℕ

Dies ist eine exakte, deterministische Vorschrift. Da m und n immer kleiner werden, muss der Algorithmus nach endlich vielen Schritten terminieren.

Schleife


Flussdiagramm

• Algorithmen lassen sich mittels Flussdiagrammen grafisch visualisieren.

• Sie bestehen aus einfachen elementaren Symbolen:– Anfang: Hier beginnt die Ausführung

•

– Anweisung/Elementaraktion–

– Der Pfeil zeigt auf nächste Anweisung–

– Test: Im Karo steht eine Bedingung (if)–

– Ende: Hier endet die Ausführung


Flussdiagramm des ggT

m < n

r := mm := nn := r

r := m - nm := nn := r

r > 0

m := an := b

FT

T F

0

1*2 3

45

Start

Ziel

1


C Implementierung des ggTint ggT(int a, int b) { int r, m = a, n = b; do { if (m < n) { r = m; m = n; n = r; } r = m - n; m = n; n = r; } while(r>0); return m;}

0

2

3

4

5

1


Ablauf einer ggT Berechnung

• Ablauf der Berechnung vom ggT(64,24):

• Nach fünf Iterationen ist das Ergebnis 8 ermittelt.

• Ist dies die beste Methode um den ggT zu berechnen?

• Problematisch sind die vielen Subtraktionen bei großen Unterschieden zwischen a und b.

– r1 = 64 – 24 = 40 , m

1 = 40, n

1 = 24

– r2 = 40 – 24 = 16 , m

2 = 24, n

2 = 16

– r3 = 24 – 16 = 8 , m

3 = 16, n

3 = 8

– r4 = 16 – 8 = 8 , m

4 = 8, n

4 = 8

– r5 = 8 – 8 = 0 , m

5 = 8, n

5 = 0


Optimierung des ggT Algorithmus

• Eine Analyse des größten gemeinsamen Teilers zeigt:– ggT(a, b) = ggT(b, a) und

– ggT(a, b) = ggT(a, a-b)

• Um z.B. den ggT(10,2) zu berechnen muss 5 mal die 2 abgezogen werden:– ggT(10,2) = ggT(8,2) = ggT(6,2) = ggT(4,2) = ggT(2,2) = 2

• Der ggT kann wesentlich schneller berechnet werden, wenn anstatt mehrfacher Subtraktionen eine Division mit Rest erfolgt, d.h. für a=qb+r:

– ggT(a, b) = ggT(qb+r, b) = ggT(b, r)

• Die Modulo a/b=q mod r Variante benötigt weniger Schritte, da q Subtraktionen eingespart werden.


Optimierter ggT Algorithmus

Gesucht ist der ggT(a,b) für

0. Setze m=a und n=b.

1. Falls m < n vertausche m und n.

2. Berechne r = m mod n.

3. Setze m=n, n=r.

4. Falls r>0 ist, so mache weiter bei 1.

5. Die Zahl m ist der gesuchte ggT(a,b).

a ,b∈ℕ

Die Modulo Operation ist leicht mit einem Rechner auszuführen und der Algorithmus terminiert auch bei großen Unterschieden zwischen a und b wesentlich schneller. Eine kleine Änderung mit großer Wirkung!


ggT mit Modulo Operationint ggT(int a, int b) { int r, m = a, n = b; do { if (m < n) { r = m; m = n; n = r; } r = m % n; m = n; n = r; } while(r>0); return m;}

0

2

3

45

1


Optimierte ggT Implementierung int ggT(int m, int n) { int r; do { if (m < n) { r = m, m = n, n = r; } r = m % n; m = n; n = r; } while(r>0); return m;}

• Da C Kopien von a und b verwendet, kann das Kopieren von a nach m und b nach n entfallen...


Zahlen raten

• Aufgabe ist es, eine bestimmte ganze Zahl n aus einer endlichen Menge zu erraten.

• Geantwortet wird immer nur mit „die Zahl n ist kleiner, größer oder gleich“ einer gegebenen Zahl z.

• Gesucht ist die beste Strategie, um die Zahl n mög-lichst schnell zu finden.

• Ein deterministisches Verfahren, das immer zum Erfolg führt, ist bei z=a zu beginnen und dann immer z um eins zu erhöhen bis n gefunden wurde, dies wird spätesten nach m=(b-a) Versuchen der Fall sein.

• Dies ist die „dümmste und ungünstigste Variante“ und benötigt im Mittel m/2 Versuche.

M=[a ,b]⊂ℕ


Intervallhalbierung

Effizienter ist das Verfahren der Intervallhalbierung:

• Um die m-elementige Menge M auf 1 zu reduzieren sind maximal k Halbierungen notwendig, mit m < 2k. D.h. dieser Algorithmus hat eine Laufzeit ~ log

2m.

1. Wähle als gesuchte Zahl z =(b+a)/2.

2. Falls z < n setze als neue untere Intervallgrenze a = z

und gehe zu 1.3. Fall z > n setze als neue obere Intervallgrenze b = z

und gehe zu 1.4. Es gilt z = n und die gesuchte Zahl ist gefunden.


Flussdiagramm Intervallhalbierung

z < n z > n

z := (a+b)/2

F

TT F

1

2 3

4

Start

Ziel

a := z b := z


Nullstellensuche

• Ein weiteres Beispiel für einen einfachen Algorithmus ist das Bisektionsverfahren zur Suche der Nullstelle einer stetigen Funktion auf einem endlichen Intervall mit .

• Letztere Bedingung garantiert, unter Anwendung des Zwischenwertsatzes für stetige Funktionen, dass min-destens eine Nullstelle existieren muss mit

• Das eben illustrierte Verfahren auf einer diskreten Menge M lässt sich direkt auf ein Intervall übertragen.

• Durch fortgesetzte Halbierung des Intervalls I wird die gesuchte Nullstelle immer enger eingegrenzt.

f :ℝℝ

I=[a ,b]⊂ℝ f a⋅ f b0

f =0.∈[a ,b ]


Das Bisektionsverfahren

• Analog zum Zahlenraten lautet die Anweisung für das Bisektionsverfahren generiere eine Folge {x

k}:

1. Wähle als gesuchte Zahl x =(b+a)/2.

2. Falls f(x) < 0 setze als neue untere Intervallgrenze a = x

und gehe zu 4.3. Fall f(x) > 0 setze als neue obere Intervallgrenze b = x

und gehe zu 4.4. Die Bedingung f(z) = 0 wird allerdings kaum zu erfüllen

sein. Statt dessen wird gesetzt: Falls das verbleibende Fehlerintervall (b-a)/2 größer ist, als eine vorgegebene Fehlerschranke , so gehe zu Schritt 1.

5. Das aktuelle xk approximiert die gesuchte Nullstelle

genau genug, d.h ∣xk−∣


Das Bisektionsverfahren

• Das Bisektionsverfahren: Durch fortgesetzte Intervall-halbierung entsteht eine konvergente Folge {x

k} mit

und limk ∞ x k= f =0

Quelle: http://de.wikipedia.org/wiki/Bisektion


Konvergenzverhalten

• Nach der ersten Iteration ist x1=(a+b)/2 und der

maximale Fehler

• Nach der k-ten Iteration ist der Fehler bedingt durch die Intervallschachtelung abschätzbar zu:

• D. h. die Zahlen {xk} definieren eine konvergente

Cauchy-Folge: Zu beliebigem > 0 gibt es mit ein so dass

1=∣x 1−∣≤b−a/2.

k

k=∣xk−∣≤b−a /2k

m :=log2b−a/ n:=⌊m1⌋∈ℕ

k=∣x k−∣ ∀ kn


Algorithmen entwickeln

• Die Lösung eines Problems zu finden ist nicht einfach und auch nicht systematisch standardisiert.

• Algorithmen zu entwickeln ist „eine Kunst“.

• Algorithmen und Daten werden im Rechner immer als Binärfolgen codiert. Der Algorithmus muss i. A. immer mathematisch definiert und formal auf seine Korrektheit überprüft werden.

• Hierzu werden häufig Beweise durch vollständige Induktion, Beweise durch Widerspruch oder aber im mathematischen Kontext Approximationen durch konvergente Cauchy-Folgen verwendet.


Zusammenfassung

• Um einen Algorithmus zu entwickeln bedarf es zunächst einer Lösungsidee.

• Das Auffinden dieser Lösungsidee ist meist der schwierigste Teil der Arbeit und ein kreativer Akt.

• Sodann muss sichergestellt werden, dass diese Idee (mathematisch, formal) korrekt ist.

• Erst als letzter Schritt wird die Idee des Algorithmus mit Hilfe einer konkreten Programmiersprache implementiert, ausreichend getestet und auf Fehler untersucht.

Documents

Einführung in die Informatik I - fh-muenster · 2018. 11. 29. · Prof. Dr. Nikolaus Wulff Informatik I 11 Optimierter ggT Algorithmus Gesucht ist der ggT(a,b) für0.Setze m=a und