Závěrečné práce

doc. RNDr. Dušan Knop, Ph.D.

Mgr. Michal Opler, Ph.D.

Katedra teoretické informatiky

Tato práce se zabývá hledáním vítěze ve volbách komisí. Poskytujeme přehled volebních systémů pro single-winner a multi-winner volby. Hledání vítěze je často výpočetně náročné, proto zavádíme volby se strukturovanými preferencemi. Ve volbách se strukturovanými preferencemi jsou hlasy voličů nějakým způsobem omezené, což může usnadnit vytváření efektivnějších algoritmů pro hledání vítěze. Popisujeme některé ze známých strukturovaných preferencí. Poskytujeme přehled současné literatury týkající se strukturovaných a téměř strukturovaných preferencí. Zkoumáme současné práce týkající se volby komisí se strukturovanými preferencemi a použití ordered weighted average (OWA) ve volbách komisí. Představujeme polynomiální algoritmy pro hledání vítězných komisí v approval volbách s OWA vektorem (0, ..., 0, 1) a intervalově omezenými voličskými preferencemi. V takových volbách, volič schvaluje komisi pouze pokud schvaluje všechny její členy. Tuto vlastnost používáme a ukazujeme dva přístupy pro hledání výherní komise.

Práce na DSpace

doc. Ing. Filip Křikava, Ph.D.

Vitaly Bragilevsky, MSc.

Katedra teoretické informatiky

Haskell je jeden z nejznámějších jazyků s non-strict sémantikou. Na jednu stranu přináší tato sémantika pohodlí nekonečných datových struktur, řídících konstrukcí definovaných uživatelem a možnost vyhnout se nepotřebným výpočtům. Na stranu druhou jsou tyto výhody postiženy daní na výkonu za běhu programu a těžko předvídatelným chováním call-by-need. Nabízí se otázka: Vyplatí se líná evaluace? K zodpovězení této otázky musíme porozumět tomu, jak je lenost využívána v praxi. K tomuto účelu jsme vyvinuli nástroj pro dynamickou analýzu použitelný k trasování evaluace funkčních parametrů. Je implementován jako zásuvný modul kompilátoru Glasgow Haskell Compiler.

Práce na DSpace

doc. RNDr. Dušan Knop, Ph.D.

Ing. Václav Blažej, Ph.D.

Katedra teoretické informatiky

Problém stabilních spolubydlících s podmínkami různorodosti spočívá v rozdělení agentů dvou typů do koalic pevné velikosti na základě jejich preferencí, které závisí pouze na počtu agentů stejného typu. V této práci se zabýváme stabilitou takových rozdělení v závislosti na velikosti koalice a struktuře preferenčních profilů agentů. Snažíme se uchopit problém v celé jeho šíři a vytvořit nadhled nad celou problematikou představením Hedonických her a jejich zajímavých podtříd. Představujeme nový randomizovaný algoritmus na rychlé hledání core stabilních řešení instancí tohoto problému a ukazujeme, jakých výsledků jsme pomocí algoritmu dosáhli. Nalezli jsme malou single-peaked instanci s prázdným core a ověřili jsme, že každá instance tohoto problému, kde velikost koalic = 3, preferenční relace všech agentů jsou single-peaked a počet agentů <= 30, velikost koalic = 3 a počet agentů <= 15, velikost koalic = 4, preferenční relace všech agentů jsou single-peaked a počet agentů = 8, má core stabilní řešení. Předkládáme argumenty, proč se domníváme, že každá instance, kde velikost koalic = 3, velikost koalic = 4 a preferenční relace všech agentů jsou single-peaked, má core stabilní řešení.

Práce na DSpace

doc. RNDr. Pavel Surynek, Ph.D.

MSc. Juan Pablo Maldonado Lopez, Ph.D.

Katedra teoretické informatiky

