AuK/Sortieren und Suchen WS13-14

Wiki-Quelltext dieser Seite.

=Einleitung=

=Sortieren=

<!--

Immer:
Name, Ablauf, Effizienz
Eventuell: Ordnung nach intern / extern
Eventuell: Für einige Beispiele Quellcode - Übungsaufgaben
Eventuell: Veranschaulichung der Verfahren mittels Animation / Tafel...
 -->



=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.
<!--
was ist suchen, wozu (anwendungsbereiche), 
 vorsortiert oder nicht, baum oder nicht (auf welche strukturen anwendbar)
In den No-Free-Lunch-Theoremen wurde gezeigt, dass – gemittelt über alle mathematisch formulierbaren Probleme – alle Suchverfahren gleich gut sind. Einen Leistungsvorsprung zeigt ein Suchverfahren jeweils nur auf einer speziellen Klasse von Problemen.
heuristiken!
-->
==Lineare Suche==
==Binäre Suche==
==Fibonacci Suche==
<!--
nicht besser als binäre suche->beweis!
deshalb nur kurze vorstellung 
-->
==Binäre Suchbäume==
<!--
wie aufgebaut, min-max suche, breitensuche und tiefensuche evtl.
-->
==Rot-Schwarz-Bäume==
==Hashing==
<!--
wo angewandt: datenbanken, wichtig!
-->
===Extern===
===Intern===
==String-Matching==
<!--
knuth-morris-prat algo, suchen in texten, boyer moore
-->
==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.
:[mailto://s3damuel@stud.hszg.de Dana Müller]
:[mailto://s3rostri@stud.hszg.de Robert Stricker]