Einstieg in die Informatik mit Java - math.kit. · PDF fileEinstieg in die Informatik mit Java...

Einstieg in die Informatik mit JavaEffizienz

Gerd Bohlender

Institut fur Angewandte und Numerische Mathematik

1 / 32

Gliederung

1 Uberblick: was ist Effizienz?

2 Landau-Symbole

3 Eier im Korb

4 Zyklische Ziffern

2 / 32

Gliederung

1 Uberblick: was ist Effizienz?

2 Landau-Symbole

3 Eier im Korb

4 Zyklische Ziffern

3 / 32

Uberblick: was ist Effizienz?

In diesem Kapitel betrachten wir verschiedene Aspekte derEffizienz eines Programms

• Benotigte Rechenzeit• Ausnutzung der Performance des Computers• Beispiel Parallelrechner mit p Prozessoren:

Effizienz(p) = Zeit(1)pZeit(p)

• Benotigter Speicher• Aufwand des Programmierers• ...• 2 Beispiele

4 / 32

Gliederung

1 Uberblick: was ist Effizienz?

2 Landau-Symbole

3 Eier im Korb

4 Zyklische Ziffern

5 / 32

Asymptotischer Aufwand eines Algorithmus –Landau-Symbole

• Landau-Symbole: Schreibweise f (n) ∈ O(g(n)) fur

”f wachst nicht wesentlich schneller als g“(Edmund Landau, Berlin / Gottingen / Jerusalem,1877-1938)

• Die Funktion f (n) ist ∈ O(g(n)), fur n →∞, genau wennes Konstanten n0 und M gibt mit

|f (n)| < M · |g(n)|

fur alle n > n0

• Alternative Definition: f (n) ∈ O(g(n)) genau wenn0 ≤ lim supn→∞ | f (n)

g(n) | < ∞• Weitere Varianten siehehttp://de.wikipedia.org/wiki/Landau-Symbole

6 / 32

Landau-Symbole – Beispiele

• g(n) ist meist eine einfache Funktion, z.B.O(n), O(n2), O(log n), ...

Notation Bedeutung wenn das Argument verdoppelt wird,f ∈ f wachst dann andert sich f etwa so:O(1) garnicht f bleibt beschranktO(n) linear f verdoppelt sichO(n log n) superlinear f wachst auf etwas mehr als das DoppelteO(n2) quadratisch f vervierfacht sichO(n3) kubisch f verachtfacht sichO(2n) exponentiell wenn das Argument um 1 erhoht wird,

dann verdoppelt sich f

7 / 32

Landau-Symbole – Anwendung

• Angaben zum Rechenaufwand eines Algorithmus(asymptotische Komplexitat)

• Angaben zum Speicherbedarf eines Algorithmus

Beispieln × n-Matrix (Zahlenschema mit n Zeilen und n Spalten)• Speicherbedarf O(n2)

• Rechenaufwand fur Addition O(n2)

• Rechenaufwand fur Multiplikation O(n3)

n O(n2) O(n3)

10 100 1000100 10000 1000000

1000 1000000 1000000000

8 / 32

Landau-Symbole – Rechenregeln

Rechenregeln fur den asymptotischen Aufwand:• Konstante Faktoren spielen keine Rolle:

O(c · g(n)) = O(g(n)) fur eine reelle Konstante c 6= 0,folglich gilt auchO(log2 n) = O(ln n) = O(log10 n)

• Langsamer anwachsende Terme konnen vernachlassigtwerden, z.B. gilt mit reellen Konstanten a > b und c:O(na + c · nb) = O(na)O(na + c · log n) = O(na)O(2n + c · nb) = O(2n)

• Beispiel:O(2n3 + 3n2 + 24n + 799) = O(n3)

9 / 32

Landau-Symbole – Einsatz zum Vergleich vonAlgorithmen

Beispiel: sortiere n Zahlen x0, x1, . . . , xn−1

Algorithmus 1 (Bubblesort) Algorithmus 2 (Quicksort)n O(n2) O(n log n)

