|
|
Pattern matching in compilers
Bílka, Ondřej ; Hubička, Jan (vedoucí práce) ; Mareš, Martin (oponent)
Název práce: Pattern matching in compilers Autor: Ondřej Bílka Katedra: Katedra Aplikované Matematiky Vedoucí diplomové práce: Jan Hubička, Katedra Aplikované Matematiky Abstrakt: V této práci vyvineme nástroje na efektivní a flexibilní pattern matching. Představíme specializovaný programovací jazyk amethyst. Jedna z funkcí amethystu je generatování parserů. Také může sloužit jako alterna- tiva k regulárním výrazum. Naš systém umí generovat dynamické parsery. Jejich hlavní uplatnění je tvorba nástroju do IDE jako např. interaktivní zvýrazňovač syntaxe nebo detektor chyb. Amethyst umí zpracovávat i obecné datové struktury. Plánované využití je implementace kompilátorových optimal- izací jako napřiklad propagace konstant či rozvrhování instrukcí a jiné optimal- izace založené na dataflow analyze. Generované parsery jsou víceméně top-down parsery. Představíme nový algo- ritmus pro parsovaní strukturovaných gramatik v linearním čase. Amethyst používá techniky z kompilatorů pro optimalizovaní generovaných parserů. Klíčová slova: packrat parsování, dynamické parsování, strukturované gramatiky, funkcionální programování 1
|
|
|
Anotující disassembler
Hluzín, Petr ; Mareš, Martin (vedoucí práce) ; Holub, Viliam (oponent)
V této práci byl vyvinut dissambler pro monolitické mikroprocesory (mikrořadiče) Microchip PIC. Tento dissambler u typických programů staticky určí hodnotu za běhu nastavovaných logických registrů čímž z neúplné adresy v instrukci získá úplnou adresu. Na jejich základě pak rozpozná procedury, vytvoří graf volání procedur a rozpozná řídící struktury. Disassembler oddělí použití registru pro proměnné více procedur a roztřídí na vstupy procedury, lokálně modifikované proměnné a návratové proměnné. Současné disassemblery této architektury se omezují na tisk instrukcí s núplnými adresami, protože analýzy neprovádějí. Powered by TCPDF (www.tcpdf.org)
|
|
|
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.
|
|
|
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).
|
|
|
Vizualizační algoritmy pro grafy
Kuča, Tomáš ; Valla, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
Tato práce studuje současné algoritmy pro kreslení grafů. Zaměřuje se především na rovinné grafy, ale rozebírá i několik algoritmů pro nerovinné grafy a metody, které umožňují převádět nerovinné grafy na rovinné. Navrhuje rozšíření algoritmu pro kreslení se stejným obsahem vnitřních stěn, které zohledňuje velikost úhlů. Popisuje, jak lze využít algoritmus pro hledání maximální nezávislé množiny na průsekových grafech při planarizaci. V závěru je představen zásuvný modul pro gra cký editor VRR, který byl vyvinut pro testování algoritmů.
|
|
|
Persistentní datové struktury
Kupec, Martin ; Mareš, Martin (vedoucí práce) ; Straka, Milan (oponent)
V této práci studujeme persistentní datové struktury, tedy takové, které si uchovávají svou historii změn. Zabýváme se zejméena strukturami založenými na ukazatelích, pro něž lze dosáhnout plné, a tedy i částečné persistence s amortizovaně konstantním časem i prostorem na operaci. Popisujeme také zpersistentnění polí, u nějž je existence optimální struktury nadále otevřena. Uvádíme těž konkrétní aplikace obecných zpersistentňovacích postupů a příklady použití persistentních struktur.
|
|
|
Hledání shluků v grafech
Navrátil, Jan ; Lidický, Bernard (vedoucí práce) ; Mareš, Martin (oponent)
Cílem práce je vytvořit aplikaci, která dokáže hledat shluky v grafech. Aplikace obsahuje na výběr několik modifikovaných algoritmů klasické shlukové analýzy a grafových algoritmů využívaných pro detekci komunit v komplexních sítích. Účelem práce není optimalizace implementace na rychlost ale možnost vyzkoušení a porovnání výsledků jednotlivých algoritmů a ověření, jestli jsou specializované grafové algoritmy skutečně vhodnější. Jádrem úkolu bylo tedy modifikovat algoritmy shlukové analýzy (byly vybrány čtyři, s řadou kombinovatelných nastavení) pro práci nad grafy a společně s algoritmy hledajícími komunity v sítích (dva, oba ve více variantách) je implementovat a prezentovat v rámci jedné aplikace.
|
|
| |
|
|
Hybridní databáze
Hušek, Radek ; Mareš, Martin (vedoucí práce) ; Lokoč, Jakub (oponent)
Tato práce popisuje návrh a implementaci datové struktury, která se snaží kombinovat výhody databází a běžných datových struktur. Ze světa databází vychází především pod- pora pro persistenci dat prostřednictvím jejich uložení na disku a práce s daty pomocí transakcí, které umožňují paralelní přístup při zajištění konzistence dat. Od datových struktur naopak přichází implementace v podobě knihovny funkcí a snaha o maximální jednoduchost a uložení dat v paměti. Navržená databáze staví na konceptu transakční paměti a data jsou na disku ukládána ve formě záznamu provedených operací. 1
|
|
|
Nowhere-dense classes of graphs
Tůma, Vojtěch ; Dvořák, Zdeněk (vedoucí práce) ; Mareš, Martin (oponent)
V této práci se zabýváme řídkými třídami grafů a jejich vlastnostmi využitelnými pro návrh algoritmů a datových struktur. Speciálně se zaměřujeme na nedávno zavedené koncepty omezené expanse a stromové hloubky, které zavedli J. Nešetřil a P. Ossona de Mendez. V této práci nejprve podáme stručný úvod do prob- lematiky a shrneme důležité výsledky a nástroje z parametrisované složitosti a algoritmické teorie modelů. Hlavní část této práce, aplikace teoretických poznatků, přináší dva nové výsledky z oblasti dynamických datových struktur. První slouží k udržování dekomposice grafu s omezenou stromovou hloubkou, druhá počítá výskyty zadaného podgrafu v udržovaném grafu. Časová i prostorová složitost operací obou struk- tur je při použití na řídké třídy grafů nízká. 1
|
host ::
RSS.