V tejto práci sa venujeme otázke evakuácie z budov alebo priestranstiev z perspektívy algoritmov na kooperatívne hľadanie ciest. Definujeme problém na zvaný multi-agentná evakuácia, ktorý sa skladá z neorientovaného grafu, v ktorého vrcholoch sa nachádzajú agenti (napríklad ľudia, roboty alebo postavy v počítačovej hre). Vrcholy v grafe sú označené ako ohrozené alebo bezpečné a úlohou je naplánovať presun agentov z ohrozených do bezpečných vrcholov v čo najkratšom čase. Existujú centralizované algoritmy založené na modelovaní tokov v sieťach, ktoré dokážu tento problém riešiť optimálne vzhľadom na rôzne ukazovatele. V reálnom svete sa však tieto algoritmy dajú aplikovať len problematicky, pretože skutoční agenti nie sú schopní nasledovať centrálne generovaný plán a musia reagovať na meniace sa situácie, ako napríklad nekooperujúcich agentov. Preto sme navrhli a implementovali algoritmus na plánovanie evakuácie založený na technikách lokálneho kooperatívneho hľadania ciest. Simulácie na viacerých realistických situáciách ukazujú, že riešenia generované týmto algoritmom majú kvalitu podobnú riešeniam z centralizovaných algoritmov.

Práce na DSpace

doc. Ing. Ivan Šimeček, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Editační vzdálenost lze vypočítat s obecně známým algoritmem využívajícím dynamické programování v čase O(n^2), kde n je délka vstupních řetězců. Algoritmus Čtyř Rusů zlepšuje tuto složitost s pomocí vyhledávací tabulky o faktor (log(n))^2. V této práci je tento algoritmus podrobně prozkoumán a důležité implementační detaily jsou prodiskutovány, přičemž zvláštní ohled je brán na paralelizování algoritmu a zmenšení velikosti vyhledávací tabulky. Implementace v jazyce C++ je poskytnuta a její výkon je porovnán v několika experimentech s populární knihovnou na výpočet editační vzdálenosti. Výsledky naznačují, že algoritmus je v praxi použitelnou volbou, ale není optimální.

Práce na DSpace

RNDr. Petr Štěpán, Ph.D.

doc. RNDr. Pavel Surynek, Ph.D.

Katedra teoretické informatiky

Práce se zabývá využitím konvolučních neuronových sítí pro detekci známého objektu ve videu s ohledem na zpracování dat v reálném čase. Poskytuje úvod do strojového učení, neuronových sítí a jejich implementace v programovacím jazyce Python a přehled nejmodernějších technologií využívaných pro detekci objektů v obraze. Dále se zabývá návrhem několika architektur, vytvořením a zpracováním dvou různých datasetů, měřením a zhodnocením navržených architektur.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

V této práci studujeme problém věčné dominace grafu, který je známý pod názvem m-eternal domination problem. Je zadán graf G a na vrcholy G umístíme ochránce. Následně jsou na vrcholy postupně vedeny útoky. Po každém útoku se musí nějaký ochránce přesunout na ohrožený vrchol. Každý vrchol smí okupovat nejvýše jeden ochránce. Nejmenší počet ochráců, který ochrání G, značíme g[?]m(G). Zabýváme se kaktusovými grafy G takovými, že každá hrana v G je na cyklu o velikosti 3k + 1 pro nějaké k [?] N. Ukazujeme, že pro každé takové G na n vrcholech platí g[?]m(G) = 1 + (n [?] 1)/3. Představujeme problém m-eternal guard configuration, který je stejný jako m-eternal domination problem, ale povoluje více ochránců na jednom vrcholu. Nejmenší nutný počet ochránců pro graf G označujeme jako G[?]m(G). Popisujeme lineární algoritmus pro výpočet G[?]m(G) v kaktusových grafech, kde každá artikulace je ve dvou blocích. Navíc předkládáme lineární algoritmus pro výpočet g[?]m(G) v klikových stromech. Přikládáme implementaci v C++ těchto algoritmů spolu s exponenciálním algoritmem, který řeší oba problémy v obecných grafech.

Práce na DSpace

Ing. Tomáš Čejka, Ph.D.

Ing. Viktor Černý

Katedra teoretické informatiky