2 4 24 16 88 64 24...

1000 106 10000106 1012 20 · 106

• Algorithmus ist fur n = 106 etwa 100000 mal schneller.• 100000 ≈ 1 Tag / 1 Sekunde

10 / 32

Landau-Symbole – Vorsicht

• Aber Vorsicht! Alle Aussagen gelten nur asymptotisch furn →∞, also ab einem (unbekannten) n0 und mit einem(unbekannten) Faktor M.

• Fur ein ”kleines“ n konnte Algorithmus 1 durchausschneller sein als Algorithmus 2.

11 / 32

Gliederung

1 Uberblick: was ist Effizienz?

2 Landau-Symbole

3 Eier im Korb

4 Zyklische Ziffern

12 / 32

Eier im Korb - Aus einem alten Rechenbuch

Ein Mann stoßt den Korb voller Eier einer Marktfrau um. DieEier gehen zu Bruch. Der Mann will den Schaden ersetzen undfragt wieviele Eier im Korb waren.Die Marktfrau antwortet:

”Die genaue Zahl weiß ich nicht.Aber wenn ich immer 2 Eier aus dem Korb genommenhabe, dann blieb eines ubrig.Genauso, wenn ich immer 3, immer 4, immer 5 oderimmer 6 Eier heraus genommen habe.Aber wenn ich immer 7 Eier heraus genommen habe,dann blieb keines ubrig.“

Wieviele Eier waren (mindestens) im Korb?

13 / 32

Eier im Korb - Erster Algorithmus

Teste alle Zahlen n = 1, 2, 3, ...

• Beginne mit n = 1• Prufe, ob die Zahl n bei Division durch 2, 3, 4, 5, 6 den

Rest 1 ergibt und ob n durch 7 ohne Rest teilbar ist.• Ist dies der Fall, dann brich ab und gib das Ergebnis aus.

Andernfalls erhohe n um 1 und prufe nochmal.

14 / 32

Eier im Korb - Erstes Java-Programm

public class Eier {

public s t a t i c void main ( S t r i n g [ ] args ){i n t i =0;do i ++;while ( i %2!=1 | | i %3!=1 | | i %4!=1 | |

i %5!=1 | | i %6!=1 | | i %7!=0);System . out . p r i n t l n ( ” Es waren ” + i +

” E ie r im Korb . ” ) ;}

}

15 / 32

Eier im Korb - Zweiter Algorithmus

Es kommen nur Zahlen in Frage, die bei Division durch 2, 3, 4,5, 6 den Rest 1 ergeben.Mit etwas Mathematik stellt man fest: Es kommen nur Zahlen inFrage, die bei Division durch kgV(2, 3, 4, 5, 6) = 60 den Rest 1ergeben.Also: Teste alle Zahlen n = 1, 61, 121...

• Beginne mit n = 1• Prufe, ob n durch 7 ohne Rest teilbar ist.• Ist dies der Fall, dann brich ab und gib das Ergebnis aus.

Andernfalls erhohe n um 60 und prufe nochmal.

16 / 32

Eier im Korb - Zweites Java-Programm

public class Eier2 {

public s t a t i c void main ( S t r i n g [ ] args ){i n t i =1;do i += 60;while ( i%7 != 0 ) ;System . out . p r i n t l n ( ” Es waren ” + i +

” E ie r im Korb . ” ) ;}

}

17 / 32

Vergleich der Effizienz

• Programm 2 braucht nur 1/60 der Rechenzeit vonProgramm 1

• Beide Programm brauchen nur Bruchteile einer Sekunde• Rechenzeit spielt hier keine Rolle• Fazit: Die Arbeitszeit des Programmierers fur die

mathematischen Uberlegungen ist ”verschwendet“• Ubrigens ... es waren 301 Eier im Korb!

18 / 32

Gliederung

1 Uberblick: was ist Effizienz?

2 Landau-Symbole

3 Eier im Korb

4 Zyklische Ziffern

19 / 32

Zyklische Ziffern - Das Problem

