Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25870
Titel: Adaptive Suchverfahren
Verfasser: Schulz, Frank
Sprache: Deutsch
Erscheinungsjahr: 1999
SWD-Schlagwörter: Suchverfahren
Markov-Kette
Online-Algorithmus
Listenverarbeitung
Freie Schlagwörter: adaptiver Suchalgorithmus
adaptive search algorithm
Markovian request sequence
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: In der vorliegenden Arbeit untersuchen wir adaptive Suchalgorithmen. Diese Verfahren arbeiten online und versuchen, ohne Kenntnis zukünftiger Anfragen gute Antwortzeiten zu erzielen, indem sie ihre Suchstrategie dynamisch ändern. Wir analysieren bekannte und entwickeln neue Verfahren für sequentielle Suche unter kompetitiven und stochastischen Kostenmodellen. Ein Schwerpunkt der Arbeit liegt auf Markov-Ketten als Zugriffsmodell, die eine Verallgemeinerung unabhängiger Zugriffe darstellen und praktisch beobachtete Phänomene gut beschreiben können. Verschiedene Varianten des Problems wie randomisierte Algorithmen, gewichtete Zugriffskosten oder bidirektionale Suche werden ebenfalls betrachtet, außerdem vergleichen wir die Konvergenzgeschwindigkeit der einzelnen Verfahren. Adaptive Verfahren ermöglichen es implizit, statistische Informationen über die Anfragefolgen zu sammeln, diewir zur Datenkompression einsetzen. Außerdemschlagen wir eine Verallgemeinerung des Kostenmaßes für Kodes und Suchbäume vor, bei demdie Vergleichskosten nicht konstant sind, sondern exponentiellmit der Tiefe wachsen, und analysieren die Auswirkungen dieses Modells.
This thesis deals with adaptive search algorithms. These algorithms work online and strive to achieve fast response time without knowledge of future requests by modifying their search strategy dynamically. We analyse known and devise new algorithms for sequential search problems in the competitive and average case settings. Special emphasis is placed on Markovian request sequences, as they provide a generalization of the independent request model and are well suited to describe real data. We also consider several variations of the problem, like randomised algorithms, weighted access costs or bidirectional search, and we investigate the convergence speeds of thealgorithms. Adaptive algorithms implicitly collect statistical information on the request sequence that can be used for data compression. Furthermore we propose a generalization of the cost functions on codes and trees. While the comparison costs are constant in the standard model, they now increase exponentially with the depth. We analyse and discuss the impacts of this model.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-11950
hdl:20.500.11880/25926
http://dx.doi.org/10.22028/D291-25870
Erstgutachter: Hotz, Günter
Tag der mündlichen Prüfung: 29-Okt-1999
SciDok-Publikation: 24-Jul-2007
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_967_Schu_Fran_1999.pdf1,5 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.