Grundlagen der funktionsorientierten Programmierung mit SCHEME/Binäre Suche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5bb8676b26c24" hidden>
(define quotient
(lambda (m n)
(floor (/ m n))))
(define remainder quotient)
(define numeingabe
(lambda (max)
(let ([eingabe (inputDialog "Deine Zahl:")])
(if (equal? eingabe 'null)
#f
(let ([anzahl (string->number eingabe)])
(if (or (equal? anzahl +nan.0) (< anzahl 0) (> anzahl max))
(numeingabe max)
anzahl))))))
(define spielerraten
(lambda (max)
(letrec
([zufallszahl
(lambda (max)
(+ 1 (random max)))]
[suche
(lambda (z anzahl)
(let ([zahl (numeingabe max)])
(cond
[(not zahl) 'ok]
[(= z zahl)
(showMessage (string-append "Du hast die Zahl " (number->string zahl)
" mit " (number->string anzahl) " Versuch(en) erraten!"))
'ok]
[(< z zahl)
(showMessage (string-append "Die Zahl " (number->string zahl) " ist zu groß!"))
(suche z (+ 1 anzahl))]
[else
(showMessage (string-append "Die Zahl " (number->string zahl) " ist zu klein!"))
(suche z (+ 1 anzahl))])))])
(suche (zufallszahl max) 1))))
(define computerraten-lsg
(lambda (zahl max)
(letrec
([suche
(lambda (li z re)
(let ([mi (floor (/ (+ li re) 2))])
(cond
[(= z mi) (list z)]
[(< z mi) (cons mi (suche li z mi))]
[else
(cons mi (suche mi z re))])))])
(suche 1 zahl (+ max 1)))))
(define last
(lambda (ls)
(car (reverse ls))))
(define listequal?
(lambda (ls1 ls2)
(cond
[(and (null? ls1) (null? ls2)) #t]
[(or (null? ls1) (null? ls2)) #f]
[(and (list? (car ls1)) (list? (car ls1)))
(and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]
[else
(and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))
</code>
== Raten einer Zahl ==
Wir kennen das einfache Spiel zum Raten einer Zahl $z$ im Intervall $1 \le z \le max$:<br />
Aus einem zuvor vereinbarten Intervall denkt sich ein Spieler eine Zahl, die sein Mitspieler erraten muss. Nach jedem Versuch erhält der Mitspieler den Hinweis, ob seine vermutete Zahl kleiner bzw. größer als die erdachte Zahl ist oder sogar mit ihr übereinstimmt. Die erdachte Zahl soll so mit einem Minimum an Versuchen erraten werden.<br />
Zunächst spielen wir gegen den Computer und erraten eine Zufallszahl:
<run id="4e750a0f86217">
(spielerraten 100)
</run>
== Computerraten einer Zahl ==
Natürlich ist ein Erraten der Zahl durch sequenzielle Suche möglich. Allerdings wissen wir, dass die Suche durch Intervallhalbierung wesentlich effizienter ist.<br />
Das Raten einer Zahl soll nun der Computer übernehmen. Dazu wollen wir selbstverständlich die ''effizientere'' Spielstrategie umsetzen:
(computerraten 47 100) --> (51 26 38 44 47)
Die Prozedur <tt>computerraten</tt> soll eine Liste mit allen "Versuchszahlen" zurückgeben. Das letzte Listenelement entspricht der zu erratenden Zahl, die Länge der Liste der Anzahl der benötigten Versuche.
<code id="4bbc334a0c1ee">
(define computerraten
(lambda (zahl max)
...))
</code>
<check>
(let* ([z (+ 1 (random 1000))] [ls (computerraten z 1000)] [ls-lsg (computerraten-lsg z 1000)])
(and (eqv? (last ls) (last ls-lsg)) (< (- (length ls) (length ls-lsg)) 3)))
</check>
<run id="4bbc334a0d178">
(computerraten 47 100)
</run>
Diese Strategie scheint tatsächlich schnell zum Erfolg zu führen, da in jedem weiteren Rekursionsschritt die Suche auf das halbe Suchintervall reduziert wird.<br />
Man bezeichnet einen derartigen Suchalgorithmus als ''binäre Suche''.<br />
Wir testen unseren Algorithmus mit Zufallszahlen:
<code id="4e750a0f8609f">
(define zufallszahl
(lambda (max)
(+ 1 (random max))))
</code>
<run id="4e750a0f8629d">
(computerraten (zufallszahl 100000) 100000)
</run>
== Effizienz beim Raten einer Zahl ==
Wie viele Versuche sind mit binärer Suche im Mittel in einem vorgegebenen Intervall notwendig?<br />
Auch hier wollen wir in grober Näherung davon ausgehen, dass jeder Versuch genau einem "Zeittakt" entspricht.<br />
=== Empirische Effizienzuntersuchungen ===
Nun können wir wieder empirische (empirisch: aus der Erfahung oder Beobachtung) Effizienzuntersuchungen vornehmen.<br />
Dazu definieren wir zweckmäßigerweise eine Prozedur <tt>computerraten-mehrfach</tt>, die im Gegensatz zu <tt>computerraten</tt> die Anzahl der benötigten Versuche als arithmetisches Mittel mehrerer Versuche zurückgibt.<br />
Dabei wird jeweils eine Zufallszahl aus dem mit <tt>max</tt> begrenzten Intervall "erraten":
<code id="5bb70d7251570">
(define computerraten-mehrfach
(lambda (max anzahl)
(letrec
([summe
(lambda (n)
(if (= n 0)
0
(+ (length (computerraten (zufallszahl max) max)) (summe (- n 1)))))])
(/ (summe anzahl) anzahl))))
</code>
<run id="4bb9b3a64d8bf">
(computerraten-mehrfach 1000 10)
</run>
=== Experimente ===
Wie bei der sequenziellen Suche automatisieren wir das Raten einer Zahl in mehreren Intervallen:
<code id="4bb9b3a64a9df">
(define experiment
(lambda (min max schrittweite anzahl)
(if (> min max)
()
(append (experiment min (- max schrittweite) schrittweite anzahl)
(list (computerraten-mehrfach max anzahl))))))
</code>
<run id="5bb70d7251616">
(experiment 500 10000 500 100)
</run>
Die Untersuchungsergebnisse werden auch hier in einem Balkendigramm veranschaulicht:<br />
<canvas w="400" h="300"></canvas>
<code id="4e750a0f8612c" hidden>
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(define balken
(lambda (hoehe breite)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite)))
(define balkendiagramm
(lambda (ls)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (floor (* (/ (car ls) (- max min)) maxhoehe)) (floor breite))
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
<run id="5bb70d7251691">
(balkendiagramm (experiment 200 10000 200 100))
</run>
'''Ergebnisse:'''<br />
<ul>
<li>
Die binäre Suche führt im Vergleich zur sequenziellen Suche wesentlich schneller zum Erfolg.
</li>
<li>
Der Zeitaufwand wächst bei zunehmender Problemgröße (Suchintervall) langsamer an.<br />
Offensichtlich ist dieser Algorithmus bei umfassender Problemgröße sehr effizient.
</li>
</ul>
== Aufgaben ==
<ol>
<li>
Ermitteln Sie für das Raten einer Zahl die mögliche funktionale Abhängigkeit
$\mbox{Zeitaufwand} = f(\mbox{Problemgröße)}$.<br />
Testen Sie dazu geeignete Regressionsmodelle mit der Tabellenkalkulation oder einem grafikfähigen Taschenrechner.
</li>
<li>
Die Nullstellensuche in der [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Kurvendiskussion|Kurvendiskussion]] ist eine typische Anwendung der binären Suche.<br />
Verallgemeinern Sie das Raten einer Zahl und die Nullstellensuche zu einer Problemklasse, auf die eine binäre Suche anwendbar ist.
</li>
</ol>
== Zum Weiterarbeiten ==
=== Extremwertsuche nach dem Verfahren des Goldenen Schnitts ===
Die binäre Suche muss nicht zwingend zur Intervallhalbierung führen.<br />
Ein interessanter Algorithmus ist die [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Extremwertsuche nach dem Verfahren des Goldenen Schnitts|Extremwertsuche nach dem Verfahren des Goldenen Schnitts]]. Dabei überlappen sich die möglichen Suchintervalle.<br />
Wir betrachten das Verfahren zunächst für die Suche eines lokalen Minimums:
<table border="0">
<tr>
<td align="center">
[[Bild:Extremwert.gif]]<br />
Animation: Minimumsuche nach dem Verfahren des Goldenen Schnitts
</td>
<td>'''Algorithmus''' (Minimumsuche):
<ul>
<li>Lege ein Suchintervall durch zwei äußere Intervallgrenzen fest.</li>
<li>Zerlege dieses Suchintervall durch einen ''zweimaligen'' Goldenen Schnitt in 3 Teilintervalle.</li>
<li>Berechne die Funktionswerte an beiden Schnittstellen.</li>
<li>Das neue Suchintervall wird aus der Schnittstelle mit dem größeren der beiden Funktionswerte und einer der äußeren Intervallgrenzen derart gebildet, dass die Schnittstelle mit dem ''kleineren'' Funktionswert ''eingeschlossen'' wird.</li>
<li>Führe im neuen Suchintervall den Goldener Schnitt durch, der wieder zu 3 Teilintervallen führt.</li>
<li>Wiederhole das Verfahren solange, bis das Suchintervall einer hinreichend kleinen ε-Umgebung genügt.</li>
<li>Der Funktionswert eines Arguments aus dieser ε-Umgebung entspricht dem gesuchten Minimum.</li>
</ul>
</td>
</tr>
</table>
Implementieren Sie den Algorithmus zur binären Suche lokaler Extremwerte (Minima <u>und</u> Maxima!) einer beliebigen Funktion.<br />
Denken Sie dabei auch an das Konzept der ''Prozeduren höherer Ordnung''!<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Extremwertsuche nach dem Verfahren des Goldenen Schnitts|Problemlösung]].