Suchalgorithmen

Suchalgorithmen

Ein häufiges Problem in der Informatik ist es, bestimmte Datensätze in einer Datenbank zu suchen. Dies hört sich erst mal sehr einfach an. "Einfach alle Datensätze anschauen und zack, fertig". Bei Datensätzen mit weniger als 20 Daten mag das noch einfach sein. Aber stellt euch vor, Google will seine Website-Datenbank mit ein paar Quadtrillionen Einträgen nach dem Begriff "Bester Suchalgorithmus ever" durchsuchen. Schon nicht mehr so ganz einfach, oder?

Um das grundlegende Problem besser zu verstehen, beschränken wir uns zunächst mal auf einfachere Suchprobleme. Statt einer gesamten Datenbank betrachten wir "nur" einen Array, und anstatt von Websites, die wir auf ein bestimmtes Stichwort durchsuchen wollen, beschränken wir uns zunächst mal auf Zahlen.

Aufgabe 1

Lest den Artikel Suchproblem auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.

Bearbeitet auch Aufgabe 1 aus dem Artikel (Antworten → Gruppendokument!).

Aufgabe 2

Lest den Artikel Entwicklung von Suchalgorithmen auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.

Bearbeitet auch Aufgabe 1 aus dem Artikel (Antworten → Gruppendokument!).

Aufgabe 3

Lest den Artikel Lineare Suche auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.

Bearbeitet nur die Aufgaben 1+2 (Antworten → Gruppendokument!).
Statt Aufgabe 3:
- Lest die beiden Info-Texte vom Fachkonzept: Brute-Force- und Lineare Suche.
- Versucht, beide Algorithmen eigenständig zu implementieren. Nutzt dazu die Vorlagen unten. Bei Problemen schaut euch die Implementierungen im Fachkonzept an.
- Probiert die beiden Algorithmen in Processing aus. Sucht nach unterschiedlichen Zahlen (sowohl welche, die im Array vorkommen und solche, die nicht vorkommen).

Vorlage zu Aufgabe 3

SearchTemplate_unsortiert.pde

int[] daten = new int[] { 8, 52, 33, 30, 69, 84, 72, 99, 78, 86, 18, 17, 89, 83, 65, 95, 14, 6, 9, 38, 5, 98, 9, 39, 82 };
 
int gesucht = 72;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (wasAuchImmer) {
  sucheDieZahl;
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}

SearchTemplate_sortiert.pde

int[] daten = new int[] { 5, 6, 8, 9, 9, 14, 17, 18, 30, 33, 38, 39, 52, 65, 69, 72, 78, 82, 83, 84, 86, 89, 95, 98, 99 };
 
int gesucht = 72;
boolean gefunden = false;
int position = 0;
int anzahlSchritte = 0;
 
while (wasAuchImmer) {
  sucheDieZahl;
}
 
if (!gefunden) {
  println("Das Element " + gesucht + " wurde nicht gefunden. Abbruch nach " + anzahlSchritte + " Schritten.");
} else {
  println("Die Position von " + gesucht + " ist: " + position + ". Abbruch nach " + anzahlSchritte + " Schritten.");
}

Aufgabe 4

Lest den Artikel Binäre Suche auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.

Bearbeitet nur Aufgabe 1.
Statt Aufgabe 2:
- Lest den Info-Text vom Fachkonzept: Binäre Suche.
- Versucht, den Algorithmus eigenständig zu implementieren. Nutzt auch dazu die Vorlage für sortierte Listen von Aufgabe 3. Bei Problemen schaut euch die Implementierungen im Fachkonzept an.
Probiert den neuen Algorithmus in Processing aus. Sucht nach unterschiedlichen Zahlen (sowohl welche, die im Array vorkommen und solche, die nicht vorkommen).

Aufgabe 5

Lest den Artikel Aufwandsanalyse auf inf-schule.de. Notiert eure Antworten zu den Fragen im Artikel im Gruppendokument.

Aufgabe 2

Sucht euch einen der drei Algorithmen von vorhin aus und implementiert diesen für das Adressbuch!

Achtung: Den Inhalt der void setup()-Methode und die Klasse class Adresse müsst ihr nicht verstehen, es geht hier nur um die Methode Adresse suche(String vorname, String nachname)!

