Effizientes Suchen - Wiki Informatik Grundkurs Abi 2017

EF-V-A4
Binäres Suchen
Seite 1 von 2
„Search & Destroy!“ – Effizientes Suchen
Einleitung
Eine der wichtigsten Aufgaben in der elektronischen Datenverarbeitung ist das Suchen von Informationen in
großen Mengen von Daten: Bei Banken werden Buchungen gesucht, in der Schuldatenbank die Note eines
bestimmten Schülers, in der Verkehrssünderkartei in Flensburg die Adresse eines Fahrers zu einem
bestimmten Kennzeichen und so weiter und so fort. Auch der Duden Informatik widmet sich in einem
Abschnitt dem Suchen und den Suchalgorithmen:
„Suchen: Tätigkeit, in einem vorgegebenen Datenbestand alle Objekte zu ermitteln, die eine bestimmte
Bedingung, das Suchkriterium, erfüllen. Man unterscheidet interne und externe Suchverfahren. […] Typische
interne Suchverfahren sind das binäre Suchen, das sequenzielle Suchen und das Suchen auf dem binären
Suchbaum. Das Suchen auf B-Bäumen und das Hash-Verfahren sind überwiegend externe Suchverfahren.
Hash-Verfahren mit Auslastungsgrad unter 80% sind den meisten Suchverfahren überlegen.“(DUDEN
Informatik A-Z, Claus, Schwill et. al., 4. Aufl., Mannheim 2006)
Unsere alltäglichen Suchstrategien, z.B. bei der Suche in einem Lexikon, in einem Text, im Kochbuch oder im
Adressbuch unseres Handys, stoßen bei großen Datenmenge (siehe ZENSUS 2011) schnell an ihre Grenzen.
Ähnlich wie bei den einfachen Sortieralgorithmen ist ihre Laufzeit bei großen Datenmengen nicht vertretbar.
Mit Hilfe der nächsten drei Aufgaben werden wir zunächst einfache Suchstrategien anwenden und
anschließend eine ebenfalls einfache, aber sehr effiziente Suchstrategie kennen lernen
Aufgabe 1: Schiffe versenken!
1. Suche dir einen Partner. Ihr müsst diese Aufgabe unbedingt zu zweit lösen.
2. Lest euch zunächst alle 7 Schritte dieser Aufgabe durch und klärt eventuelle Fragen! Es ist sehr
wichtig, dass ihr, sobald ihr die Bögen erhalten habt (siehe Schritt 4) wisst wie das Spiel funktioniert.
3. Setzt euch Rücken an Rücken, so dass ihr nicht auf die Arbeitsblätter eures Partners sehen könnt.
4. Ihr erhaltet nun zwei Bögen: Einer von euch nimmt den Bogen 1A, der andere den Bogen 1B. Achtet
darauf, dass ihr nicht auf den Bogen eures Partners schaut, da sonst die Aufgabe nicht lösbar und der
Spaß an der Sache sofort verloren geht.
5. Nun kreist jeder auf seinem Bogen in der oberen Hälfte eines der 26 Schlachtschiffe ein und sagt
eurem Partner dessen 4-stellige Nummer. Dieses Schiff muss euer Partner nun „versenken“, wenn er
gewinnen will.
6. Abwechselnd (der jüngere von euch beginnt) ratet ihr nun in welchem Feld (A bis Z) das
Schlachtschiff eures Partners versteckt ist. Euer Partner antwortet auf euren Buchstaben jeweils mit
der Nummer des Schiffes in diesem Feld (Beispiel: „J“  „1234“). Solltet ihr das Schiff verfehlt haben
streicht ihr das Schiff im falsch geratenen Feld in der unteren Hälfte eures Bogens durch.
7. Das Spiel endet, wenn beide Partner das Schiff des jeweils anderen gefunden/getroffen haben. Das
Ergebnis dieser Partie ist dann die Anzahl der Schüsse die ihr benötigt habt (z. B. „5 zu 9 ).
Sobald alle Gruppen mit Aufgabe 1 fertig sind werden wir die Ergebnisse zunächst sammeln! Beginnt noch
nicht mit Aufgabe 2! Solltet ihr sehr schnell mit Aufgabe 1 fertig geworden sein, könnt ihr euch noch zwei
weitere Bögen (1A‘ und 1B‘) holen und das Spiel wiederholen. Je mehr Ergebnisse wir haben, umso besser
wird die Auswertung funktionieren.
EF-V-A4
Binäres Suchen
Seite 2 von 2
Aufgabe 2: Schiffe versenken revisited!
1. Setzt euch in die gleiche Ausgangssituation wie bei Aufgabe 1.
2. Ihr erhaltet nun wieder zwei Bögen (2A und 2B) und wiederholt das Spiel von Aufgabe 1.
Ein „kleiner“ Tipp:
Die Nummern der Schiffe sind nun im Gegensatz zur Aufgabe 1 in aufsteigender
Reihenfolge (von klein nach groß) sortiert!!!
Aufgabe 3: Algorithmus zur effizienten Suche (ggf. Hausaufgabe)
Versucht nun unsere Beobachtungen aus der Aufgabe 2 in einen Algorithmus zur effizienten Suche
umzusetzen. Dieses Verfahren nennt man auch die „binäre Suche“. Verwendet dazu ein PAP und innerhalb
des PAP Umgangssprache oder Pseudocode.
„binäres Suchen (auch Intervallschachtelung genannt): Bezeichnung für ein schnelles Verfahren zum Suchen
von Elementen in einem aufsteigend oder absteigend vorsortierten linearen Feld durch fortgesetztes
Halbieren des Bereiches, in dem sich das zu suchende Element noch befinden kann.[…]“(DUDEN Informatik AZ, Claus, Schwill et. al., 4. Aufl., Mannheim 2006)
Ergebnisse von Aufgabe 1 (Tafelabschrieb)
Durchschnittliche Anzahl der Schüsse
…insgesamt:
…bis zum Sieg:
Ergebnisse von Aufgabe 2 (Tafelabschrieb)
Durchschnittliche Anzahl der Schüsse
…insgesamt:
Welchen Vorteil bringt die Sortierung?
…bis zum Sieg:

Download Report