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==
<!--
was ist suchen, wozu (anwendungsbereiche), wichtige aufgabe eines rechners, was kann damit gemacht werden: ersetzen,löschen,ändern
aufgrund hoher priorität sehr gut erforscht; 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]