Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25870
Titel: | Adaptive Suchverfahren |
VerfasserIn: | Schulz, Frank |
Sprache: | Deutsch |
Erscheinungsjahr: | 1999 |
Kontrollierte Schlagwörter: | Suchverfahren Markov-Kette Online-Algorithmus Listenverarbeitung |
Freie Schlagwörter: | adaptiver Suchalgorithmus adaptive search algorithm Markovian request sequence |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Dissertation |
Abstract: | 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 |
Datum des Eintrags: | 24-Jul-2007 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Dissertation_967_Schu_Fran_1999.pdf | 1,5 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.