Verwendet eine der beiden Adress-Datenbanken, je nach dem, welchen Algorithmus ihr gewählt habt!
- bei loadTable("l2-adressdaten.csv", "csv") in Zeile 5 ggf. Dateinamen anpassen!
- l2-adressdaten.csv oder l2-adressdaten_sortiert.csv

Tipps:
- mit if (adressen[position].getNachname().equals(nachname)) { … } kann man den Nachnamen der i-ten Adresse auf Gleichheit zu nachname überprüfen
- mit if (adressen[position].getNachname().compareTo(nachname) > 0) { … } kann man überprüfen, ob der Nachname der i-ten Adresse größer als der gesuchte nachname ist
- Statt der Position der gefundenen Adresse soll die Adresse selbst zurückgegeben werden. Das funktioniert z.B. mit return adresse[position];.

Vorlage für Aufgabe 2

Sketch

Search_AdressesTemplate.pde

Adresse[] adressen;
int vergleiche = 0;
 
void setup() {  
  Table table = loadTable("l2-adressdaten.csv", "csv");
 
  int anzahl = table.getRowCount();
  adressen = new Adresse[anzahl];
 
  int i = 0;
 
  for (TableRow row : table.rows()) {  
    String nachname = row.getString(0);
    String vorname = row.getString(1);
    String adresse = row.getString(2);
    String plz = row.getString(3);
    String ort = row.getString(4);
 
    adressen[i++] = new Adresse(nachname, vorname, adresse, plz, ort);
  }
 
  String vorname = "Nadine";
  String nachname = "Muench";
  Adresse adresse = suche(nachname, vorname);
 
  println("Die Suche benötigte " + vergleiche + " Vergleiche!");
 
  if (adresse != null) {
    println(vorname + " " + nachname + " wohnt in " + adresse.getAdresse()  + ", " + adresse.getPlz() + " " + adresse.getOrt());
  } else {
    println("Keine Adresse von " + vorname + " " + nachname + " gefunden!");
  }
}
 
Adresse suche(String nachname, String vorname) {
  // Hier kommt euer Algorithmus hin!
 
  return null;
}

Adresse

Adresse.pde

class Adresse {
  private String nachname, vorname, adresse, plz, ort;
 
  Adresse(String nachname, String vorname, String adresse, String plz, String ort) {
    this.nachname = nachname;
    this.vorname = vorname;
    this.adresse = adresse;
    this.plz = plz;
    this.ort = ort;
  }
 
  String getNachname() { return nachname; }
  String getVorname() { return vorname; }
  String getAdresse() { return adresse; }
  String getPlz() { return plz; }
  String getOrt() { return ort; }
 
}

Lösung: Brute Force

Verwende die unsortierte Liste!

Adresse suche(String nachname, String vorname) {
  for (int i = 0; i < adressen.length; i++) {
    vergleiche++;
 
    if (adressen[i].getNachname().equals(nachname) && adressen[i].getVorname().equals(vorname)) {
      return adressen[i];
    }
  }
 
  return null;
}

Lösung: Lineare Suche

Verwende die sortierte Liste!

Adresse suche(String nachname, String vorname) {
  for (int i = 0; i < adressen.length; i++) {
    vergleiche++;
 
    if (adressen[i].getNachname().equals(nachname) && adressen[i].getVorname().equals(vorname)) {
      return adressen[i];
    } else if (adressen[i].getNachname().compareTo(nachname) > 0) {
      return null;
    }
  }
 
  return null;
}

Lösung: Binäre Suche

Verwende die sortierte Liste!

Adresse suche(String nachname, String vorname) {
  int links = 0;
  int rechts = adressen.length - 1;
 
  while (links <= rechts) {
    int mitte = links + (rechts - links) / 2;
    Adresse a = adressen[mitte];
 
    if (a.getNachname().equals(nachname) && a.getVorname().equals(vorname)) {
      return adressen[mitte];
    }
 
    if (a.getNachname().compareTo(nachname) > 0) {
      rechts = mitte - 1;
    } else if (a.getNachname().compareTo(nachname) < 0) {
      links = mitte + 1;
    } else if (a.getVorname().compareTo(vorname) > 0) {
      rechts = mitte - 1;
    } else if (a.getVorname().compareTo(vorname) < 0) {
      links = mitte + 1;
    } 
 
    vergleiche++;
  }
 
  return null;
}

Alle Lösungen

searchalgorithms.zip