Monitorování síťového provozu je nezbytnou součástí správy dnešních počítačových sítí. Získané informace slouží nejen k zajištění základní funkcionality a včasné detekování potenciálních problémů, ale především k bezpečnostní analýze. Z důvodu soukromí uživatelů a snížení objemu sbíraných dat je dnes standardem agregace provozu do tzv. síťových toků. Tato práce se zabývá otázkou exportu síťových toků s rozšířením o informace z aplikačních vrstev. Výsledkem práce je rozšíření a vylepšení open source exportéru toků z projektu NEMEA. Tento softwarový modul byl po optimalizacích původního kódu úspěšně portován na platformu vestavných zařízení se systémem OpenWrt. Díky tomuto přínosu je možné vytvořit monitorovací sondu i z nevýkonných levných domácích směrovačů a zvýšit tak přehled o provozu na síti včetně detekce škodlivého provozu. Mimo paměťových a výkonnostních optimalizací vnitřních struktur je modul rozšířen o možnost číst pakety ze síťového rozhraní pomocí knihovny libpcap. Vnitřní struktura pro ukládání toků, flow cache, je upravena pro ukládání informací z aplikačních protokolů. Použití tohoto rozšíření je demonstrováno na dvou vytvořených ukázkových parsovacích pluginech pro HTTP a DNS provoz. Exportér je díky této práci schopen exportovat toky ve formátu IPFIX.

Práce na DSpace

Ing. Tomáš Čejka, Ph.D.

Katedra teoretické informatiky

Zpracování nahlášených bezpečnostních incidentů je poměrně obtížný úkol, který zahrnuje analýzu velkého množství událostí a dohledání dodatečných informací. Jedním z nástrojů pracujících s přijatými bezpečnostními incidenty, je Network Entity Reputation Database (NERD) vyvíjený a provozovaný sdružením CESNET, který na základě detekovaných událostí shromažďuje potenciálně škodlivé síťové entity a dohledává o nich relevantní informace. Tato bakalářská práce se zabývá rozšířením NERDu o získání dalších užitečných informací o entitách a realizací automatické klasifikace entit podle podstaty jejich chování. Hlavním přínosem práce je návrh a implementace modulu na klasifikaci entit pomocí konfigurovatelných klasifikačních pravidel. Vytvořené funkční a otestované řešení bylo nasazeno do produkční instance systému NERD používané členy bezpečnostních týmů.

Práce na DSpace

Mgr. Jan Starý, Ph.D.

Ing. Radek Richtr, Ph.D.

Katedra teoretické informatiky

Cílem této práce je vytvoření programu, který bude na základě požadavku uživatele generovat odpovídající molekuly. Program za pomoci genetického algoritmu vytváří z uživatelem dodané databáze populace nových molekul, které jsou následně ohodnoceny virtuálním screeningem - softwarem pro určení vhodnosti dané molekuly podle uživatelského zadání. Byla vybrána vhodná reprezentace molekuly a navrženy příslušné genetické operátory křížení a mutace. Výsledkem je sada unixových programů provádějící jednotlivé úkony genetického algoritmu. Výsledný program umožňuje ze zadání pro virtuální screening a vstupní databáze molekul vygenerovat rozsáhlou sadu molekul odpovídající zadaným požadavkům.

Práce na DSpace

Ing. Jan Bělohoubek

Ing. Miroslav Skrbek, Ph.D.

Katedra teoretické informatiky

Práce se zabývá validací kódů pro jednoduché vestavné systémy. Nejprve popisuje současné pokrytí relevantní podmnožiny standardu CERT C Secure Coding Standard v dostupných nástrojích. V praktické části pak popisuje implementaci kontrol některých pravidel standardu, která dosud nebyla dostatečně pokryta volně dostupnými nástroji, v novém rozšiřitelném nástroji založeném na knihovně LibTooling překladače Clang. Na zdrojových kódech skutečných projektů je pak demonstrována účinnost nástroje objevením konstrukcí, které s velkou pravděpodobností mohou vést k chybě.

Práce na DSpace