|
|
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 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.
|
|
|
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.
|
|
|
Experimentální analýza algoritmů pro hledání nejkratších cest
Truchlý, Peter ; Koubková, Alena (vedoucí práce) ; Mareš, Martin (oponent)
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.
|
|
|
Fraktální komprese časových řad
Lysík, Martin ; Skopal, Tomáš (vedoucí práce) ; Koubková, Alena (oponent)
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.
|
|
|
Operace DELETE ve srůstajícím hašování
Mrkva, Lukáš ; Koubková, Alena (vedoucí práce) ; Skopal, Tomáš (oponent)
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:...
|
|
|
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.
|
|
|
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.
|
|
|
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.
|
host ::
RSS.