Grundlagen der funktionsorientierten Programmierung mit SCHEME/Sequenzielle Suche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
== Zufallszahlen ==
Wir haben bereits Zufallszahlen in [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Prozeduren mit Zeichenketten und Listen|Prozeduren mit Zeichenketten und Listen]] implementiert. Dabei wurde folgende Syntax genutzt:
<run id="5bb66765ca8d6">
(random 100)
</run>
Zur Erinnerung: <tt>(random <max>)</tt> gibt eine Zufallszahl $z$ zurück mit $0 \le z < max$.<br />
Vervollständigen Sie die nachfolgende nullstellige Prozedur, mit der das Würfeln einer Augenzahl $z$ mit $1 \le z \le 6$ simuliert werden kann:
<code id="5bb66765ca5b6">
(define wuerfelzahl
(lambda ()
...))
</code>
<code id="5bb66765ca65f" hidden>
(define wuerfelzahl?
(lambda (proz anz)
(letrec
([element?
(lambda (ls el)
(cond
[(null? ls) #f]
[(= (car ls) el) #t]
[else (element? (cdr ls) el)]))]
[sammeln
(lambda (ls anz)
(if (= anz 0)
ls
(let ([z (apply proz ())])
(case z
[(1 2 3 4 5 6)
(if (element? ls z)
(sammeln ls (- anz 1))
(sammeln (cons z ls) (- anz 1)))]
[else #f]))))])
(let ([ergebnis (sammeln () anz)])
(and ergebnis (= (length ergebnis) 6))))))
</code>
<check>
(wuerfelzahl? wuerfelzahl 100)
</check>
<run id="5bb66765ca948">
(wuerfelzahl)
</run>
== Zufallslisten ==
Nun können wir Listen mit Zufallszahlen generieren, deren Elemente im Intervall $1 \le z \le max$ liegen sollen. Vervollständigen Sie dazu die Prozedur <tt>zufallsliste</tt>.
<code id="5bb66765ca6e4">
(define zufallszahl
(lambda (max)
(+ 1 (random max))))
(define zufallsliste
(lambda (max anzahl)
...))
</code>
<run id="5bb66765ca9b7">
(zufallsliste 100 20)
</run>
== Elementsuche ==
Schreiben Sie nun die Prozedur <tt>suche</tt>, die nach einem Element in einer unverschachtelten Liste suchen soll.<br />
Ist das Element in dieser Liste enthalten, soll seine Position in der Liste zurückgegeben werden. Anderenfalls ist der Rückgabewert <tt>#f</tt>:
(suche 3 '(7 5 4 3 2 1 3 4 5)) --> 4
(suche 3 '(6 5 4 5)) --> #f
<code id="4ba16a4490d81">
(define suche
(lambda (el ls)
...))
</code>
<check>
(or (and (= (suche 3 '(-5 -3 1 3 3 45)) 4) (= (suche 3 '(-23 -23 -12 -2 0 0 1 1 3)) 9) (not (suche 3 '(1 2 5 6)))) (and (= (suche 3 '(7 5 4 3 2 1 3 4 5)) 4) (= (suche 3 '(7 5 4 2 1 9 4 5 3)) 9) (not (suche 3 '(6 5 4 5)))))
</check>
Testen Sie die Prozedur <tt>suche</tt> mit Zufallszahlenlisten.
<run id="5bb66765caa25">
(suche 57 (zufallsliste 100 100))
</run>
In diesem Suchverfahren werden alle Listenelemente solange nacheinander untersucht, bis eine Übereinstimmung festgestellt wird.<br />
Wir bezeichnen diesen ''Suchalgorithmus'' als ''lineare'' oder ''sequenzielle Suche''.
== Effizienz der sequenziellen Suche ==
Ein Algorithmus ist ''effizient'', wenn er mit möglichst geringem Ressourcenaufwand (Zeit, Speicherbedarf)
ein vorgegebenes Problem löst.<br />
Wir wollen uns im Weiteren auf den ''Zeitaufwand'' der sequenziellen Suche konzentrieren.<br />
Dazu nehmen wir vereinfacht an, dass jeder Vergleich der Elemente genau einem "Zeittakt" entspricht.
Die Prozedur <tt>suche</tt> liefert also den erforderlichen Zeitaufwand, wenn beim Rückgabewert <tt>#f</tt> die Länge der übergebenen Liste benutzt wird.<br />
=== Empirische Effizienzuntersuchungen ===
Wie viele Vergleiche sind im Mittel in einem vorgegebenen Intervall (Problemgröße) notwendig?<br />
Dazu definieren wir die Prozedur <tt>suche-mehrfach</tt>, die die Suche von Zufallszahlen $z$ mit $1 \le z \le max$ im Intervall $[1 ; max]$ mehrfach durchführt und den Mittelwert aller erforderlichen Vergleiche zurückgibt:
<code id="5bb66765ca75c">
(define suche-mehrfach
(lambda (max anzahl)
(letrec
([summe
(lambda (ls n)
(let* ([el (zufallszahl max)] [pos (suche el ls)])
(cond
[(= n 0) 0]
[(not pos) (+ (length ls) (summe ls (- n 1)))]
[else
(+ pos (summe ls (- n 1)))])))])
(/ (summe (zufallsliste max max) anzahl) anzahl))))
</code>
<run id="5bb66c9418afb">
(suche-mehrfach 100 100)
</run>
=== Experimente ===
Wir erweitern nun die sequenzielle Suche auf mehrere Intervalle und automatisieren diesen Prozess:
<code id="5bb66765ca7d4">
(define experiment
(lambda (min max schrittweite anzahl)
(if (> min max)
()
(append (experiment min (- max schrittweite) schrittweite anzahl)
(list (suche-mehrfach max anzahl))))))
</code>
<run id="5bbcb2daf182d">
(experiment 10 100 5 100)
</run>
Nun sollen unsere Untersuchungsergebnisse für eine größere Anzahl von Intervallen in einem Balkendigramm visualisiert werden.<br />
Dazu benutzen wir wieder das aus den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen|Mehrfachrekursionen]] bekannte Balkendiagramm. Zur Erinnerung soll die Syntax der Prozedur <tt>balkendiagramm</tt> für numerische Listen nochmals angegeben werden:
(balkendiagramm <ls>) ; <ls> ... Liste mit Zahlenwerten
'''Achtung!''' Beim Experimentieren ist etwas Geduld erforderlich!<br />
<canvas w="400" h="300"></canvas>
<code id="5bb66765ca846" 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="5bbcb2daf18c0">
(balkendiagramm (experiment 10 100 5 100))
</run>
'''Ergebnis:''' Offensichtlich wächst der Zeitaufwand bei der sequenziellen Suche ''linear'' mit der Problemgröße.
== Aufgaben ==
<ol>
<li>
=== Auswertung der empirischen Effizienzuntersuchung ===
Ermitteln Sie den Proportionalitätsfaktor in der vermuteten linearen Abhängigkeit
$\mbox{Zeitaufwand} = f(\mbox{Problemgröße)}$.<br />
Nutzen Sie dazu die lineare Regression der Tabellenkalkulation oder des grafikfähigen Taschenrechners.
</li>
<li>
=== Problemklasse der sequenziellen Suche ===
Die Grenzwertsuche im [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Projekt Zahlenfolgen|Projekt Zahlenfolgen]] ist eine typische Anwendung der sequenziellen Suche.<br />
Nennen Sie weitere Beispiele für die sequenzielle Suche aus der angewandten Informatik.<br />
Verallgemeinern Sie diese Beispiele zu einer Problemklasse, auf die eine sequenzielle Suche anzuwenden ist.
</li>
<li>
=== Häufigste Elemente ===
In [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Numerische Listen|numerischen Listen]] haben wir bereits nach ''einem'' Element gesucht, das am häufigsten vorkommt. Nun sollen in einer Liste mit Elementen eines beliebigen Datentyps ''alle'' Elemente ermittelt werden, die am häufigsten auftreten. Diese Elemente sind in einer Liste zurückzugeben.<br />
Implementieren Sie die entsprechende Prozedur und testen Sie diese auch an Listen mit Zufallszahlen.
'''Hinweis:''' Denken Sie ggf. an geeignete Hilfsprozeduren.
<code id="5bd3683774b4a">
(define maxelement-liste
(lambda (ls)
...))
</code>
<code id="5bd36f277ddff" hidden>
(define element-equal?
(lambda (ls1 ls2)
(letrec
([element?
(lambda (el ls)
(cond
[(null? ls) #f]
[(equal? el (car ls)) #t]
[else
(element? el (cdr ls))]))]
[streichen
(lambda (el ls)
(cond
[(null? ls) '()]
[(equal? el (car ls)) (cdr ls)]
[else
(cons (car ls) (streichen el (cdr ls)))]))])
(cond
[(and (null? ls1) (null? ls2)) #t]
[(or (null? ls1) (null? ls2)) #f]
[(not (element? (car ls1) ls2)) #f]
[else
(element-equal? (cdr ls1) (streichen (car ls1) ls2))]))))
</code>
<check>
(and (equal? (maxelement-liste '(1)) '(1))
(equal? (maxelement-liste '(2 2)) '(2))
(element-equal? (maxelement-liste '(1 2 3 4 a d 1 r f 1 e d a d 1 a d d 1 a a)) '(1 a d)))
</check>
<run id="5bd3683774c04">
(maxelement-liste '(2 3 e r 4 3 e 2 3 e))
</run>
<run id="5bd3683774c8c">
(maxelement-liste (zufallsliste 10 100))
</run>
</li>
</ol>
== Zum Weiterarbeiten ==
[[Bild:Wuerfel1.jpg|miniatur|Wurf mehrerer Würfel]]
=== Würfeln mit mehreren Würfeln ===
Wir dürfen davon ausgehen, dass beim Würfeln mit einem Würfel eine Gleichverteilung aller Augenzahlen vorliegt.<br />
Doch wie ist die ''Summe aller Augenzahlen'' verteilt, wenn mehrere Würfel gleichzeitig geworfen werden?<br />
Untersuchen Sie mit einem Simulationsprogramm, welche Häufigkeitsverteilung beim Werfen von 10 Würfeln vorliegt.
Nutzen Sie zur Auswertung geeignete Werkzeuge (z.B. eine Tabellenkalkulation).<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Würfeln mit mehreren Würfeln|Simulation]].