|
|
Dynamické hašovací tabulky
Vitovják, Radek ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
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.
|
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (vedoucí práce) ; Koubek, Václav (oponent) ; Sereni, Jean-Sébastein (oponent)
Jedním ze základních problémů moderní statistické fyziky je snaha porozumět \mbox{frustraci} a chaosu. Základním modelem je konečně dimenzionální Edwards-Anderson Ising model. V této práci zavádíme zobecnění tohoto modelu. Studujeme množinové systémy uzavřené na symetrické rozdíly. Ukážeme, že významnou otázku, zda groundstate v Ising modelu je jednoznačný, lze studovat v těchto množinových systémech. Krewerasova hypotéza říká, že každé perfektní párování v hyperkrychli $Q_n$ lze rozšířit na Hamiltonovskou kružnici. Tuto hypotézu jsme dokázali. Matching graf $\mg{G}$ grafu $G$ má za vrcholy perfektní párování v $G$ a hranami jsou spojeny ty dvojice perfektních párování, jejichž sjednocení tvoří Hamiltonovskou kružnici v $G$. Dokážeme, že matching graf $\mg{Q_n}$ je bipartitní a souvislý pro $n \ge 4$. Toto dokazuje Krewerasovu hypotézu, že graf $M_n$ je souvislý, kde $M_n$ vznikne z grafu $\mg{Q_n}$ kontrakcí vrcholů $\mg{Q_n}$, které odpovídají izomorfním perfektním párováním. Cesta v $Q_n$ vyhýbající se zadaným $f$ chybným vrcholům se nazývá dlouhá, jestliže její délka je alespoň $2^n - 2f - 2$. Analogicky kružnice je dlouhá, pokud její délka je alespoň $2^n - 2f$. Pokud jsou všechny chybné vrcholy ze stejné bipartitní třídy $Q_n$, pak jsou tyto délky nejlepší možné. Dokážeme, že pro každou množinu...
|
|
|
Reprezentace řetězců v hašovacích tabulkách
Urbánek, Vít ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
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.
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (vedoucí práce) ; Mareš, Martin (oponent)
Práce se zabývá studiem problému predchudce, kde datová struktura udržuje dynamickou usporádanou množinu klícu. Krome prehledu nejduležitejších publikovaných výsledku ukazujeme podrobný popis konkrétní možnosti, jak lze docílit pravdepodobnostní úpravy van Emde Boasovy struktury. Tato úprava snižuje pametovou nárocnost na optimum, akorát stejné casové složitosti (log logN) již není dosahováno v nejhorším prípade, ale v amortizovaném ocekávaném prípade. Nejlepší ocekávaná amortizovaná složitost dosahovaná na tríde (s ; s1-d)-hladkých distribucí je rovna O(log log n). Kombinací známých technik dostáváme novou datovou strukturu, která dosahuje stejné složitosti, ale na širší tríde distribucí než bylo doposud možné. Navíc lze jako podstrukturu využít optimální amortizované rešení problému navržené Beamem a Fichem, což zarucí omezení amortizované složitosti nové struktury na asymptoticky optimální hodnotu rovnou p(log n/ log log n).
|
|
|
Relation of determinism and non-determinism for linear time
Juračka, Matej ; Koubek, Václav (vedoucí práce) ; Kučera, Petr (oponent)
Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou.
|
|
| |
|
|
Relaxované vyvažování binárních vyhledávacích stromů
Kříž, Martin ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
Na rozdíl od klasických vyvážených binárních vyhledávacích stromů, kdy proces vyvažování následuje bezprostředně po každém vložení nebo ubrání prvku, relaxované vyvažování umožňuje oddělit tyto fáze a provést vyvažování odděleně. Má význam například při paralelním přístupu k datům, kdy je možné vyvažování odložit na dobu, kdy je systém málo zatížen požadavky uživatelů. Další výraznou výhodou popsaných typů relaxovaného vyvažování je to, že pri paralelním přístupu k datům potřebují držet pouze konstatní počet zámku při modifikujících operacích a umožnují tak více modifikujících operací současně ve stromu. Cílem této práce je experimentálne porovnat klasickou a relaxovanou variantu AVL stromu v několika různých scénárích v paralelním prostředí podle počtu porovnání, počtu a typu rotací a podle spotřebovaného času.
|
|
|
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.
|
|
| |
|
|
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.
|
host ::
RSS.