-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathIntroduction.html
More file actions
644 lines (638 loc) · 39.1 KB
/
Introduction.html
File metadata and controls
644 lines (638 loc) · 39.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
<!DOCTYPE html><html lang="de"><head>
<title>Variationen zum Thema: Algorithmen</title>
<meta name="title" content="Variationen zum Thema: Algorithmen">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta charset="UTF-8">
<meta name="description" content="Eine Einführung anhand von Beispielen">
<meta name="keywords" content="Java,Algorithmen,Datenstrukturen">
<meta name="author" content="Ralph P. Lano">
<meta name="robots" content="index,follow">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" type="text/css" href="book.css">
</head>
<body><center>
<div id="wrap">
<ul class="sidenav">
<p><a href="index.html">Variationen zum Thema</a><a href="index.html">Algorithmen</a></p>
<li><a href="Introduction.html" class="active">Introduction</a></li>
<li><a href="Lists.html">Lists</a></li>
<li><a href="Maps.html">Maps</a></li>
<li><a href="Recursion.html">Recursion</a></li>
<li><a href="Algorithms.html">Algorithms</a></li>
<li><a href="Sorting.html">Sorting</a></li>
<li><a href="Trees.html">Trees</a></li>
<li><a href="Graphs.html">Graphs</a></li>
<li><a href="Text.html">Text</a></li>
<li><a href="Techniques.html">Techniques</a></li>
</ul>
<div class="content"><p>
<img src="images/Pi2.png" style="display: block; margin-left: auto; margin-right: auto; width: 221px; height: 211px;" /></p>
<h1>
Introduction</h1>
<p>
Algorithmen sind überall. Algorithmen bestimmen unser tägliches Leben. Beim Zusammenbauen von IKEA Möbeln, beim Backen eines Kuchens oder beim Spielen mit Lego folgen wir einem Algorithmus. Hinter selbstfahrenden Autos, Gesichtserkennung und Fingerabdrucksensoren stecken Algorithmen. Die Verschlüsselung, die künstlichen Intelligenz und auch die moderne Genetik verwenden Algorithmen. Es gibt Algorithmen die sind sehr alt, es gibt Algorithmen die sind sehr schön. Algorithmen können trivial sein, aber es gibt auch sehr komplexe Algorithmen. Es gibt sogar Algorithmen die produzieren Kunst. Auf den folgenden Seiten wollen wir uns ein wenig mit der Welt der Algorithmen vertraut machen, und wir beginnen ganz einfach.</p>
<p>
.</p>
<h2>
Introduction</h2>
<p>
Das Wort Algorithmus ist eigentlich die latinisierte Version des Nachnamens des persischen Mathematikers Abu Dscha'far Muhammad ibn Musa al-Chwarizmi (ca. 780 - ca. 850). Er ist u.a. verantwortlich für die Verbreitung des indischen Zahlensystems, einschließlich der Zahl Null. Er hat auch das Buch "Das kurzgefasste Buch über die Rechenverfahren durch Ergänzen und Ausgleichen" geschrieben, welches allgemein als Beginn der Algebra angesehen wird [3].</p>
<p>
Laut Wikipedia ist ein Algorithmus eine effektive Methode etwas innerhalb einer begrenzten Zeit und mit begrenztem Raum zu berechnen, das man in einer wohl definierten Sprache ausdrücken kann. Diese Sprache beschreibt wie man von einem Anfangszustand, mit einer begrenzte Anzahl von Schritten, über wohl-definierte Zwischenzustände, schließlich einen finalen Endzustand erreicht [2]. </p>
<p>
Schauen wir uns einfach mal ein paar Beispiele an.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Pi2.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 191px; float: right;" />Pi</h2>
<p>
Es gibt viele Arten die Kreiszahl Pi auszurechnen, aber die einfachste ist wahrscheinlich die grafische: Wir zeichnen einfach ein Quadrat, und darin einen Viertelkreis. Dann malen wir einfach zufällig Punkte, möglichst gleichmäßig. Wir zählen die Punkte die innerhalb des Viertelkreises liegen, also <em>n_innerhalb = 18</em>, und die Gesamtzahl der Punkte, also <em>n_gesamt =28</em>. Pi ist dann einfach</p>
<pre style="margin-left: 40px;">
Pi = 4 * n_innerhalb / n_gesamt = 2.6</pre>
<p>
Das ist jetzt nicht sehr genau, grob stimmt das aber. Wenn wir nämlich ganz viele Punkte machen, und die Punkte auch wirklich zufällig verteilt sind, dann kommt da wirklich Pi raus.</p>
<p>
.</p>
<h2>
<img alt="" src="images/b63f8aaa-c348-42b5-b144-eb5784d499a0.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 226px; float: right;" />Longest Common Substring</h2>
<p>
DNA-Analyse hört sich jetzt an wie wenn es etwas super-kompliziertes wäre. Teilweise ist es das natürlich auch, speziell bis zu dem Schritt wo man die Buchstaben, also die Reihenfolge der Aminosäuren, hat. Hat man die aber, dann ist es ganz einfach. Nehmen wir an Bart's DNA sieht so aus:</p>
<pre style="margin-left: 40px;">
Bart = "GTTCCTAATA"</pre>
<p>
und die von Homer so</p>
<pre style="margin-left: 40px;">
Homer = "CGATAATTGAGA".</pre>
<p>
Alles was man dann machen muss, um z.B. festzustellen ob Bart wirklich Homer's Sohn ist, die beiden DNA Sequenzen entlang der X- und Y-Achsen auf einem karierten Papier aufzutragen, und die Stellen an denen beide übereinstimmen, markiert man einfach mit einem Kreuzchen. Wenn man sich das dann ansieht findet man Kreuzchen die sich zu einer Diagonale verbinden. Je länger die Diagonelen, desto mehr Übereinstimmung zwischen den beiden DNAs [4].</p>
<p>
.</p>
<h2>
<img alt="" src="images/EuclidGraphics.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 106px; float: right;" />Greatest Common Divisor (GCD)</h2>
<p>
Einer der ältesten Algorithmen der immer noch benutzt wird, stammt von Euclid [5]. Er beschreibt wie man den größten gemeinsamen Teiler zweier Zahlen findet. Die Anleitung wie man das macht, also der Algorithmus geht wie folgt:</p>
<ol>
<li>
ziehe die kleinere Zahl von der größeren solange ab, bis es nicht mehr geht;</li>
<li>
ist die Zahl die übrig bleibt null sind wir fertig, die kleinere Zahl ist der größte gemeinsame Teiler;</li>
<li>
falls die Zahl nicht null ist, dann machen wir aus der übrig gebliebenen Zahl die kleine Zahl und aus der kleinen Zahl die große und beginnen von vorne.</li>
</ol>
<p>
Am besten probiert man das einfach mal mit einem Beispiel aus: nehmen wir an die große Zahl ist 299, und die kleine Zahl ist 115. Verkürzt ergeben sich dann folgende Schritte:</p>
<pre style="margin-left: 40px;">
299 = 115*2 + 69
115 = 69*1 + 46
69 = 46*1 + 23
46 = 23*2 + 0</pre>
<p>
Das bedeutet, dass 23 der größte gemeinsame Teiler von 299 und 115 ist.</p>
<p>
Der Algorithmus hört sich ausgeschrieben etwas kompliziert an, aber wenn man ihn in Java übersetzt, dann ist er verblüffend einfach:</p>
<pre style="margin-left: 40px;">
private int gcd(int a, int b) {
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}</pre>
<p>
Der Algorithmus lässt sich übrigens auch sehr schön visualisieren.</p>
<p>
.</p>
<h2>
Counting People</h2>
<p>
Wohl noch älter als Euclid's Algorithmus ist das Zählen. Man sollte meinen das ist ja eigentlich eine ganz einfach Angelegenheit. Aber sobald es sich um größere Mengen handelt wird es schon etwas schwieriger: wie zählt man denn die Anzahl der Zuschauer in einem etwas größeren Fußballstadium?</p>
<p>
Wir könnten die Leute zählen wie sie ins Stadium kommen, einen nach dem anderen. Oder wir könnten einfach durchzählen lassen, wobei das in einem Stadium nicht ganz so einfach ist. Wir könnten auch ein Foto machen, und dann könnte einer die Leute auf dem Foto zählen. Auf die Art und Weise würden wir die genaue Anzahl der Leute wissen, solange wir uns nicht verzählen. Interessant ist die Frage wie lange das dauert: Nehmen wir an wir haben 20000 Leute im Stadium, und das Zählen einer Person dauert eine Sekunde. Dann dauert es knapp sechs Stunden bis wir fertig sind! Bis wir also fertig mit dem Zählen sind, ist das Spiel schon vorbei.</p>
<p>
Stellt sich die Frage, geht das auch schneller? Wir könnten das Zählen "parallelisiseren": wenn unser Stadium sechs Eingänge hätte, und wir würden an jedem Eingang zählen, dann würde es nur ein sechstel der Zeit in Anspruch nehmen. Wir wären also in einer Stunde fertig. Wenn wir 20000 Eingänge hätten, dann würde das Ganze nur eine Sekunde dauern!</p>
<p>
Gibt es weitere Möglichkeiten Leute in einem Stadium zu zählen? Interessanterweise sehr viele. Vor allem wenn wir nur eine ungefähre Anzahl benötigen. Wir könnten z.B. durch den Stadiumsprecher bitten, dass die Leute deren Nachnahme mit 'A' losgeht aufstehen sollen. Die zählen wir dann und multiplizieren die Zahl mit 26. Schon 26 mal schneller. Wir könnten uns auch einen kleinen Teil des Stadiums suchen, von dem wir wissen wieviele Sitzplätze es dort gibt. Dann zählen wir wieviel Prozent der Sitzplätze dort besetzt sind. Wenn wir annehmen, dass im Schnitt die Leute gleichmässig verteilt sind, können wir damit ausrechnen wieviele Leute ungefähr im Stadium sind. Wir könnten auch alle Sitze weiß anmalen, und den Leuten beim Eintritt rote Mützen geben. Dann machen wir ein Foto und messen einfach wie rot das Bild ist. Je roter desto mehr Leute. Oder wir fragen jemanden der sich mit Menschenmassen auskennt und wenn der dann sagt, "Oh, ich denke das sind so 20000", dann wäre das auch eine Möglichkeit zu zählen, aber eben nur eine Schätzung.</p>
<p>
Worauf wir hinaus wollen: Sehr häufig gibt es mehr als nur einen Weg ein Problem zu lösen. Dabei sind manche Wege schneller als andere, andere sind dafür wieder genauer. Wenn wir also nach einem Algorithmus suchen, dann müssen wir zunächst entscheiden was uns wichtig ist, damit wir dann den passenden Algorithmus wählen können.</p>
<p>
.</p>
<h2>
<img alt="" src="images/gameOfLife.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />GameOfLife</h2>
<p>
Das größte Genie des letzten Jahrhunderts, John von Neumann, versuchte eine hypothetische Maschine zu konstruieren, die Kopien von sich selbst anfertigen konnte. Dies gelang ihm auch, allerdings hatte das mathematische Modell seiner Maschine sehr komplizierte Regeln. Dem britischen Mathematiker John Horton Conway schaffte es anfang der 70er von Neumann's Ideen drastisch zu vereinfachen, heute bekannt unter dem Namen Conway's <em>Game of Life</em> [6].</p>
<p>
Das Universum des Spiel des Lebens ist ein zweidimensionales Gitter aus quadratischen Zellen (GRects), von denen jede in einer von zwei möglichen Zuständen sein kann: lebend (schwarz) oder tot (weiß). Jede Zelle hat acht Nachbarn, und abhängig vom Zustand der Nachbarn entscheidet sich der eigene Zustand in der nächsten Runde nach folgenden Regeln:</p>
<ul>
<li>
jede lebende Zelle mit weniger als zwei lebenden Nachbarn stirbt (Unter-Bevölkerung)</li>
<li>
jede lebende Zelle mit zwei oder drei lebenden Nachbarn lebt</li>
<li>
jede lebende Zelle mit mehr als drei lebenden Nachbarn stirbt (Über-Bevölkerung)</li>
<li>
jede tote Zelle mit genau drei lebenden Nachbarn wird eine lebende Zelle (Fortpflanzung)</li>
</ul>
<p>
Das Resultat dieser einfachen Regeln ist durchaus überraschend.</p>
<p>
.</p>
<hr />
<h1>
Review</h1>
<p>
In der Einführung haben wir uns ein paar einfache, teilweise sehr alte Algorithmen angesehen. Wir haben auch gesehen, dass es Algorithmen gibt die nützlich sind und andere die nur eine Spielerei sind. Es gibt Algorithmen die schnell sind, und es gibt welche die langsam sind. Es gibt genaue und ungenaue Algorithmen. Und meistens gibt es mehr als einen Algorithmus ein bestimmtes Problem zu lösen. Das Wichtigste was allerdings hoffentlich rüberkommt: Algorithms are fun!</p>
<p>
.</p>
<hr />
<h1>
Projekte</h1>
<p>
Algorithmen sind so alt wie die Menschheit. Im Prinzip sind es einfach Kochrezepte, und genau wie diese sind die meisten Algorithmen auch intuitiv. Womit wir uns manchmal etwas schwer tun, ist sie dem Computer beizubringen. Aber wie mit allem, Übung macht den Meister.</p>
<p>
.</p>
<h2>
<img alt="" src="images/EuclidSimple.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />EuclidSimple</h2>
<p>
Wir beginnen mit der einfach Version, einem ConsoleProgram. Wir fragen den Nutzer nach zwei Zahlen,</p>
<pre style="margin-left: 40px;">
int a = readInt("Enter width (e.g. 299): ");
int b = readInt("Enter height (e.g. 115): ");
println( gcd(a, b) );</pre>
<p>
und berechnen dann mit der Methode <em>gcd()</em> von oben den größten gemeinsamen Teiler.</p>
<p>
.</p>
<h2>
<img alt="" src="images/EuclidGraphics.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 106px; float: right;" />EuclidGraphics</h2>
<p>
Als nächstes wollen wir den Euclidschen Algorithmus visualisieren. Dazu verwenden wir ein GraphicsProgram. Zunächst fragne wir wieder den Nutzer nach zwei Zahlen. Da es sich um ein GraphicsProgram handelt, verwenden wir die Klasse <em>IODialog</em>,</p>
<pre style="margin-left: 40px;">
IODialog dialog = getDialog();
int w = dialog.readInt("Enter width (e.g. 299): ");
int h = dialog.readInt("Enter height (e.g. 115): ");
int x = gcd(w, h);</pre>
<p>
Mit dieser Klasse kann man auch Dinge ausgeben, z.B. mittels</p>
<pre style="margin-left: 40px;">
dialog.println("GCD is:" + x);</pre>
<p>
Der Algorithmus selbst bleibt fast identisch</p>
<pre style="margin-left: 40px;">
private int gcd(int a, int b) {
while (b != 0) {
if (a > b) {
a = a - b;
<span style="color:#0000ff;">drawRect(a, 0, b, b)</span>;
} else {
b = b - a;
<span style="color:#0000ff;">drawRect(0, b, a, a)</span>;
}
pause(1000);
}
return a;
}</pre>
<p>
Wir müssen lediglich noch die Methode <em>drawRect()</em> implementieren. Die zeichnet einfach ein GRect mit zufälliger Farbe an den vorgegebenen Koordinaten:</p>
<pre style="margin-left: 40px;">
private void drawRect(int a, int b, int w, int h) {
GRect rect = new GRect(a, b, w, h);
rect.setFilled(true);
rect.setFillColor(rgen.nextColor());
add(rect);
}</pre>
<p>
Gar nicht so schwer.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Pi.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 222px; float: right;" />Pi</h2>
<p>
Wie bereits angedeutet kann Pi einfach durch das Zeichnen von Punkten ermitteln. Das mag zwar nicht die schnellste Methode sein, sie lässt sich aber am einfachsten visualisieren. Wir schreiben ein GraphicsProgram mit drei Instanzvariablen:</p>
<pre style="margin-left: 40px;">
private RandomGenerator rgen = RandomGenerator.getInstance();
private int totalPoints = 0;
private int insidePoints = 0;</pre>
<p>
einen Zufallszahlengenerator, und zwei Zählern, einen für die Gesamtzahl der Punkte und einen für die Punkte die innerhalb des Viertelkreises liegen. In der <em>run()</em> Methode zeichnen wir dann jeweils einen Punkt, und berechnen nach jedem Mal Pi und geben es auf der Konsole aus:</p>
<pre style="margin-left: 40px;">
while (true) {
drawRandomPoint();
double pi = 4.0 * insidePoints / totalPoints;
System.out.println( "Pi = " + pi );
}</pre>
<p>
Die <em>drawRandomPoint()</em> Methode macht auch nicht besonders viel:</p>
<pre style="margin-left: 40px;">
private void drawRandomPoint() {
double x = rgen.nextDouble();
double y = rgen.nextDouble();
totalPoints++;
GRect point = new GRect(x*SIZE,SIZE-y*SIZE, 1,1);
if ( <span style="color:#0000ff;">( x*x+y*y ) < 1.0</span> ) {
insidePoints++;
point.setColor( Color.RED );
} else {
point.setColor( Color.BLUE );
}
add( point );
}</pre>
<p>
Wir holen uns zwei zufällige Werte, x und y, erhöhen unseren Punktezähler und generieren ein Punkt Objekt. Da es in der ACM Library keine Punkte gibt, nehmen wir einfach ein GRect, das eine Höhe und Breite von je eins hat. Geht auch. Der Trick ist, wie weiss ich ob ein Punkt nun innerhalb oder außerhalb des Viertelkreises ist? Falls wir das vergessen haben, schlagen wir das schnell in einem alten Mathebuch nach: Alle Punkte bei denen</p>
<pre style="margin-left: 40px;">
( x*x + y*y ) < 1.0</pre>
<p>
die sind innerhalb des Kreises. Und die malen wir rot an, die anderen blau. Funktioniert ganz gut. Falls man mehr über Pi wissen möchte, kann man sich das Buch eines Kollegen kaufen [7].</p>
<p>
.</p>
<h2>
<img alt="" src="images/Lehmer.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />Lehmer</h2>
<p>
Wie wir gerade gesehen haben können Zufallszahlen ganz praktisch sein. Auch letztes Semester haben wir schon häufiger einen Zufallszahlengenerator, den <em>RandomGenerator</em>, verwendet. Nur wie funktioniert der, wo kommen denn die Zufallszahlen her?</p>
<p>
Wenn man Glück hat, kommen die aus der Natur. Ein Computer hat jetzt aber recht wenig mit Natur zu tun, und für einen Computer ist es überraschend schwer an gute Zufallszahlen heranzukommen. Aber Gott sei Dank gab es den Herrn Lehmer und der hat sich da was überlegt, den Lehmer Algorithmus [8]:</p>
<pre style="margin-left: 40px;">
X_i+1 = ( a * X_i + c ) % m
</pre>
<p>
dabei ist '%' unser Freund der Modulo Operator. Der Lehmer Algorithmus erzeugt Pseudo-Zufallszahlen zwischen 0 und m-1, die linear kongruent sind, also gleichmäßig verteilt. Die Konstanten a, c und m müssen zwei Bedingungen erfüllen</p>
<pre style="margin-left: 40px;">
2 <= a < m und 0 <= c < m
</pre>
<p>
z.B., a=13, c=1, und m=16. Das erste x, also x_0, kann beliebig sein, idealerweise aber auch kleiner als m. Man nennt dieses erste x auch das <em>Seed</em>.</p>
<p>
Wenn wir den Algorithmus in Java übersetzen</p>
<pre style="margin-left: 40px;">
int a = 13;
int c = 1;
int m = 16;
int x = 3;
for (int i = 0; i < 20; i++) {
print(x + ",");
x = (a * x + c) % m;
}
</pre>
<p>
und mal ausprobieren, dann stellen wir etwas interessantes fest: die Zahlen wiederholen sich! Und zwar nach m Schritten. Das ist der Grund warum diese Zahlen auch Pseudo-Zufallszahlen nennt. Es stellt sich heraus, dass alle im Computer durch Algorithmen erzeugten Zufallszahlen immer Pseudo-Zufallszahlen sind.</p>
<p>
Kann man da was machen? Nein. Aber durch geschickte Wahl der Konstanten a, c und m kann man das Ganze erträglich machen.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Randomness.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 200px; float: right;" />Randomness</h2>
<p>
Was ist denn ein geschickte Wahl für der Konstanten a, c und m? Man kann jetzt Mathematik studieren (durchaus empfohlen) oder man liest in schlauen Büchern nach [9]. Wenn man relativ gute Pseudo-Zufallszahlen auf einem 32 bit Computer erzeugen will, dann sind folgende gute Werte:</p>
<ul>
<li>
wenn man für <em>m</em> eine Primzahl wählt, dann kann man <em>c = 0</em> setzen;</li>
<li>
die Primzahl <em>m</em> sollte möglichst groß sein, und wir haben Glück: <em>2^31 - 1</em> ist eine Primzahl;</li>
<li>
und die Mathematiker erzählen uns, dass <em>a = 7*7*7*7*7 = 16807</em> eine gute Wahl für <em>a</em> ist.</li>
</ul>
<p>
Diese Wahl nennt man auch den "Minimal Standard Random Number Generator". </p>
<p>
Schauen wir mal ob er was taugt, also ob er gut genug ist. Es stellt sich nämlich heraus, dass unser Auge relativ gut erkennen kann ob etwas zufällig ist oder nicht. Es braucht nur ein klein bischen Unterstützung. Als erstes implementiern wir unseren Lehmer Algorithmus, oder genauer den "Minimal Standard Random Number Generator" in Java:</p>
<pre style="margin-left: 40px;">
private long <span style="color:#0000ff;">a = 7 * 7;</span> // * 7 * 7 * 7; // use 7 or 7*7
private long m = 2147483647L;
private long x = System.currentTimeMillis();
public int nextInt() {
x = a * x % m;
return (int) x;
}</pre>
<p>
Für unsere Seed <em>x</em> verwenden wir einfach die Uhrzeit, damit bekommen wir jedes mal andere Zufallszahlen. Macht man echt so. Ist auch der Grund warum die NSA so einfach unsere Verschlüsselungen knacken kann.</p>
<p>
Die Methode <em>nextInt()</em> erzeugt Zufallszahlen zwischen 1 und 2^31 (-2). Wir benötigen aber sehr häufig Zahlen zwischen 0 und einer Obergrenze <em>n</em>:</p>
<pre style="margin-left: 40px;">
public int nextInt(int n) {
int z = nextInt();
return (int) (z % n);
}</pre>
<p>
und da ist er wieder unser Freund der Modulo Operator. </p>
<p>
Kommen wir zum Auge. Dafür schreiben wir ein GraphicsProgram in dessen <em>run()</em> Methode wir ein paar zufällige Punkte malen:</p>
<pre style="margin-left: 40px;">
for (int i = 0; i < 10000; i++) {
int x = nextInt(SIZE);
int y = nextInt(SIZE);
setPixel(x, y, Color.RED);
}</pre>
<p>
wobei <em>setPixel()</em> wieder wie oben beim Project Pi ein GRect mit einem Pixel Höhe und Breite malt.</p>
<p>
Wenn wir uns das Resultat ansehen, und <em>a</em> auf den Wert 7*7 gesetzten haben, dann sehen wir rote Streifen! Unser Auge sagt uns, das sind keine guten Zufallszahlen. Wählen wir aber für <em>a</em> den Wert den uns die Mathematiker nahelegen, also 7*7*7*7*7, dann können wir keine Streifen mehr erkennen. Keine Streifen, oder irgendwelche Muster im Allgemeinen, sind ein Zeichen für einen guten Zufallszahlengenerator.</p>
<p>
.</p>
<h2>
<img alt="" src="images/CreditCard.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />CreditCard</h2>
<p>
Wie weiss man ob man sich vertippt hat? Dafür gibt es Prüfsummen (checksum). Ein Beispiel ist der Luhn-Algorithmus, von dem deutsch-amerikanischen Informatiker Hans Peter Luhn [10], der z.B. bei Kreditkarten verwendet wird. </p>
<p>
Eine Kreditkarte besteht aus 16 Zahlen. Dabei sind die ersten 15 die eigentliche Nummer, die letzte Zahl ist aber die sogenannte Prüfziffer. Wie funktioniert der Luhn-Algorithmus?</p>
<ul>
<li>
Erst mal wird jede zweite Ziffer verdoppelt, beginnend bei der zweiten von rechts. wenn dieses Resultat größer als neun ist, wird neun abgezogen;</li>
<li>
dann werden alle Ziffern aufaddiert, also sowohl die nicht verdoppelten als auch die verdoppelten, wenn diese Summe modulo 10 die Null ergibt, ist alles in Ordnung.</li>
</ul>
<p>
Eine Implementierung in Java sieht wie folgt aus:</p>
<pre style="margin-left: 40px;">
private boolean checkCreditCardNumber(String creditNumber) {
int sum = 0;
int len = creditNumber.length();
for (int i = 0; i < len; i++) {
int x = creditNumber.charAt(i) - '0'; // turn char in to int
int y = x * (2 - (i + len) % 2); // multiply by two every other
if (y > 9) {
y -= 9;
}
sum += y;
}
return sum % 10 == 0;
}</pre>
<p>
Es ist interessant zu sehen wie die Anforderung "die zweite Ziffer von rechts verdoppeln" umgesetzt wurde:</p>
<pre style="margin-left: 40px;">
int y = x * (2 - (i + len) % 2);</pre>
<p>
Das muss man einfach mal auf Papier ausprobiern, und dann sieht man, dass das anscheinend funktioniert.</p>
<p>
.</p>
<h2>
<img alt="" src="images/ISBN.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 100px; float: right;" />ISBN</h2>
<p>
Ähnlich wie bei Kreditkarten gibt es auch bei Büchern die Internationale Standardbuchnummer (ISBN) anhand der man Bücher eindeutig identifizieren kann [11]. Auch bei dieser Nummer gibt ist die letzte Ziffer eine Prüfziffer. Der Algorithmus ist sogar noch einfacher als bei den Kreditkarten:</p>
<ul>
<li>
addiere jede Ziffer multipliziert mit ihrer Position;</li>
<li>
wenn das Resultat modulo 11 die Null ergibt stimmt die Nummer.</li>
</ul>
<p>
</p>
<p>
In Java wird daraus:</p>
<pre style="margin-left: 40px;">
char[] arr = isbnNumber.toCharArray();
for (int i = 0; i < 9; i++) {
t = arr[i] - '0';
s += t * (i + 1);
}</pre>
<p>
Eine kleine Ausnahme gibt es: die Prüfziffer könnte eine 10 sein, dann macht man einfach ein 'X' daraus, also 111111112X:</p>
<pre style="margin-left: 40px;">
if (arr[9] == 'X') {
s += 10 * 10;
} else {
t = arr[9] - '0';
s += t * 10;
}
if (s % 11 == 0) { ... }</pre>
<p>
.</p>
<h2>
<img alt="" src="images/Benford.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 150px; float: right;" />Benford's Law</h2>
<p>
Gerade haben wir gesehen wie man feststellen kann ob in Kreditkarten- oder ISBN Nummern ein Fehler ist. Dafür verwendet man einen Algorithmus. Kann man aber auch in anderen Daten Fehler finden? Ein interessantes Beispiel dafür ist das Benfordsche Gesetz [12]. Eigentlich hat es zuerst ein Herr Newcomb entdeckt, und deswegen nennt man es auch manchmal <em>Newcomb-Benford’s Law</em>. </p>
<p>
Es geht darum, dass es in empirischen Daten eine überraschende Regelmäßigkeit gibt mit der gewisse Ziffern auftreten, speziell die erste Ziffer. Naiv würde man erwarten, dass alle Ziffern gleich oft dran kommen, und für zufällig verteilte Daten ist das auch der Fall. Aber eben nicht für die meisten empirischen Daten. Die folgen nämlich sehr häufig der folgenden Verteilung:</p>
<pre style="margin-left: 40px;">
'1' 30,1 %
'2' 17,6 %
'3' 12,5 %
'4' 9,7 %
'5' 7,9 %
'6' 6,7 %
'7' 5,8 %
'8' 5,1 %
'9' 4,6 %</pre>
<p>
(Quelle [12]). D.h. 30 Prozent aller Zahlen in einem empirischen Datensatz beginnen mit der Ziffer '1'. Steuerfahnder verwenden diese Gesetzmäßigkeit um Steuerbetrug aufzudecken, und auch Wahlbetrug ist schon auf diese Art und Weise entlarvt worden.</p>
<p>
Im letzten Semester hatte wir schon einmal mit empirischen Daten zu tun und das waren Aktienkurse. Im Prinzip können wir die Klasse <em>StockDataBase</em> unverändert verwenden. Dann sind in der <em>stockDB</em> HashMap die ganzen Aktienkurse gespeichert. Die gehen wir dann einen nach dem anderen durch und zählen wie häufig sie mit einer bestimmten Ziffer beginnen. Das Zählen machen wir in dem Array <em>counts</em>.</p>
<pre style="margin-left: 40px;">
public double[] analyze() {
double total = 0;
double[] counts = new double[10];
for (String stock : stockDB.keySet()) {
StockEntry ent = stockDB.get(stock);
List<Double> prices = ent.getPrices();
for (int i = 0; i < prices.size(); i++) {
double price = prices.get(i);
char c = String.valueOf(price).charAt(0);
if (Character.isDigit(c)) {
counts[c - '0']++;
total++;
}
}
}
return counts;
}</pre>
<p>
Danach sollten wir noch die Daten in Prozent umrechnen, damit wir sie mit dem Benfordsche Gesetz vergleichen können. Und interessanterweise scheinen auch Aktienkurse grob dem Benfordsche Gesetz zu folgen. Ob der Unterschied vielleicht auf Insider-Trading hindeutet?</p>
<p>
Das Benfordsche Gesetz ist natürlich kein Algorithmus. Deswegen stellt sich natürlich die Frage gehört das in dieses Buch. Die Frage darf jeder für sich selbst beantworten. Auf den Webseiten zum Buch von Sedgewick und Wayne finden sich noch eine ganze Menge anderer Datensätze über die man ähnliche Analysen laufen lassen könnte [13].</p>
<p>
.</p>
<hr />
<h1>
Challenges</h1>
<p>
.</p>
<h2>
<img alt="" src="images/mandelBrot.png" style="margin-left: 10px; margin-right: 10px; width: 200px; height: 222px; float: right;" />Mandelbrot</h2>
<p>
Die Apfelmännchen sind nach dem französischen Mathematiker Benoît Mandelbrot benannt. Es handelt sich dabei um sogenannte Fraktale, aber die meisten Leute finden sie einfach nur hübsch [14]. </p>
<p>
Die mathematische Gleichung die hinter der Mandelbrot Menge liegt ist sehr einfach:</p>
<pre>
z_n+1 = z_n * z_n + c</pre>
<p>
dabei sind <em>z</em> und <em>c</em> komplexe Zahlen. Es handelt sich hier um eine Iteration, d.h. wenn wir <em>z_n</em> kennen, dann können wir <em>z_n+1</em> ausrechnen. Die Anfangsbedingungen lauten, dass <em>z_0</em> gleich null sein soll und <em>c</em> ist der Punkt in der komplexen Ebene für den die Farbe ausgerechnet werden soll. Also wenn wir in x- und y-Koordinaten denken, dann ist </p>
<pre>
c = x + i y</pre>
<p>
die Anfangsbedingung. Alles was noch nötig ist, ist das Abbruchkriterium, wann sollen wir mit der Iteration aufhören? Entweder wenn z*z >= 4 ist oder wenn die Anzahl der Iterationen größer als ein maximal Wert ist:</p>
<pre>
while ( (x*x + y*y < 4) && (iteration < max_iteration) ) {
...
iteration++;
}</pre>
<p>
Damit das Ganze dann hübsch aussieht, nehmen wir die Anzahl der Iterationen und kodieren sie in Farbe:</p>
<pre>
int color = RAINBOW_COLORS[iteration % RAINBOW_NR_OF_COLORS];</pre>
<p>
Dabei ist <em>RAINBOW_COLORS</em> ein Farbarray, das wir beliebig initialisieren können. Zu guter Letzt brauchen wir noch eine <em>setPixel()</em> Methode, die es in der ACM Graphics Bibliothek eigentlich gar nicht gibt. Wir behelfen uns damit, dass wir kleine GRects zeichnen:</p>
<pre>
private void setPixel(double x, double y, Color color) {
int i = (int) (((x - xMin) * WIDTH) / (xMax - xMin));
int j = (int) (((y - yMin) * HEIGHT) / (yMax - yMin));
GRect r = new GRect(1, 1);
r.setColor(color);
add(r, i, j);
}
</pre>
<p>
Das ist nicht gerade die schnellst und effektivste Art, aber sie funktioniert.</p>
<p>
.</p>
<h2>
RandomGenerator</h2>
<p>
Letztes Semester haben wir häufig die Klasse RandomGenerator der ACM Bibliothek benutzt. Inzwischen können wir diese Klasse selbst implementieren. Dazu benutzen wir einfach Lehmer's Algorithmus mit den Konstanten wie sie z.B. in Referenz [8] empfohlen werden:</p>
<pre style="margin-left: 40px;">
public final class RandomGenerator {
private int seed = 1;
private static final int a = 16807; // = 7*7*7*7*7
private static final int m = 2147483647; // = 2^31 -1
private static final int q = 127773; // = m div a
private static final int r = 2836; // = m mod a
public RandomGenerator() {
}
/**
* @return a random number between 0 and 2147483647
*/
public int nextInt() {
seed = a * (seed % q) - r * (seed / q);
return seed;
}
/**
* sets the initial seed
*
* @param s
* a good idea is a changing value, such as the time, ideally it
* is a truely random number.
*/
public void setSeed(int s) {
if ((s < 1) || (s >= m)) {
throw new IllegalArgumentException("invalid seed");
}
seed = s;
}
}
</pre>
<p>
Was jetzt noch zu tun bleibt sind die übrigen Methoden der RandomGenerator Klasse zu implementieren, z.B.:</p>
<ul>
<li>
<strong>int nextInt(int n):</strong> gibt eine zufällige Ganzzahl zwischen 0 <= r < n zurück;</li>
<li>
<strong>int nextInt(int low, int high):</strong> gibt eine zufällige Ganzzahl zwischen low <= r < high zurück;</li>
<li>
<strong>boolean nextBoolean():</strong> gibt einen zufällige Boolean mit einer 50/50 Wahrscheinlichkeit von true oder false zurück;</li>
<li>
<strong>double nextDouble():</strong> gibt eine zufällige Gleitkommazahl zwischen 0 <= r < 1 zurück;</li>
<li>
<strong>double nextDouble(double low, double high):</strong> gibt eine zufällige Gleitkommazahl zwischen low <= r < high zurück;</li>
<li>
<strong>Color nextColor():</strong> gibt eine zufällige Farbe zurück.</li>
</ul>
<p>
.</p>
<hr />
<h1>
Research</h1>
<p>
Natürlich können wir in diesem Buch nur die Oberfläche streifen, aber es gibt einige Themen die man noch vertiefen könnte.</p>
<p>
.</p>
<h2>
List of Algorithms</h2>
<p>
Um eine Vorstellung davon zu bekommen, wie viele Algorithmen es da draußen gibt, werfen wir einen Blick auf die Sammlung von Algorithmen, die in der Wikipedia gelistet werden [1].</p>
<p>
.</p>
<h2>
Entscheidungsproblem</h2>
<p>
David Hilbert's <em>Entscheidungsproblem</em> und Alan Turing's <em>Turing Machine</em> sind zwei Themen über die wir mal recherchieren sollten.</p>
<p>
.</p>
<h2>
Luhn vs ISBN</h2>
<p>
Wenn wir den Luhn Algorithmus mit dem ISBN Algorithmus vergleichen, stellt sich die Frage: Welcher ist besser? Welcher erkennt mehr Fehler, bzw. häufiger auftretende Fehler?</p>
<p>
.</p>
<hr />
<h1>
Fragen</h1>
<ol>
<li>
Wer hat den ersten Algorithmus geschrieben?<br />
</li>
<li>
Beschreiben Sie in Ihren eigenen Worten, wie der Größte Gemeinsame Teiler Algorithmus funktioniert.<br />
</li>
<li>
Nennen Sie zwei der wichtigsten Errungenschaften von Muhammad ibn Musa al-Chwarizmi.<br />
</li>
<li>
Was ist der Unterschied zwischen einer echten Zufallszahl und einer Pseudozufallszahl?<br />
</li>
<li>
Wie kann man die Kreiszahl Pi mit zufälligen Zahlen berechnen?<br />
</li>
<li>
Beschreiben Sie die grafische Version von Euclid's Algorithmus.<br />
</li>
<li>
Wofür wird Lehmer's Algorithmus verwendet?<br />
</li>
<li>
Wie können Sie grafisch bestimmen, ob ein Zufallszahlengenerator schlecht ist?</li>
</ol>
<p>
.</p>
<hr />
<h1>
Referenzen</h1>
<p>
Anbei finden sich die Referenzen zum ersten Kapitel.</p>
<p>
[1] List of algorithms, <a href="http://en.wikipedia.org/wiki/List_of_algorithms">en.wikipedia.org/wiki/List_of_algorithms</a></p>
<p>
[2] Algorithm, <a href="http://en.wikipedia.org/wiki/Algorithm">en.wikipedia.org/wiki/Algorithm</a></p>
<p>
[3] Muḥammad ibn Mūsā al-Khwārizmī, <a href="https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi">https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi</a></p>
<p>
[4] Longest common substring problem, <a href="https://en.wikipedia.org/wiki/Longest_common_substring_problem">https://en.wikipedia.org/wiki/Longest_common_substring_problem</a></p>
<p>
[5] Euclidean algorithm, <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm">https://en.wikipedia.org/wiki/Euclidean_algorithm</a></p>
<p>
[6] Conways Spiel des Lebens, <a href="https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens">https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens</a></p>
<p>
[7] Pi: Algorithmen, Computer, Arithmetik, Jörg Arndt, Christoph Haenel</p>
<p>
[8] Lehmer random number generator, <a href="https://en.wikipedia.org/wiki/Lehmer_random_number_generator">https://en.wikipedia.org/wiki/Lehmer_random_number_generator</a></p>
<p>
[9] Generating Random Numbers in Data Structures and Algorithms, Bruno R. Preiss, <a href="http://www.brpreiss.com/books/opus5/html/page465.html#33557">http://www.brpreiss.com/books/opus5/html/page465.html#33557</a></p>
<p>
[10] Luhn-Algorithmus, <a href="https://de.wikipedia.org/wiki/Luhn-Algorithmus">https://de.wikipedia.org/wiki/Luhn-Algorithmus</a></p>
<p>
[11] International Standard Book Number, <a href="https://en.wikipedia.org/wiki/International_Standard_Book_Number#ISBN-10_check_digits">https://en.wikipedia.org/wiki/International_Standard_Book_Number#ISBN-10_check_digits</a></p>
<p>
[12] Benfordsches Gesetz, <a href="https://de.wikipedia.org/wiki/Benfordsches_Gesetz">https://de.wikipedia.org/wiki/Benfordsches_Gesetz</a></p>
<p>
[13] Real-World Data Sets, Robert Sedgewick and Kevin Wayne, <a href="http://introcs.cs.princeton.edu/java/data/">http://introcs.cs.princeton.edu/java/data/</a></p>
<p>
[14] Mandelbrot-Menge, <a href="https://de.wikipedia.org/wiki/Mandelbrot-Menge">https://de.wikipedia.org/wiki/Mandelbrot-Menge</a></p>
<p>
.</p>
<p class="footer">
Copyright © 2016-2021 <a href="http://www.lano.de">Ralph P. Lano</a>. All rights reserved.
</p>
</div>
</center>
</div>
</body>
</html>