|
|
Fraktální komprese časových řad
Lysík, Martin ; Koubková, Alena (oponent) ; Skopal, Tomáš (vedoucí práce)
Cieľom tejto práce bolo vyhľadávanie jednorozmerných fraktálnych distribúcií v reálnych časových radoch a ich použitie na kompresiu týchto časových radov. Bola preskúmaná použiteľnosť tejto metódy na bezstratovú ako aj stratovú kompresiu. Na základe analýzy problému bol ako prvý navrhnutý a implementovaný základný kompresný algoritmus. Tento bol postupne doplnený o jednoduché heuristiky pre rýchlejšie spracovanie dat a tiež rozširovaný o ďalšie kroky, ktoré mali minimalizovať jeho nedostatky. Ako výsledok vznikli dva rozširujúce kompresné algoritmy a jeden algoritmus s rozdielnym spôsobom spracovania dat. Chovanie týchto algoritmov, veľkosť výstupov a kvalita dekomprimovaných dát boli porovnané na rôznych vstupných dátach a algoritmy boli porovnané aj s existujúcimi kompresnými algoritmami a metódami používanými pre uchovávanie časových radov.
|
|
|
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.
|
|
|
Experimentální analýza algoritmů pro hledání nejkratších cest
Truchlý, Peter ; Mareš, Martin (oponent) ; Koubková, Alena (vedoucí práce)
Hľadanie najkratších ciest v grafe, je často riešenou úlohou programovania v mnohých podobách, zvyčajne ako súčasť riešenia iného problému. Vhodnosť algoritmu či implementácie, na riešenie konkrétnej skupiny problémov, nemusí byť na prvý pohľad zrejmá. V praxi preto môže nastať situácia, keď použitý algoritmus z hľadiska správnosti zodpovedá riešenej úlohe, avšak výkonovo o niekoľko rádov zaostáva. Cieľom diplomovej práce je poskytnutie aktuálneho, prakticky použiteľného prehľadu algoritmov, ktorý je doplnený o experimentálne zistenia a odporúčania vhodnosti pre jednotlivé typy úloh. Značná časť uvedených algoritmov bola otestovaná na spoločnej platforme, čím došlo k zjednoteniu a rozšíreniu predošlých výsledkov. Zahrnuté sú predovšetkým algoritmy triedy SSSP, implementovateľné na bežne dostupnom hardware, zmienené sú však aj algoritmy iných tried, napríklad OPSP a APSP. Špeciálna pozornosť je venovaná aktuálnemu trendu zvyšovania paralelizmu, či už vo forme viacjadrových CPU, alebo masívne paralelných výpočtov na platformách odvodených od GPU.
|
|
|
The influence of caches on the efficiency of sorting
Hrdina, Karol ; Yaghob, Jakub (oponent) ; Koubková, Alena (vedoucí práce)
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 medzi jednotlivými vrstvami. Interné algoritmy tak získavajú 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ý dôraz je kladený na implementáciu vybraných algoritmov a ich experimentálne overenie.
|
|
| |
|
|
Relaxované vyvažování binárních vyhledávacích stromů
Kříž, Martin ; Koubek, Václav (oponent) ; Koubková, Alena (vedoucí práce)
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.
|
|
| |
|
|
Simulace obchodniho domu
Bartušek, Martin ; Koubková, Alena (oponent) ; Černý, Jakub (vedoucí práce)
Cílem práce je napsání programu, který umožní navrhnout model obchodního domu (supermarketu). Do modelu postupně umisťujeme základní prvky - např. regály nebo pokladny, až vytvoříme funkční obchod. Poté diskrétní simulací zkusíme co nejpřesněji napodobit chování skutečných zákazníků. Důraz byl kladen na možnost umístit do modelu akční nabídky zboží a sledovat jejich úspěšnost. Abych porovnal simulaci s realitou, namodeloval jsem skutečný supermarket. Zaměřil jsem se na pozorování průměrné délky nakupování a průměrné útraty. Tato data přibližně odpovídala těm reálně naměřeným. Dále uvedu běžné marketingové techniky, které ovlivňují chování zákazníků, a ověřím jejich účinnost v simulaci. Stručně také popíši komerční simulační software.
|
|
|
Min-max haldy
Neuvirth, Jan ; Žemlička, Michal (oponent) ; Koubková, Alena (vedoucí práce)
Diplomová práce se věnuje detailnímu popisu oboustranných prioritních front, které vycházejí z běžně používané datové struktury halda. Zároveň se snažíme zjistit, jak se tyto datové struktury chovají na velkých datech. Vzájemně pak poměřujeme kvality těchto datových struktur na základě dosažených výsledků v experimentálních testech. Nesnažíme se kategoricky vyhlásit nejlepší min{max haldu, raději chceme čtenáři poskytnout dostatečné množství užitečných informací, které by nám dovolily vybrat použití takové struktury, která by v daných podmínkách vykazovala nejlepší chování.
|
|
|
Chromatické stromy
Nezval, Kamil ; Koubek, Václav (oponent) ; Koubková, Alena (vedoucí práce)
Č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.
|
host ::
RSS.