• Finde eine Zahl mit Endziffer 5• Multipliziere sie mit 5• Ist das Produkt gleich der ursprunglichen Zahl, wenn man

die 5 am Ende streicht und dafur vorne anfugt?• Beispiel: 5 * abcd5 = 5abcd

(mit 4 Ziffern a, b, c, d)• Verallgemeinerung: ersetze 5 durch Faktor 2 bis 9

Quelle: Jacques Arsac, Computerdenkspiele selbstprogrammiert, Problem 3

20 / 32

Zyklische Ziffern - Erster Algorithmus

Teste alle Zahlen n = 1, 2, 3, ...

• Beginne mit n = 1• Prufe, ob die Zahl n die Bedingung ”Zyklische Ziffern“ erfullt• Ist dies der Fall, dann brich ab und gib das Ergebnis aus.

Andernfalls erhohe n um 1 und prufe nochmal.

21 / 32

Zyklische Ziffern - Erstes Java-Programm

public class ZykZ i f f 1 {

public s t a t i c void main ( S t r i n g [ ] args ){i n t i =0;do i ++;while ( i ∗5 != i /10+50000); / / be i 4 Z i f f e r n abcdSystem . out . p r i n t l n ( ” Zyk l i sche Z i f f e r n : ” + i ) ;

}

}

22 / 32

Zyklische Ziffern - Probleme mit diesem Programm

• Unbekannt, ob 4 Stellen abcd notig sind oder mehr oderweniger

• Ggf. mussen alle Stellenzahlen durchprobiert werden• Reicht der Zahlbereich von int (9 Stellen) aus?• Reicht long (19 Stellen)?• Rechenzeit???

23 / 32

Zyklische Ziffern - Mathematische Idee

Fuhre Ziffernvergleich bei 5 ∗ abcd5 = 5abcd durch,beginnend bei der niederwertigsten Ziffer.

• 5 ∗ abcd5 = 5abcd fuhrt wegen 5 ∗ 5 = 25 zu d = 5• Es entsteht ein Ubertrag von 2, der im nachsten Schritt zu

berucksichtigen ist• 5 ∗ abc55 = 5abc5 fuhrt wegen 5 ∗ 5 + 2 = 27 zu c = 7• Es entsteht ein Ubertrag von 2• 5 ∗ ab755 = 5ab75 fuhrt wegen 5 ∗ 7 + 2 = 37 zu b = 7• Es entsteht ein Ubertrag von 3• usw. (egal wie viele Stellen abcd vorliegen)• Der Algorithmus ist zu Ende, wenn

• die berechnete Ziffer = 5 ist, und• der Ubertrag = 0 ist

24 / 32

Zyklische Ziffern - Zweiter Algorithmus

Verallgemeinerung: ersetze 5 durch beliebigen Faktor 2 bis 9

• Starte mit Ziffer = Faktor und Ubertrag = 0• Berechne das 2-stellige Produkt = Ziffer * Faktor +

Ubertrag• Zerlege Produkt in die niederwertige Ziffer

und den hoherwertigen Ubertrag• Wiederhole solange

• die berechnete Ziffer nicht gleich dem Faktor ist, oder• der Ubertrag nicht 0 ist

25 / 32

Zyklische Ziffern - Zweites Programm

import java . u t i l .∗ ;

