Sequenzielle Suche

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Zufallszahlen

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

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:

 

Quelltext überprüfen:

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.

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

 

Quelltext überprüfen:

Testen Sie die Prozedur suche mit Zufallszahlenlisten.

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:

Experimente

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

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!

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.

     

    Quelltext überprüfen:

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.

Persönliche Werkzeuge