Sequenzielle Suche

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Zufallszahlen 2 Zufallslisten 3 Elementsuche 4 Effizienz der sequenziellen Suche 4.1 Empirische Effizienzuntersuchungen 4.2 Experimente 5 Aufgaben 5.1 Auswertung der empirischen Effizienzuntersuchung 5.2 Problemklasse der sequenziellen Suche 5.3 Häufigste Elemente 6 Zum Weiterarbeiten 6.1 Würfeln mit mehreren Würfeln

Zufallszahlen

Wir haben bereits Zufallszahlen in Prozeduren mit Zeichenketten und Listen implementiert. Dabei wurde folgende Syntax genutzt:

(random 100)

ausführen

Zur Erinnerung: (random <max>) gibt eine Zufallszahl $z$ zurück mit $0 \le z < max$.
Vervollständigen Sie die nachfolgende nullstellige Prozedur, mit der das Würfeln einer Augenzahl $z$ mit $1 \le z \le 6$ simuliert werden kann:

(define wuerfelzahl (lambda () ...))

(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))))))

(wuerfelzahl)

ausführen

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 zufallsliste.

(define zufallszahl (lambda (max) (+ 1 (random max)))) (define zufallsliste (lambda (max anzahl) ...))

(zufallsliste 100 20)

ausführen

Elementsuche

Schreiben Sie nun die Prozedur suche, die nach einem Element in einer unverschachtelten Liste suchen soll.
Ist das Element in dieser Liste enthalten, soll seine Position in der Liste zurückgegeben werden. Anderenfalls ist der Rückgabewert #f:

(suche 3 '(7 5 4 3 2 1 3 4 5)) --> 4
(suche 3 '(6 5 4 5)) --> #f

(define suche (lambda (el ls) ...))

Testen Sie die Prozedur suche mit Zufallszahlenlisten.

(suche 57 (zufallsliste 100 100))

ausführen

In diesem Suchverfahren werden alle Listenelemente solange nacheinander untersucht, bis eine Übereinstimmung festgestellt wird.
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.
Wir wollen uns im Weiteren auf den Zeitaufwand der sequenziellen Suche konzentrieren.
Dazu nehmen wir vereinfacht an, dass jeder Vergleich der Elemente genau einem "Zeittakt" entspricht. Die Prozedur suche liefert also den erforderlichen Zeitaufwand, wenn beim Rückgabewert #f die Länge der übergebenen Liste benutzt wird.

Empirische Effizienzuntersuchungen

Wie viele Vergleiche sind im Mittel in einem vorgegebenen Intervall (Problemgröße) notwendig?
Dazu definieren wir die Prozedur suche-mehrfach, 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:

(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))))

(suche-mehrfach 100 100)

ausführen

Experimente

Wir erweitern nun die sequenzielle Suche auf mehrere Intervalle und automatisieren diesen Prozess:

(define experiment (lambda (min max schrittweite anzahl) (if (> min max) () (append (experiment min (- max schrittweite) schrittweite anzahl) (list (suche-mehrfach max anzahl))))))

(experiment 10 100 5 100)

ausführen

Nun sollen unsere Untersuchungsergebnisse für eine größere Anzahl von Intervallen in einem Balkendigramm visualisiert werden.
Dazu benutzen wir wieder das aus den Mehrfachrekursionen bekannte Balkendiagramm. Zur Erinnerung soll die Syntax der Prozedur balkendiagramm für numerische Listen nochmals angegeben werden:

(balkendiagramm <ls>) ; <ls> ... Liste mit Zahlenwerten

Achtung! Beim Experimentieren ist etwas Geduld erforderlich!

(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)))))

(balkendiagramm (experiment 10 100 5 100))

ausführen

Ergebnis: Offensichtlich wächst der Zeitaufwand bei der sequenziellen Suche linear mit der Problemgröße.

Aufgaben

1. Auswertung der empirischen Effizienzuntersuchung

   Ermitteln Sie den Proportionalitätsfaktor in der vermuteten linearen Abhängigkeit $\mbox{Zeitaufwand} = f(\mbox{Problemgröße)}$.
   Nutzen Sie dazu die lineare Regression der Tabellenkalkulation oder des grafikfähigen Taschenrechners.

2. Problemklasse der sequenziellen Suche

   Die Grenzwertsuche im Projekt Zahlenfolgen ist eine typische Anwendung der sequenziellen Suche.
   Nennen Sie weitere Beispiele für die sequenzielle Suche aus der angewandten Informatik.
   Verallgemeinern Sie diese Beispiele zu einer Problemklasse, auf die eine sequenzielle Suche anzuwenden ist.

3. Häufigste Elemente

   In 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.
   Implementieren Sie die entsprechende Prozedur und testen Sie diese auch an Listen mit Zufallszahlen.

   Hinweis: Denken Sie ggf. an geeignete Hilfsprozeduren.

   (define maxelement-liste (lambda (ls) ...))

   (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))]))))

    

   Quelltext überprüfen:

   jetzt prüfen

   (maxelement-liste '(2 3 e r 4 3 e 2 3 e))

   ausführen

   (maxelement-liste (zufallsliste 10 100))

   ausführen

Zum Weiterarbeiten

Würfeln mit mehreren Würfeln

Wir dürfen davon ausgehen, dass beim Würfeln mit einem Würfel eine Gleichverteilung aller Augenzahlen vorliegt.
Doch wie ist die Summe aller Augenzahlen verteilt, wenn mehrere Würfel gleichzeitig geworfen werden?
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).

Zur Simulation.