Teoretická informatika (verze pro anglické studenty)

Závěrečné práce

Bakalářské práce

Strukturované volby komisí

Autor
Terezie Hrubanová
Rok
2023
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
Mgr. Michal Opler, Ph.D.
Anotace
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.

Dynamické tracovaní Haskellu

Autor
Ondřej Kvapil
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. Ing. Filip Křikava, Ph.D.
Oponenti
Vitaly Bragilevsky, MSc.
Anotace
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.

Stabilita Hedonických her se strukturovanými preferencemi

Autor
Jan Šmolík
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Anotace
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í.

Plánování evakuace založené na lokálních technikách kooperativního hledání cest

Autor
Róbert Selvek
Rok
2019
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Pavel Surynek, Ph.D.
Oponenti
MSc. Juan Pablo Maldonado Lopez, Ph.D.
Anotace
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.

Vícevláknová implementace "Four Russians" algoritmu pro výpočet editační vzdálenosti

Autor
Martin Rejmon
Rok
2019
Typ
Bakalářská práce
Vedoucí
doc. Ing. Ivan Šimeček, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
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í.

Sledování letících dron

Autor
Hynek Davídek
Rok
2018
Typ
Bakalářská práce
Vedoucí
RNDr. Petr Štěpán, Ph.D.
Oponenti
doc. RNDr. Pavel Surynek, Ph.D.
Anotace
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.

Eternal domination na speciálních třídách grafů

Autor
Jan Matyáš Křišťan
Rok
2018
Typ
Bakalářská práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
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.

Exportér síťových toků s podporou aplikačních informací

Autor
Jiří Havránek
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Tomáš Čejka, Ph.D.
Oponenti
Ing. Viktor Černý
Anotace
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.

Automatická klasifikace síťových entit

Autor
Jakub Jančička
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Tomáš Čejka, Ph.D.
Anotace
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ů.

Genetické algoritmy pro generování molekul

Autor
Jonatan Matějka
Rok
2017
Typ
Bakalářská práce
Vedoucí
Mgr. Jan Starý, Ph.D.
Oponenti
Ing. Radek Richtr, Ph.D.
Anotace
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.

Validátor zdojových kódů pro vestavné systémy

Autor
Jakub Šimek
Rok
2017
Typ
Bakalářská práce
Vedoucí
Ing. Jan Bělohoubek
Oponenti
Ing. Miroslav Skrbek, Ph.D.
Anotace
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ě.

Za obsah stránky zodpovídá: Ing. Zdeněk Muzikář, CSc.