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. |