Aufgaben - TuH2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
==Aufgaben zur Binären Suche==
Ziel der folgenden Aufgaben ist es, eine Empirische Aufwandsanalyse der Binären Suche durchzuführen.
===Aufgabe (a) - Durchrechnen ===
'''Gegeben''' sei folgende Liste:
<!-- Liste -->
'''Gesucht''' ist das Element 13
Verdeutlichen sie sich die Arbeitsweise der binären Suche.
''Zeichnen sie den Suchbaum!''
===Aufgabe (b) - Empirische Analyse ===
Die modifizierte Variante der Binären Suche in Scheme bietet mit ihrem Zähler die Möglichkeit für eine Empirische Analyse.
Führen Sie eine empirische Aufwandsanalyse durch. Um ausreichend Testfälle zu Produzieren, stehen die Prozeduren ''zzls'' für die Generierung einer Zufallszahlenliste sowie ''mv-mergesort'' (Bekannt aus '''Teile und Herrsche 1''') zum Sortieren der generierten Liste zur Verfügung.
Führen Sie sie empirische Aufwandsanalyse ausserdem mit der Sequenziellen Suche durch, um einen Qualitätiven Vergleich anstellen zu können.
''zzls - ZufallsZahlenListe''
<code>
;zzls für ZufallsZahlenListe. Generiert eine Liste mit n paarweise verschiedenen Ganzen Zahlen zwischen a und b.
;Beispielaufruf:
;>(zzls 10 100 1000) ; Zufallszahlenliste mit 1000 Zufallszahlen zwischen 10 und 100
(define zzls
(lambda (a b n)
(if (= n 0)
(list)
(let ((x (random b)))
(if (> x a)
(append (list x)(zzls a b (- n 1)))
(zzls a b n))))))
</code>
Aufrufbeispiel
<eval>(zzls 0 50 20)</eval>
HINWEIS! Offensichtlich beherrscht die SchemeImplementation im Wiki nicht die Prozedur (random x). Deshalb erscheint hier ein Fehler.
In einer Lokalen DrScheme-Umgebung sollte der Quellcode funktionieren, wenn als Sprache "Kombo" ausgewählt wird.
Für die Übung haben wir einige Beispiellisten vorgegeben, die Sie benutzen können.
Vorgefertigte, unsortierte Listen
<code>
(define u_liste1 '(37 1 26 29 9 3 44 4 24 9 20 11 16 30 16 48 39 28 25 46))
(define u_liste2 '(21 34 27 20 3 5 28 37 14 5 28 6 39 3 13 32 8 30 13 36))
(define u_liste3 '(14 27 16 30 22 5 10 30 13 47 36 12 44 43 2 45 11 49 3 46))
(define u_liste4 '(13 25 17 37 39 48 21 36 18 45 9 38 36 12 8 27 46 42 15 44))
(define u_liste5 '(19 22 9 49 28 26 46 9 27 31 8 19 36 48 36 49 14 38 9 8))
</code>
Diese Listen müssen für die Binäre Suche in Sortierter Form vorliegen. Zum Sortieren verwenden wir die Prozedur ''mv-mergesort'' welche in der Vorlesung '''Teile und Herrsche 1''' behandelt wurde.
<code hidden>
(define teillisten2
(lambda (ls)
(let ((k (floor (/ (length ls) 2))))
(letrec
((helfer
(lambda (ls i)
(if (= i 0)
(values '() ls)
(call-with-values
(lambda ()(helfer (cdr ls)(- i 1)))
(lambda (links rechts)
(values (cons (car ls) links) rechts)))))))
(helfer ls k)))))
(define verbinden
(lambda (lls rls)
(cond
((null? lls) rls)
((null? rls) lls)
(else
(let ((x (car lls))(y (car rls)))
(if (< x y)
(cons x (verbinden (cdr lls) rls))
(cons y (verbinden lls (cdr rls)))))))))
(define mv-mergesort
(lambda (ls)
(if (or (null? ls)(null? (cdr ls)))
ls
(call-with-values
(lambda () (teillisten2 ls))
(lambda (ls1 ls2)
(verbinden
(mv-mergesort ls1)
(mv-mergesort ls2)))))))
</code>
Die sortierten Listen
<code>
(define liste1 (mv-mergesort u_liste1))
(define liste2 (mv-mergesort u_liste2))
(define liste3 (mv-mergesort u_liste3))
(define liste4 (mv-mergesort u_liste4))
(define liste5 (mv-mergesort u_liste5))
</code>
Überprüfe, ob die Liste korrekt Sortiert wurde.
<eval>liste1</eval>
<code hidden>
(define binhelfer
(lambda (x ls)
(call-with-values
(lambda () (teillisten2 ls))
(lambda (lls rls)
(cond
((null? rls) "Schluessel nicht enthalten")
((= x (car rls)) (and (and (set! index (+ index (length lls)))
(and (string-append "Schluessel gefunden an Stelle "
(number->string index) ". Anzahl Rekursionen: "
(number->string calls))))))
((< x (car rls))
(if (null? lls)
"Schluessel nicht enthalten"
(and (set! calls(+ calls 1))
(binhelfer x lls))))
(else
(if (null? (cdr rls))
(string-append "Schluessel nicht enthalten. Anzahl Rekursionen: " (number->string calls))
(and (set! calls (+ calls 1))
(and (set! index (+ index (length lls)))(binhelfer x rls))))))))))
(define index 0)
(define calls 0)
(define binaersuche2
(lambda (x ls)
(set! index 0)
(set! calls 0)
(binhelfer x ls)))
</code>
Somit haben wir alle Werkzeuge zur Hand, um die Empirische Analyse durchzuführen und den Aufwand der Binären Suche mit dem der Sequenziellen Suche zu vergleichen
Beispielaufruf Binaersuche:
<eval>(binaersuche2 44 liste1)</eval>
<code hidden>
(define seqsuche
(lambda (x ls)
(cond
((null? ls) "Schluessel nicht enthalten.")
((= x (car ls)) (string-append "Schluessel gefunden an der Stelle " (number->string calls) ". Anzahl Rekursionen " (number->string calls)))
((< (car ls) x)(set! calls(+ calls 1))(seqsuche x (cdr ls)))
(else "Schluessel nicht enthalten."))))
</code>
Beispielaufruf Sequenzielle Suche:
<eval>(seqsuche 44 liste1)</eval>
Von Interesse sind für die Analyse die Anzahl der Rekursionsschritte. Führen Sie nun die Aufwandsanalyse mit geeigneten Werten durch und fassen Sie Ihre Ergebnisse zusammen.
<code>
(63
66
99
107
115
133
175
196
254
273
286
312
316
321
334
353
376
387
423
428
469
469
485
498
507
530
556
578
609
613
697
779
858
866
871
883
896
912
941
952
999
1007
1051
1116
1140
1167
1196
1206
1220
1221
1256
1257
1274
1291
1312
1345
1368
1389
1396
1406
1430
1440
1448
1451
1458
1464
1505
1536
1583
1625
1631
1638
1644
1676
1693
1821
1834
1894
1899
1924
1959
1963
2013
2039
2066
2067
2083
2084
2188
2223
2265
2286
2302
2388
2390
2485
2485
2510
2538
2596
2608
2613
2624
2639
2642
2643
2716
2739
2740
2749
2759
2796
2802
2812
2812
2816
2867
2939
2940
2952
3019
3024
3057
3072
3085
3101
3119
3157
3163
3177
3192
3253
3257
3285
3325
3327
3336
3336
3353
3355
3365
3366
3405
3411
3472
3473
3474
3504
3536
3548
3569
3577
3589
3668
3771
3784
3804
3829
3850
3869
3869
3879
3890
3898
3936
3948
3949
3950
3981
4012
4047
4083
4121
4154
4166
4202
4205
4211
4227
4234
4245
4276
4276
4287
4315
4329
4329
4368
4381
4410
4458
4493
4513
4519
4537
4574
4577
4594
4609
4609
4622
4646
4649
4657
4660
4662
4668
4672
4678
4714
4734
4783
4786
4798
4828
4832
4836
4862
4871
4878
4928
4936
4948
4991
4996
5003
5050
5075
5094
5117
5121
5125
5163
5184
5184
5187
5189
5223
5225
5268
5281
5316
5352
5418
5423
5450
5460
5484
5488
5499
5519
5529
5532
5532
5557
5563
5573
5582
5589
5628
5661
5664
5672
5691
5693
5752
5766
5792
5805
5837
5845
5894
5901
5928
5929
5942
5950
5954
5961
5968
5974
5978
5994
5998
6002
6022
6030
6031
6033
6059
6089
6091
6117
6145
6162
6171
6197
6202
6276
6286
6286
6296
6310
6347
6367
6367
6369
6374
6377
6394
6478
6492
6497
6552
6565
6569
6596
6618
6651
6653
6683
6719
6741
6748
6755
6761
6803
6819
6831
6833
6870
6892
6902
6911
6929
6990
7027
7030
7045
7057
7069
7076
7085
7112
7152
7152
7192
7196
7196
7245
7271
7279
7282
7283
7284
7311
7319
7325
7326
7339
7369
7383
7390
7410
7431
7432
7445
7458
7463
7493
7496
7527
7530
7540
7542
7582
7614
7628
7632
7634
7669
7699
7722
7730
7760
7784
7801
7827
7846
7886
7915
7954
7961
7979
7995
7996
8024
8028
8042
8061
8068
8098
8118
8122
8127
8159
8203
8227
8236
8239
8248
8252
8256
8270
8283
8294
8345
8354
8373
8377
8417
8432
8449
8501
8518
8538
8539
8556
8639
8655
8657
8663
8664
8670
8700
8701
8720
8745
8764
8765
8794
8797
8818
8836
8863
8881
8881
8896
8900
8916
8933
8936
8960
8960
8960
8985
9078
9162
9183
9224
9231
9265
9272
9277
9293
9315
9336
9354
9363
9365
9370
9372
9400
9414
9437
9442
9451
9472
9480
9483
9513
9526
9536
9551
9617
9624
9673
9787
9810
9829
9908
9927
9936
9940
9959
9964
9965
9966
9987
9989)</code>
===Aufgabe (c) - Modifikation der Binaeren Suche ===
Auf der Hauptseite wurde schon angemerkt, dass die Binäre Suche zwar im Prinzip Logarithmischen Aufwand besitzt, unsere Scheme-Implementation dies jedoch nicht erfüllt. Machen Sie sich klar, warum dies so ist. Betrachten Sie dazu auch den Quellcode der Prozedur ''teillisten2''
<code>
(define teillisten2
(lambda (ls)
(let ((k (floor (/ (length ls) 2))))
(letrec
((helfer
(lambda (ls i)
(if (= i 0)
(values '() ls)
(call-with-values
(lambda ()(helfer (cdr ls)(- i 1)))
(lambda (links rechts)
(values (cons (car ls) links) rechts)))))))
(helfer ls k)))))
</code>
Überlegen Sie sich eine Lösung für dieses Problem. Wie könnte man die Binäre Suche umgestalten? Ziehen Sie die Möglichkeiten von Vectoren in Scheme in Betracht.
Scheme stellt unter anderem diese Sprachelemente zur Benutzung von Vectoren bereit:
'''<tt>vector</tt>''': Definiert einen Vektor
<eval>(define v (vector 1 2 3 4 5 6 7 8))
v</eval>
'''<tt>vector?</tt>''': Überprüft, ob es sich um einen Vektor handelt
<eval>(vector? v)</eval>
'''<tt>vector-length</tt>''': gibt die Länge des Vektors zurück
<eval>(vector-length v)</eval>
'''<tt>vector-ref</tt>''': gibt das Element an einer bestimmten Stelle zurück
<eval>(vector-ref v 4)</eval>
'''<tt>vector->list</tt>''': Wandelt einen Vektor in eine Liste um
<eval>(define liste (vector->list v))
liste</eval>
'''<tt>list->vektor</tt>''': Wandelt eine Liste in einen Vektor um
<eval>(define v2 (list->vector liste))
v2</eval>
Genauere Erklärungen und ein paar mehr Sprachelemente finden Sie z.B. [http://www.cs.grinnell.edu/~stone/courses/scheme/spring-2000/vectors.xhtml HIER]
Versuchen Sie nun eine verbesserte Binäre Suche zu Implementieren. Sie können dafür diesen EVAL-Blog verwenden:
<eval>
;verbesserte Binaere Suche
</eval>
Eine mögliche Lösung finden Sie auf der Lösungsseite
==Aufgaben zum Karatsuba Algorithmus==
===Aufgabe 1===
Multiplizieren sie folgende Werte mit Hilfe Karatsubas Verfahren.
<math>
\begin{array}{lcc}
12 & \text{und} & 45 \\
4536 & \text{und} & 6734 \\
36727 & \text{und} & 345
\end{array}
</math>
===Aufgabe 2 - Analyse der Schulbuchmethode===
Tip:
Man sollte damit Beginnen sich zu überlegen aus welchen Operationen die Multiplikation zweier n-stelliger Zahlen besteht.
Dabei hilft mal ein Beispiel zu rechnen. Man erkennt eine bestimmte Anzahl von Multplikationen und Additionen! :-)
==weitere Aufgaben==
==Lösungen==
Damits nicht gleich ins Auge fällt haben wir die Lösungen auf eine seperate Seite gepackt!
Die findet ihr hier: [[Lösungen - TuH2L]]