Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
Samoupravující seznamy
Název práce v jazyce práce (slovenština): Samoupravující seznamy
Název práce v češtině: Samoupravující seznamy
Název v anglickém jazyce: Self-organizing linear lists
Klíčová slova: vyhledávání, lineární seznam, samoupravující seznam
Klíčová slova anglicky: search, linear list, self-organizing list
Akademický rok vypsání: 2010/2011
Typ práce: diplomová práce
Jazyk práce: slovenština
Ústav: Katedra distribuovaných a spolehlivých systémů (32-KDSS)
Vedoucí / školitel: RNDr. Alena Koubková, CSc.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 14.09.2010
Datum zadání: 14.09.2010
Datum potvrzení stud. oddělením: 02.05.2013
Datum a čas obhajoby: 30.05.2011 00:00
Datum odevzdání elektronické podoby:11.04.2011
Datum odevzdání tištěné podoby:11.04.2011
Datum proběhlé obhajoby: 30.05.2011
Oponenti: RNDr. Martin Babka
 
 
 
Zásady pro vypracování
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. Úkolem diplomanta bude vypracovat přehled známých algoritmů pro řešení tohoto problému (s uvedením teoretických výsledků o jejich charakteristikách, jsou-li známy) a experimentální studii 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ů).
Seznam odborné literatury
J. H. Hester, D. S. Hirschberg: Self-organizing linear search. Computing Surveys 17 (1985), 295 - 311.

S. Albers, J. Westbrook: Self-organizing data structures. LNCS 1442 (1998), 13 - 51.

S. Albers: Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27 (1998), 682 - 693.

Další časopisecká literatura podle pokynů vedoucího.
 
Univerzita Karlova | Informační systém UK