|
|
Algoritmy konstrukce sufixových stromů
Host, Ján ; Majerech, Vladan (oponent) ; Senft, Martin (vedoucí práce)
V predloženej práci študujeme algoritmy pre výstavbu dátovej štruktúry sufixový strom. Táto štruktúra pomáha optimálne riešiť mnoho problémov z oblasti spracovávania textu. Existuje hneď niekoľko prístupov a algoritmov, ako ju postaviť. Cieľom je vytvoriť taxonómiu algoritmov konštruujúcich sufixové stromy a poskytnúť tak prehľad v ich vlastnostiach a použiteľnosti. Algoritmy doležité z roznych hľadísk sú prezentované, je vysvetlený princíp a myšlienka ich práce. Nasledovne sa porovnajú v testoch a odhalia sa ich prínosy a úskalia. Z výsledkov testov, ale aj teoretických znalostí a znalostí z naštudovanej literatúry, sú zistené spoločné znaky algoritmov a po predložení vhodných kritérií je vytvorená ich taxonómia.
|
|
|
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.
|
|
|
Moderní metody fraktální komprese obrazu
Čunát, Vladimír ; Senft, Martin (oponent) ; Dvořák, Tomáš (vedoucí práce)
V předložené práci studujeme metody fraktální komprese obrazu. Jsou zde rozebrány základní používané techniky, publikovaná rozšíření a jsou navržena a implementována drobná vylepšení stávajících metod. Dále je představen modulární systém umožňující vyměřování různých variant jednotlivých částí kompresního procesu a zjednodušující tak porovnání účinnosti různých algoritm. Nově navržená vylepšení jsou vyhodnocena na testovacích obrázcích. Pedstavená penalizační metoda dosahuje vyšších kvalit dekomprimovaných obrázků. Diferenční kódování v kombinaci s přeuspořádáním cílových blok snižuje nároky na prostor okolo 5%. Predikce implementovaná pomocí KD-stromů se naopak ukázala jako nepříliš účinná v porovnání s článkem používajícím jinou datovou strukturu.
|
|
|
Konstrukční algoritmy pro sufixové datové struktury
Šedek, Jindřich ; Senft, Martin (oponent) ; Dvořák, Tomáš (vedoucí práce)
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].
|
|
|
Trenažér Mariáše
Malý, Dominik ; Bílý, Tomáš (oponent) ; Senft, Martin (vedoucí práce)
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.
|
|
|
Algoritmy nad rozšířeným sufixovým polem
Šedek, Jindřich ; Senft, Martin (oponent) ; Dvořák, Tomáš (vedoucí práce)
Su fixový strom je v oblasti efektivních řešení vyhledávacích problémů jednou z nejdůležitějších datových struktur. Hlavní nevýhodou sufixového stromu je jeho prostorová složitost. Sufixové pole je naproti tomu prostorově úsporná datová struktura, která však nemá tak široké aplikace. Aby bylo možné využít sufi xové pole v pokročilejších aplikacích, je nutné jej rozšířit dalšími pomocnými informacemi. Tato práce je zaměřna na experimentální srovnání rozšířeného sufi xového pole se sufi xovým stromem ve vybraných aplikacích z hlediska časové a prostorové složitosti.
|
|
|
Suffix Array for Large Alphabet
Šesták, Radovan ; Senft, Martin (oponent) ; Lánský, Jan (vedoucí práce)
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.
|
|
|
Algorithm Visualisation
Vranec, Maroš ; Kučera, Luděk (oponent) ; Senft, Martin (vedoucí práce)
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ť.
|
host ::
RSS.