Sortieren und Suchen WS13-14
Inhaltsverzeichnis |
Einleitung
Sortieren
Suchen
Einführung
Das Suchen nach Daten ist eine der wichtigsten Aufgaben eines Computers, da es weitere grundlegende Operationen wie das Ersetzen, Löschen oder Ändern von Daten erst ermöglicht. Aufgrund dieser hohen Priorität sind Suchverfahren sehr gut hinsichtlich ihres Aufwandes erforscht. Suchen ist dabei das Finden von Mustern oder Objekten mit bestimmten Eigenschaften in einem Suchraum. Beispiele sind Zeichenketten aus einem Text oder Zahlen aus einer Liste von Zahlen. Betrachtet werden auch die Datenstrukturen, auf welche die Verfahren angewendet werden können (elementare oder effizientere, wie Bäume). Außerdem ist zu prüfen, ob eine Vorsortierung des Suchraumes notwendig, effizienzverbessernd oder unnötig ist. In diesem Kapitel werden verschiedene Suchverfahren mit ihren Aufwänden vorgestellt, von einfachen schrittweisen Suchen und deren Verbesserungen hin zu komplexen Suchvorgängen in Bäumen.
Lineare Suche
Binäre Suche
Fibonacci Suche
Binäre Suchbäume
Rot-Schwarz-Bäume
Hashing
Extern
Intern
String-Matching
Interpolationssuche
Übungen
Literaturverzeichnis
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007
- Sedgewick, Robert: Algorithmen, Addison-Wesley, 1992
- Heun, Volker: Grundlegende Algorithmen, Vieweg, 2000
- Mehlhorn, Volker: Datenstrukturen und effiziente Algorithmen Band 1 Sortieren und Suchen, B. G. Teubner Stuttgart, 1988
Kontakt
Sollten während der Nacharbeitung der Vorlesung Fragen auftreten, können diese gern gestellt werden.