|
|
Self-organizing linear lists
Kulman, Igor ; Koubková, Alena (vedoucí práce) ; Babka, Martin (oponent)
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ů).
|
|
|
Fibonacciho haldy - jejich varianty a alternativní datové struktury
Melka, Jakub ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
V této práci budeme zkoumat Fibonacciho haldy a jejich varianty. Alternativní verze Fibonacciho hald, tzv. thin a thick haldu zavedli H. Kaplan a R. E. Tarjan v roce 2008. Srovnáme tyto haldy jak z experimentálního, tak z teoretického hlediska a do tohoto srovnání zahrneme i některé klasické druhy hald, jmenovitě párovací a regulární haldu. Při experimentech nás bude nejvíce zajímat celkový čas nutný pro běh algoritmu, který pracuje s haldou. Na výsledcích ukážeme, že thin a thick haldy jsou obvykle rychlejší, než Fibonacciho halda a pomalejší, než regulární haldy. Na závěr shrneme poznatky získané experimenty.
|
|
|
Očekávaná výška binárních vyhledávacích stromů
Langhammer, Martin ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
V této práci studujeme očekávanou výšku binárních vyhledávacích stromů a některé jejich další vlastnosti. Očekávanou výšku zjišťujeme u nevyvážených stromů, a u dvou asi nejznámějších a nejpoužívanějších variant vyvážených stromů, tj. AVL a červeno-černých stromů. Kromě očekávané hodnoty výšek stromů zjišťujeme i rozptyl výšek stromů, a některé další statistiky. V práci se přikláníme k řešení pomocí experimentů. V textu dále uvádíme všechny nám známé teoretické výsledky. Především se zaměřujeme na srovnávání naměřených hodnot s teoreticky vypočtenými výsledky. U případů, kde teoretické výsledky neexistují, jsme se pokoušíme získat co nejpřesnější odhad. Kromě toho porovnáváme i rozdíly stromů mezi sebou. Okrajově měříme i rychlosti vytváření stromů. V experimentech také zkoumáme závislosti na různých typech vstupních dat, jako jsou netříděná data, či data vygenerovaná z různých typů rozdělení. Pro vyhodnocení výsledků používáme standardní statistické metody, především metodu lineární regrese.
|
|
|
Use of Markov decision processes for modelling of collective games
Zákutný, Roman ; Antoch, Jaromír (vedoucí práce) ; Koubková, Alena (oponent)
V tejto práci je navrhnutý a implementovaný model vychádzajúci z teórie Markovovho procesu so spojitým časom na jednu vybranú kolektívnu hru. Na vstupných dátach je prevedená rozsiahla analýza, na základe ktorej sú odvodené regresné modely pre odhady parametrov. Spustenou simuláciou je preukázaná použiteľnosť modelu a v porovnávacej analýze sú zhodnotené výhody nášho modelu oproti použitiu Markovovho reťazca s diskrétnym časom navrhnutom a implementovanom v mojej bakalárskej práci. Na záver je prevedená diskusia možného rozšírenia na ostatné hry.
|
|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Koubková, Alena (vedoucí práce) ; Yaghob, Jakub (oponent)
Klasické algoritmy pre triedenie vo vnútornej pamäti boli navrhnuté za predpokladu, že táto pamäť je homogénna. V moderných počítačoch je ale štruktúra pamäte hierarchická s rozdielnou rýchlosťou jednotlivých vrstiev. Doba výpočtu algoritmu teda závisí nielen na počte vykonaných operácií (napr. porovnanie prvkov), ale aj na počte presunov dát mezi jednotlivými vrstvami. Interné algoritmy tak získávajú niektoré rysy algoritmov externých. V tejto práci si kladieme za úlohu stručne zhrnúť existujúce prístupy k problematike a opísať známe vylepšenia niektorých algoritmov pre prácu v nehomogénnej pamäti. Hlavný doraz je kladený na implementáciu vybraných algoritmov a ich experimentálne overenie.
|
|
|
Vyhledávání tras v silniční síti
Voldřich, Matouš ; Koubková, Alena (oponent) ; Mareš, Martin (vedoucí práce)
Cílem práce je analýza problému hledání optimaální silniční trasy v mapě, návrh efektivních vyhledávacích algoritmů pro tento problém a jejich implementace v prostředí síťového serveru. Algoritmy by přitom měly brát v úvahu i požadavky reálného života, jako například zákazy odbočení, jednosměrné ulice a obdobná omezení.
|
|
|
Reprezentace řetězců v hašovacích tabulkách
Urbánek, Vít ; Koubek, Václav (oponent) ; Koubková, Alena (vedoucí práce)
Základním problémem hašování je řešení kolizí. Jednou z možností řešení tohoto problému je vytváření řetězců kolidujících prvků. Řetězce se ukládají buď uvnitř, nebo vně tabulky a jsou obvykle reprezentovány jako neuspořádané spojové seznamy. Cílem této práce je navrhnout alternativní struktury (uspořádané řetězce, samoupravující seznamy, ...) pro reprezentaci kolidujících prvků, implementovat je do známých algoritmů a alespoň experimentálně zhodnotit jejich vliv na rychlost základních operací v hašovacích tabulkách.
|
|
|
Dynamické hašovací tabulky
Vitovják, Radek ; Koubek, Václav (oponent) ; Koubková, Alena (vedoucí práce)
Cílem této práce je popsat různé metody umožňující změnu velikosti interní hašovací tabulky v závislosti na počtu vložených prvků a porovnat je na základě známých teoretických výsledků. Dále vypracovat vlastní experimentální studii chování a vzájemného porovnání vybraných metod na simulovaných datech. Závěry porovnat s teoretickými výsledky a s publikovanými výsledky předchozích experimentálních studií, pokud existují. První část práce obsahuje popis metod implementace hašovacích tabulek a analýzu očekávaného počtu porovnání klíčů při úspěšném a neúspěšném vyhledávání. Další část pak obsahuje výsledky experimentů provedených na hašovacích tabulkách implementovaných podle popisu v první části.
|
|
|
Operace DELETE ve srůstajícím hašování
Mrkva, Lukáš ; Skopal, Tomáš (oponent) ; Koubková, Alena (vedoucí práce)
Nazev pracc: Opcra.ee DELETE ve srustajicim luisovani Autor: Lukas Mrkva Katedra (listav): Katedra softwaroveho inzenyrstvi Vedouci diplomovc prace: R.NDr. Alona Koubkova, CSc. E-rnail vedouciho: koubkova@ksi.ms.mff.cuni.cz Abstrakt: Diplomova pnioe jo vcnovana opcraci DELETE vo srustajicim hasovani. Nejprve jsou uvodeny principy hasovani a nektere jeho zakladni druhy. O srnstajicim hasovani pojednava ka])itola 3, kde jsou podrobnc ]>o- psany i ruznc melody koikstrukce h;usovaoi tal)ulky ro/dekuio die pofadi ko- liznich zaznamu a pfitonniosti sklepa. Dale jsou ])fcdstaveny tri rozdilne al- goritmy pro opora.ci DKLI^TK a dctailne diskutovtiny jojich implnincntacc pro jcdnutlivo inotody srustajiciho ha.sova.ni. Po tooroticke cayti naslcdiiji vy- slodky a koinontafo oxpcriincntu na siniulovanych datodi. Pracr jc zainefcna zejmena na porovnani casovu narooiiosti jednotlivych mazacich algoritnm a na porovnani ca.su potfcl)nych k vyhlcdavani za'/nanm prod a po smazani cast! tabulky. Pouzito algoritiny iiu])lciu(1iitovane v ja/yco C' a vyslodky ex- pcrimcntn jsou ]>rilozouy na CD. Klfcova slova: srustajici hasovani. delcto Title: Deletion in Coalesced Hashing Author: Lukas Mrkva Department: Dopartnicnt of Software Engineering Supervisor: RXDr. Aleua Koulikova,CSc. Supervisor's e-mail address:...
|
|
|
Operace DELETE ve srůstajícím hašování
Mrkva, Lukáš ; Koubková, Alena (vedoucí práce) ; Skopal, Tomáš (oponent)
Diplomová práce je věnována operaci DELETE ve srůstajícím hašování. Nejprve jsou uvedeny principy hašování a některé jeho základní druhy. O srůstajícím hašování pojednává kapitola 3, kde jsou podrobně popsány i různé metody konstrukce hašovací tabulky rozdělené dle pořadí kolizních záznamů a přítomnosti sklepa. Dále jsou představeny tři rozdílné algoritmy pro operaci DELETE a detailně diskutovány jejich implementace pro jednotlivé metody srůstajícího hašování. Po teoretické části následují výsledky a komentáoe experimentů na simulovaných datech. Práce je zaměřena zejména na porovnání časové náročnosti jednotlivých mazacích algoritmů a na porovnání časů potřebných k vyhledávání záznamů před a po smazání části tabulky. Použité algoritmy implementované v jazyce C a výsledky experimentů jsou přiloženy na CD.
|
host ::
RSS.