public class Z y k z i f f 5 {

public s t a t i c void main ( S t r i n g [ ] args ) {Locale . se tDe fau l t ( Locale .US) ;Scanner sc = new Scanner ( System . i n ) ;i n t Faktor , Z i f f e r , Uebertrag =0 , Produkt , S t e l l e n =0;System . out . p r i n t ( ” Mi t welchem Faktor s o l l m u l t i p l i z i e r t werden ? ” ) ;Faktor = sc . n e x t I n t ( ) ; / / Faktor e in lesenZ i f f e r = Faktor ; / / n i ed e rwe r t i g s t e Z i f f e r = FaktorSystem . out . p r i n t l n ( ”Das Ergebnis l a u t e t ( rueckwaerts gelesen ! ) : ” ) ;do{

System . out . p r i n t ( Z i f f e r ) ; / / a k t u e l l e Z i f f e r ausdruckenS t e l l e n ++; / / S t e l l e n z a h l be i j ede r Ausgabe erhoehenProdukt = Z i f f e r ∗ Faktor + Uebertrag ; / / neues Produkt , z w e i s t e l l i gZ i f f e r = Produkt % 10; / / neue Z i f f e r = n ieders te S t e l l e des ProduktsUebertrag = Produkt / 10; / / neuer Uebertrag = hoechste S t e l l e des Produkts

} / / wiederholen , wenn eine der beiden . . .while ( Z i f f e r != Faktor | | Uebertrag != 0 ) ; / / . . . Abbruch−Bedingungen v e r l e t z t i s tSystem . out . p r i n t l n ( ) ;System . out . p r i n t l n ( ” Es hat ” + S t e l l e n + ” S t e l l e n ” ) ;

}

}

26 / 32

Zyklische Ziffern - Ergebnisse

c:\b\java>java Zykziff5Mit welchem Faktor soll multipliziert werden ? 5Das Ergebnis lautet (rueckwaerts gelesen !):557783964376381959798442216035623618040201Es hat 42 Stellen

27 / 32

Zyklische Ziffern - Ergebnisse

Mit welchem Faktor soll multipliziert werden ? 2

248637498751362501

Es hat 18 Stellen

Mit welchem Faktor soll multipliziert werden ? 3

3973142715569860268572844301

Es hat 28 Stellen

Mit welchem Faktor soll multipliziert werden ? 4

465201

Es hat 6 Stellen

Mit welchem Faktor soll multipliziert werden ? 6

6697760446811726754748050389833022395531882732452519496101

Es hat 58 Stellen

Mit welchem Faktor soll multipliziert werden ? 7

7975048813263572944101

Es hat 22 Stellen

Mit welchem Faktor soll multipliziert werden ? 8

8487228562101

Es hat 13 Stellen

Mit welchem Faktor soll multipliziert werden ? 9

91742202834944046788980825779716505595321101

Es hat 44 Stellen

28 / 32

Zyklische Ziffern - Laufzeit des zweiten Algorithmus

• 42 Schleifendurchlaufe• etwa 10 Operationen pro Schleife• theoretisch etwa 10−7 Sekunden auf einem

handelsublichen PC• mit Java-Overhead (Interpretation, Startup)

deutlich unter 1 Sekunde

29 / 32

Zyklische Ziffern - Laufzeit des ersten Algorithmus

• Er benotigt 1042 Schleifendurchlaufe= etwa 1043 Operationen

• Schnellster Rechner zzt. (2009, Quelle: www.top500.org):etwa 1015 Flops (Floating point Operationen pro Sekunde)

• Dieser braucht etwa 1028 Sekunden zur Losung• 1028 Sekunden = etwa 1020 Jahre

(1 Jahr = 365 ∗ 86400 Sekunden = etwa 3 ∗ 107 Sekunden)• ... aber das Universum existiert erst

etwa 1010 Jahre seit dem Urknall!

30 / 32

Zyklische Ziffern - Laufzeitvergleich der beidenAlgorithmen

• Der erste Algorithmus braucht 1020 Jahre auf demschnellsten Rechner der Erde

• Der zweite Algorithmus braucht einen Bruchteil einerSekunde auf einem handelsublichen PC

• Fazit: Nachdenken uber mathematische Hintergrunde hatsich gelohnt

31 / 32

Zyklische Ziffern - Wann sind Computer schnell genugfur den ersten Algorithmus?

• Der erste Algorithmus braucht 1020 Jahre auf dem heuteschnellsten Rechner der Erde

• Supercomputer wurden im letzten Jahrzehnt fast um denFaktor 1000 schneller (Quelle: www.top500.org)

• In 70 Jahren ware das (theoretisch!!!) ein Faktor 1021

• Im Jahre 2080 brauchte der schnellste Computer der Erdenoch 1 Monat(sehr theoretisch!!!)

32 / 32