|
|
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 setří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.
|
|
|
Chromatické stromy
Nezval, Kamil ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
Červeno-černé stromy jsou obdobou binárních vyhledávacích stromů zaručující logaritmickou složitost svých operací i v nejhorším případě. Relaxovaná verze této datové struktury byla vyvinuta pro zrychlení operací a zvíšení míry souběžnosti v paralelním prostředí. Hlavní myšlenkou je oddělený vyvažování od aktualizace stromu. Cílem této diplomové práce je experimentálně porovnat standardní červeno-černé stromy a jejich jednotlivé relaxované varianty v neparalelním prostředí z hlediska chování na velkých datech.
|
|
|
Individualita a normalizace - aplikace teoretických poznatků v objektové realizaci
KOUBEK, Václav
Léta normalizace měla velký vliv na rozvoj lidské individuality, tedy i na rozvoj lidské osobnosti odrážející se ve výtvarném projevu. Tato bakalářská práce Individualita a normalizace proto zkoumá tuto problematiku na pozadí základních historických událostí v Evropě a v naší zemi po 2. světové válce, které v Československu vyústily v období totalitního režimu a dobu normalizace. Na základě těchto poznatků na vybraných příkladech práce popisuje, jak byla v období totality u nás ovlivňována umělecká scéna, zejména svoboda tvůrčího projevu, která je se svobodným rozvojem individuality neoddělitelně spjatá. Praktická část práce je objektovou realizací na toto téma.
|
|
| |
|
| |
|
|
Synchronizace konečných automatů
Vorel, Vojtěch ; Koubek, Václav (vedoucí práce) ; Pangrác, Ondřej (oponent)
Práce je úvodem do zkoumání synchronizačních slov konečných automatů a Černého domněnky. Podává přehled o důležitých výsledcích v oboru a metodách jejich dokazování, ale také o širokém spektru dosud nevyřešených otázek. Reprodukuje i důkazy některých nejnovějších výsledků, konkrétně Trakhtmanova horního odhadu obecného sycnhronizačního prahu a Steinbergova těsného odhadu pro jednoklastrové automaty s prvočíselnou délkou cyklu. V poslední kapitole se blíže zaměřujeme na problém synchronizace podmnožin a související výpočetní úlohy. Je zde prezentován nový dolní odhad maximálního synchronizačního prahu podmnožiny. Podařilo se také částečně určit časovou složitost jisté přirozeně omezené varianty PSPACE-úplné úlohy rozhodování o synchronizovanosti podmnožiny.
|
|
|
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.
|
|
|
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.
|
|
|
Implementation of operations in double-ended heaps
Bardiovský, Vojtech ; Koubek, Václav (vedoucí práce) ; Hubička, Jan (oponent)
Existuje viacero spôsobov ako vytvoriť dvojkoncovú haldu z dvoch klasických háld. V tejto práci rozšírime dvojkoncovú haldu založenú na prepojení listov a vytvoríme novú schému nazvanú L-korešpondencia. Táto schéma rozšíri triedu možných klasických háld použiteľných pre vytvorenie dvojkoncovej haldy (napr. Fibonacci halda, Rank-pairing halda). Ďalej umožní operácie ``Zníž prioritu'' a ``Zvýš prioritu''. Tento prístup ukážeme na troch konkrétnych haldách a odhadneme časovú zložitosť pre všetky operácie. Ďalším výsledkom je, že pre tieto tri konkrétne haldy, očakávaný čas operácií ``Zníž prioritu'' a ``Zvýš prioritu'' je obmedzený konštantou.
|
|
|
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).
|
host ::
RSS.