|
|
Nové struktury a operace v matematické informatice
Bureš, Richard ; Krčmář, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Cílem této práce je podívat se na některé známé a na některé v této práci vytvořené operace a na jejich vlastnosti nad především regulárními, ale i bezkontextovými jazyky. Dále si zde ukážeme, jak je možné takové operace provádět nad konečnými a zásobníkovými automaty a nakonec také jak je možné tyto automaty a operace nad nimi implementovat.
|
|
|
Computational Bounded Rationality
Černý, Jakub ; Loebl, Martin (vedoucí práce) ; Hladík, Milan (oponent)
Tato závěrečná práce formalizuje model omezené racionality hráčů v sekvenčních hrách nazvaný herní schémata. Ve zkoumaném modelu jsou strategie reprezentované strukturou skládající se z konečného automatu a dvou výpočetních funkcí. Zatímco konečný automat reprezentuje hráčovu strukturovanou pamět', výpočetní funkce reprezentují jeho schopnost efek- tivně abstrahovat danou hru. Schémata jsou realizacemi čistých strategií a mohou být hráčem implementovány za účelem hraní sekvenční hry. Práce ukazuje jak zkonstruovat korektně hrající schéma pro jakoukoli strategii v jakékoli sekvenční hře s vícero hráči a jak určit jeho složitost. Dokazuje, že ekvilibrium vždy existuje a jeho výpočet je PPAD-těžký. Navíc práce defin- uje třídu efektivně reprezentovatelných strategií, pomocí které lze spočítat MAXPAY-EFCE v polynomiálním čase. 1
|
|
|
Knihovna pro konečné automaty a převodníky
Bieliková, Michaela ; Lengál, Ondřej (oponent) ; Hruška, Martin (vedoucí práce)
Konečné automaty majú široké uplatnenie v informatike, okrem iných vo formálnej verifikácii, modelovaní systémov a spracovaní prirodzeného jazyka. Avšak modely skutočne reprezentujúce realitu bývajú veľmi komplikované a môžu byť definované nad veľkými, v niektorých prípadoch až nekonečnými, abecedami, a teda môžu obsahovať veľký počet prechodov. V týchto prípadoch nemusí byť je použitie algoritmov na prácu s konečnými automatmi efektívne. Symbolické automaty poskytujú stručnejší zápis tak, že namiesto symbolov v prechodoch používajú predikáty. Konečné prevodníky tiež majú široké uplatnenie, od ligvistiky až po formálnu verifikáciu. Symbolické prevodníky nahradzujú symboly dvojicou predikátov - jeden predikát pre vstupné symboly a jeden pre výstupné. Cieľom tejto práce je návrh knižnice pre klasické a symbolické automaty a prevodníky, ktorá bude vhodná na rýchle prototypovanie nových algoritmov.
|
|
|
Efektivní funkcionální knihovna pro konečné automaty
Říha, Jakub ; Hruška, Martin (oponent) ; Lengál, Ondřej (vedoucí práce)
Konečné automaty jsou důležitou matematickou abstrakcí. Ve formální verifikaci se konečné automaty používají ke stručné reprezentaci regulárních jazyků. V této souvislosti se používají operace nad konečnými automaty, jako je testování jazykové univerzality a inkluze. Naivní přístup k implementaci těchto operací vede k explicitní determinizaci konečného automatu, což může být nakladné a nežádoucí. Nicméně existuje pokročilejší metoda k vykonávání těchto operací nazývaná Antichains algoritmus, která se vyhýbá explicitní determinizaci. Tato práce se zabývá efektivní implementací operací nad konečnými automaty v Haskellu a také porovnává několik implementačních variant. Získané výsledky jsou poté porovnány s knihovnou VATA, což je imperativní implementace knihovny pro práci nad konečnými automaty.
|
|
|
Porovnávání jazyků a redukce automatů používaných při filtraci síťového provozu
Havlena, Vojtěch ; Rogalewicz, Adam (oponent) ; Vojnar, Tomáš (vedoucí práce)
Tato práce se zabývá porovnáváním jazyků automatů a redukcí automatů používaných při monitorování síťového provozu. Je navrženo několik přístupů pro přibližnou redukci automatů (nezachovávající jazyk) a přístup pro porovnávání jejich jazyků. Redukce jsou založeny na podaproximaci jazyka automatu, kdy dochází k odstraňování stavů nebo na nadaproximaci jazyka, kdy dochází k přidávání nových smyček (a odstranění zbytečných stavů později). Navržené metody pro přibližnou redukci a navržená pravděpodobnostní vzdálenost využívají informaci ze síťového provozu. Jsou poskytnuty formální záruky vzhledem k modelu síťového provozu, který je reprezentován pravděpodobnostním automatem. Metody byly implementovány a jejich vlastnosti byly ověřeny na automatech používaných pro filtrování síťového provozu.
|
|
|
Využití hierarchických konečných automatů pro popis vzorů chování
Renát, Dušan ; Pergel, Martin (vedoucí práce) ; Holan, Tomáš (oponent)
V předložené práci zavádíme a studujeme hierarchické konečné automaty jako model umělé inteligence autonomních agentů v obecných virtuálních prostředích a systémech. Formálně definujeme pojem hierarchického automatu, analyzujeme jeho výpočetní sílu srovnáním se známými druhy automatů a poukazujeme na možnosti jejího zvýšení. Poté uvádíme nejběžnější přístupy k simulaci inteligentního chování, rozlišujeme přímý a nepřímý popis vzorů chování a představujeme výhody hierarchických automatů coby nástroje pro popis přímý. Zároveň předkládáme knihovnu interpretující tyto automaty vytvořenou jako součást této práce. Demonstrací jejího použití na ukázkovém robotu pro prostředí Robocode ukazujeme, že jsou obecným a použitelným řešením pro takováto nasazení.
|
|
|
Multidimensionální jazyky a jejich automaty
Dibďák, Lukáš ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Práce seznamuje s teorií formálních jazyků a konečných automatů. Popisuje zobecnění této teorie do dvou rozměrů. Představuje základní typy dvoudimensionálních automatů, přede- vším teselační automaty. Pro teselační automaty jsou nabídnuty algoritmy k jejich determinizaci. Jeden z algoritmů je následně používán přiloženou aplikací pro determinizaci.
|
|
|
Generování Content Adressable Delayed DFA z regulárních výrazů
Hammer, Jan ; Dvořák, Milan (oponent) ; Kaštil, Jan (vedoucí práce)
Práce se zabývá konstrukcí rozšířených typů konečných automatů ze sad regulárních výrazů.Hlavní důraz je na rozšíření CD2FA - Content Addressed Delayed Input DFA, které je navrženo k použití při hloubkové analýze paketů v síti, za účelem snížení paměťové náročnosti a zachování rychlosti výpočtu. Nad takto zkonstruovanými automaty jsou zkoumány statistiky paměťové náročnosti, které ukazují, že CD2FA jsou řádově desetkrát méně paměťově náročné, než původní DFA. Dále jsou prezentovány některá vylepšení procesu konstrukce CD2FA, především vylepšení přípravy adresace stavů za použití perfektního hashování.
|
|
|
Detekce narušení počítačové sítě
Hank, Andrej ; Martínek, Tomáš (oponent) ; Kořenek, Jan (vedoucí práce)
Stále rastúce rozšírenie a priepustnosť počitačových sietí prináša mnoho bezpečnostných hrozieb. Jedným z prostriedkov zabezpečenia sú systémy detekcie narušenia (IDS). Nízka priepustnosť softwérových IDS vyúsťuje vo vývoj hardwérových akcelerátorov. Konkrétnym je sonda Traffic Scanner projektu Liberouter využívajúca technológiu FPGA. Jadro akcelerácie spočíva vo vyhľadávaní jednoduchých reťazcov v obsahu paketu. Komplexný popis reťazcov zaručujú regulárne výrazy. Táto práca obohacuje sondu Traffic Scanner o možnosť pokročilého vyhľadávania reťazcov pomocou Perl Compatible Regular Expressions (PCRE) implementovaným transformátorom. Ďalej prináša návrh a implementáciu programového vybavenia umožňujúceho využiť funkcionalitu akcelerátoru užívateľom. Podáva koncepciu detekcie narušenia sieťe s využítím sondy Traffic Scanner a možnosti spolupráce s inými bezpečnostnými zariadeniami.
|
|
|
Simulace kolektivního chování entit ve virtuálním světě
Vymazal, Tomáš ; Žák, Pavel (oponent) ; Láník, Aleš (vedoucí práce)
Tématem této práce je zhodnotit a porovnat možnosti řízení entit (agentů) ve virtuálním světě a jeden vybraný přístup realizovat ve formě programu. Pro implementaci byl vybrán přístup, kdy konečný automat, řídící agenta, podléhá evoluci pomocí genetických algoritmů. Tento přístup by měl přizpůsobit, případně vylepšit agentovo chování tak, aby odpovídalo zadaným požadavkům: zde např. aby se agent naučil težit zdroje ve virtuálním světě. Implementace je realizována pomocí modulu pro běh evoluce a pomocí modulu se 3d zobrazením, kde lze prohlížet chování agentů.
|
host ::
RSS.