Závěrečné práce

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

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

RNDr. Ondřej Suchý, Ph.D.

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

Katedra teoretické informatiky

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

V této práci analyzujeme několik otevřených problémů v oblasti nestranných i stranných her typu Taking and Breaking. Pro nestranné odčítací hry dokážeme existenci hry s aperiodickou nim-sekvencí a periodickou sekvencí výhra-prohra. Analyzujeme ekvivalenční třídy těchto her a nalézáme řešení jedné z těchto tříd. Také představujeme novou hru typu Taking and Breaking, kterou z velké části vyřešíme. V oblasti stranných her provedeme analýzu několika odčítacích her a her typu Pure Breaking. Pro tyto hry také představíme obecnou techniku testování aritmetické periodicity. Pro automatické řešení nestranných her typu Taking and Breaking navrhujeme několik algoritmů. Práci uzavíráme důkazem PSPACE-těžkosti nestranné zobecněné odčítací hry a EXPTIME-těžkosti této hry ve stranné variantě.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

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

Katedra teoretické informatiky

Je-li dán vážený graf a podmnožina jeho vrcholů zvaných terminály, problém Steinerova stromu spočívá v nalezení souvislého podgrafu s nejmenší váhou, který obsahuje všechny terminály. Jedná se o známý NP-těžký problém, který nalézá užití kupříkladu v návrhu integrovaných obvodů, nebo počítačových a dopravných sítích. V této práci rozebereme algoritmus od Dreyfuse a Wagnera, od Ericksona, Monmy a Veinotta, a Nederlofův algoritmus, které řeší verzi tohoto problému parametrizovanou počtem terminálů, a algoritmus využívající dynamické programování a matici řezů pro parametrizaci dle stromové šířky. Pro všechny popsané algoritmy vytvoříme optimalizovanou implementaci a pro porovnání s jinými řešeními ukážeme její výsledky v soutěži PACE 2018.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Problém zvaný d-Path Vertex Cover, d-PVC spočívá v nalezení podmnožiny F vrcholů daného grafu G=(V,E) takové, že G \ F neobsahuje žádnou cestu na d vrcholech. Cesty, které chceme takto podchytit, nemusí být indukované. Je známo, že problém d-PVC je NP-úplný pro každé d >= 2. Dále je známo, že problém 5-PVC parametrizovaný velikostí řešení k je řesitelný v čase O(5^k*n^O(1)). V této práci přicházíme s algoritmem používající iterativní kompresi, který řeší problém 5-PVC v čase O(4^k*n^O(1)).

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Tato práce popisuje řešení problému izomorfismu podgrafů pomocí techniky barevného kódování. V práci je popsán problém izomorfismu podgrafů, jeho varianty a jeho aplikace. Dále je rozebrán problém tvorby hezkého stromového rozkladu optimální šířky pro zadaný graf, jelikož takováto struktura je pro daný přístup vyžadována. Jako hlavní část práce je popsáno několik modifikací a optimalizací původního algoritmu založeného na barevném kódování. Praktickým výsledkem práce je modul implementovaný v jazyce C, který je navržen pro řešení velkých instancí problému izomorfismu podgrafů včetně výpisu nalezených výsledků.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

Tato práce studuje takzvané vzorky v sítích. Vzorky v sítích jsou souvislé podgrafy v dané síti, které se vyskytují ve výrazně vyšších četnostech, než je očekávané v náhodných sítích. Jsou popsány různé přístupy pro hledání vzorků v sítích a na základě jejich analýzy je představen nový, vylepšený, paralelní algoritmus pro hledání vzorků v sítích, nazvaný Efise. Praktické výsledky ukazují, že Efise nabízí výrazně vyšší výkonnost než ostatní nástroje. Díky efektivní metodě paralelizace dosahuje Efise lineárního zrychlení a dokáže hledat vzorky v sítích řádově rychleji než doposud nejrychlejší nástroje.

Práce na DSpace