Sequenzielle Suche

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2012-09-30T12:45:40+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Zufallszahlen
2 Zufallslisten
3 Elementsuche
4 Effizienz der sequenziellen Suche
- 4.1 Empirische Effizienzuntersuchungen
- 4.2 Experimente
5 Aufgaben
6 Zum Weiterarbeiten
- 6.1 Würfeln mit mehreren Würfeln

Zufallszahlen

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

(random 100)

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

(wuerfelzahl)

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)

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

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)))])))])
      (exact->inexact (/ (summe (zufallsliste max max) anzahl) anzahl)))))

(suche-mehrfach 100 10)

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 100 1000 100 10)

Nun sollen unsere Untersuchungsergebnisse für eine größere Anzahl von Intervallen in einem Balkendigramm visualisiert werden.
Dazu benutzen wir das vom Projekt Zahlenfolgen bekannte Balkendiagramm. Die Syntax der Prozedur balkendiagramm vereinfacht sich erwartungsgemäß bei der Anwendung auf Listen:

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

Achtung! Beim Experimentieren ist etwas Geduld erforderlich!

(balkendiagramm (experiment 200 10000 200 100))

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

Aufgaben

Ermitteln Sie den Proportionalitätsfaktor in der vermuteten linearen Abhängigkeit \mbox{Zeitaufwand} = f(\mbox{Problemgr\"o\ss e)}.
Nutzen Sie dazu die lineare Regression der Tabellenkalkulation oder des grafikfähigen Taschenrechners.
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.

Zum Weiterarbeiten

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