|
Delta Compression
Kmeť, Peter ; Senft, Martin (vedoucí práce) ; Bílý, Tomáš (oponent)
V tejto práci prezentujem algoritmus na riešenie problému delta kompresie spočúvajúceho v otázke ako úsporne reprezentovať zmeny, ktoré nastali v upravenej verzií súboru vzhľadom na povodný súbor. Algoritmus využíva metódu hľadania v slovníku na nahrádzanie opakujúcich sa reťazcov znakov krátkymi odkazmi na ich predchádzajúci výskyt, pričom sa zhody zisťujú v oboch súboroch. Spoločné predpony reťazcov sa získavajú prostrednictvom su xových polí, potenciálne zaujúmavej alternatívy k iným postupom. Riešenie je rozdelené do niekoľkých ľahko zmeniteľných modulov a rozdiely sa ukladajú v súboroch vo vlastnom formáte. V práci sa stručne diskutujú výsledky použitých techník a navrhujú vylepšenia projektu.
|
|
Algorithm Visualisation
Vranec, Maroš ; Senft, Martin (vedoucí práce) ; Kučera, Luděk (oponent)
Knižnica animelib je určená pre užívateľsky prívetivú vizualizáciu algoritmov. Dôraz je kladený na to, aby programátor nemusel písať veľa kódu, ktorý sa týka vizualizácie, a tiež nemusel príliš prispôsobovať jeho vlastný kód (teda kód algoritmu, ktorý chce vizualizovať). Zaoberá sa vizualizáciou základných dátových štruktúr (zoznam, spojový zoznam, strom a graf). Práca s knižnicou je takmer transparentná, jediná potrebná vec je zaregistrovať dátové štruktúry, ktoré sa majú zobraziť. Knižnica naviac poskytuje rozšírené operácie na objektoch, ktoré dovoľujú lepšie animovať.
|
|
Suffix Array for Large Alphabet
Šesták, Radovan ; Lánský, Jan (vedoucí práce) ; Senft, Martin (oponent)
Burrows-Wheelerova Transformace (BWT) [3] je používána jako hlavní část blokové komprese, která má dobrý kompresní poměr a přijatelný čas běhu. Suffixová pole jsou používána v kódovací fázi BWT a my se soustředíme na jejich tvorbu pro abecedu větší než 2^8 symbolů. Motivací pro tuhle práci byl softwarový projekt XBW [4] - aplikace pro kompresi velkých XML souborů. Úkolem BWT je přeuspořádat vstup před použitím jiných algoritmů. Popisujeme a implementujeme tři skupiny algoritmů pro kódování. První je inspirována prací Sadakana [10] a dále vylepšená Larssonem [8]. Druhá skupina obsahuje algoritmus od Sewarda [11] a algoritmus od Itoha vylepšený Kaoem [5]. Závěrem prezentujeme algoritmus od Kärkkäinena a Sanderse [6] pro konstrukci suffixových polí v lineárním čase. Jako hlavní výsledek ukážeme, že pro textová data použití slabik nebo slov jako abecedy zlepšuje čas běhu i kompresní poměr.
|
|
Konstrukční algoritmy pro sufixové datové struktury
Šedek, Jindřich ; Dvořák, Tomáš (vedoucí práce) ; Senft, Martin (oponent)
Directed Acyclic Word Graph (DAWG) je prostorově úsporná datová struktura, která slouží k ukládání přípon řetězců. Compact Directed Acyclic Word Graph (CDAWG) je ještě úspornější variantou DAWG. Jejich hlavní uplatnění je v hledání vzorků uvnitř rozsáhlých řetezců. Tato práce je zaměřena na implementaci několika známých konstrukčních algoritmů těchto datových struktur. Otestoval jsem je na různé druhy vstupních dat a porovnal jejich vlastnosti. Konkrétně jsem se zajímal o Blumerův algoritmus na konstrukci DAWG [1], Crochemorův algoritmus na konstrukci CDAWG [2] a Inenagův algoritmus na konstrukci CDAWG [3].
|
|
Vytěžování databáze Poradny pro poruchy metabolismu
Senft, Martin ; Ivánek, Jiří (vedoucí práce) ; Musil, Vladimír (oponent)
Tato práce aplikuje data miningovou metodu rozhodovacích pravidel na data z Poradny pro poruchy metabolismu Fakultní nemocnice Plzeň. Jako nástroj slouží systém LISp-Miner, vyvinutý na VŠE Praha. Nalezená rozhodovací pravidla jsou zhodnocena s odborníkem. Základní části této práce jsou: souhrn hlavních data miningových metod a metod pro hodnocení výsledků. Dále pak popis aplikace data minigu a popis a zhodnocení výsledků.
|
|
Kompaktní sufixový automat v posuvném okně
Filip, Ondřej ; Dvořák, Tomáš (vedoucí práce) ; Senft, Martin (oponent)
Kompaktní sufixový automat (CDAWG) je prostorově šetrnější variantou datové struktury pro indexaci slov zvané sufixový strom. Cílem této práce je implementace algoritmů pro CDAWG v posuvném okně a porovnání jejich vlastností. Posuvné okno je výhodné v případech, kdy není možné v paměti udržovat indexovou strukuturu pro celá indexovaná data. Jeden přesný posun okna je možné provést v čase lineárním k délce okna. Rovněž existuje aproximativní algoritmus vyžadující pro posun okna pouze konstantní čas. Korektnost tohoto algoritmu ovšem byla v této práci vyvrácena.
|
|
Trenažér Mariáše
Malý, Dominik ; Senft, Martin (vedoucí práce) ; Bílý, Tomáš (oponent)
Mariáš je pravděpodobně nejznámější a nejoblíbenější karetní hrou v Čechách a přitom zůstává téměř výhradně výsadou našich luhů a hájů. V této práci studujeme, jakým způsobem je možné tuto zajímavou hru implementovat v řeči jedniček a nul výpočetních zařízení. Je zde také stručně popsán vývoj algoritmů pro implementaci her s úplnou informací a nulovým součtem, od stařičkého minimaxu, přes alfa-beta prořezávání až k mému vlastnímu upravenému negamaxu - algoritmu pro hry s neúplnou informací, používajícímu obecnější postup, který by teoreticky mohl být rozšiřitelný na všechny existující i neexistující karetní hry.
|
|
Vytěžování databáze Poradny pro poruchy metabolismu
Senft, Martin ; Ivánek, Jiří (vedoucí práce) ; Musil, Vladimír (oponent)
Tato práce aplikuje data miningovou metodu rozhodovacích pravidel na data z Poradny pro poruchy metabolismu Fakultní nemocnice Plzeň. Jako nástroj slouží systém LISp-Miner, vyvinutý na VŠE Praha. Nalezená rozhodovací pravidla jsou zhodnocena s odborníkem. Základní části této práce jsou: souhrn hlavních data miningových metod a metod pro hodnocení výsledků. Dále pak popis aplikace data minigu a popis a zhodnocení výsledků.
|
|
Suffix Graphs and Lossless Data Compression
Senft, Martin ; Dvořák, Tomáš (vedoucí práce) ; Dvorský, Jiří (oponent) ; Smyth, William F. (oponent)
Název práce: Sufixové grafy a bezeztrátová komprese dat Autor: Martin Senft Katedra: Katedra software a výuky informatiky Vedoucí doktorské práce: doc. RNDr. Tomáš Dvorˇák, CSc., Katedra software a výuky informatiky Abstrakt: Sufixový strom a prˇíbuzné datové struktury umožnˇují asymptoticky optimálneˇ rěšit rˇadu úloh o rětežcích a jejich vlastností lze též využít k imple- mentacimetodbezztrátovékompresedat. Cílemprácejeprozkoumatmožnosti opacňéhoprˇístupu,tedy využití vlastností sufixovýchgrafu˚ k návrhukompres- ních algoritmu˚. Práce popisuje univerzální konstrukcňí algoritmus pro sufixo- vý trie,sufixový strom,DAWGa CDAWG,doprovázený analýzousimulaceim- plicitních sufixových hran, která prˇináší dveˇ praktické alternativy k tradicňímu rěšení. Protožekompresnímetody vyžadují udržování textuvposuvnémokneˇ, je trěba rozebrat chování sufixových grafu˚ v této situaci. V práci je oveřěno, že pouze sufixový strom je schopen udržovat posuvné okno v amortizovaneˇ kon- stantním cˇase, zatímco CDAWG (podobneˇ jako DAWG) vyžaduje cˇas úmeřný délce okna, což rěší hypotézu Inenagy a kol. Na tomto základeˇ je popsána trˇí- da kompresních algoritmu˚, založených pouze na popisu konstrukce sufixové- ho grafu nad komprimovaným textem. Zatímco neˇkteré z algoritmu˚ odpoví- dají klasickým slovníkovým cˇi kontextovým...
|
|
Kompaktní sufixový automat v posuvném okně
Filip, Ondřej ; Dvořák, Tomáš (vedoucí práce) ; Senft, Martin (oponent)
Kompaktní sufixový automat (CDAWG) je prostorově šetrnější variantou datové struktury pro indexaci slov zvané sufixový strom. Cílem této práce je implementace algoritmů pro CDAWG v posuvném okně a porovnání jejich vlastností. Posuvné okno je výhodné v případech, kdy není možné v paměti udržovat indexovou strukuturu pro celá indexovaná data. Jeden přesný posun okna je možné provést v čase lineárním k délce okna. Rovněž existuje aproximativní algoritmus vyžadující pro posun okna pouze konstantní čas. Korektnost tohoto algoritmu ovšem byla v této práci vyvrácena.
|