Original title: Samoupravující seznamy
Translated title: Self-organizing linear lists
Authors: Kulman, Igor ; Koubková, Alena (advisor) ; Babka, Martin (referee)
Document type: Master’s theses
Year: 2011
Language: slo
Abstract: [eng] [cze]
Self-organizing linear lists Self-organizing linear lists are data structures for fast search, provided that certain elements stored in them are searched more frequently than others, while the probability of access to individual elements is generally not known in advance. Efficient search is achieved using different permutation rules that keep changing the list structure so that the more frequently searched elements are closer to the beginning. This thesis gives an overview of known algorithms for solving this problem (with the theoretical results about their complexity, if they are known), and experimental study of their behavior (using its own or freely available implementations and software for generating input data, testing algorithms and processing the results of experiments). Samoupravující seznamy Samoupravující seznamy jsou datové struktury sloužící k rychlému vyhledávání za předpokladu, že některé prvky v nich uložené jsou vyhledávány častěji než jiné, přičemž pravděpodobnosti přístupu k jednotlivým prvkům obecně nejsou předem známy. Efektivnějšího vyhledávání je dosaženo použitím různých permutačních pravidel, která průběžně mění uspořádání seznamu tak, aby častěji vyhledávané prvky byly blíže k jeho začátku. V této práci je uveden přehled známých algoritmů pro řešení tohoto problému (s uvedením teoretických výsledků o jejich složitosti, jsou-li známy) a experimentální studie o jejich chování (s využitím vlastních nebo volně dostupných implementací a programových prostředků pro generování vstupních dat, testování algoritmů a zpracování výsledků experimentů).
Keywords: linear list; search; self-organizing list; lineární seznam; samoupravující seznam; vyhledávání

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/48275

Permalink: http://www.nusl.cz/ntk/nusl-312561


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses