Grafy, hry, optimalizace, algoritmy, teoretická informatika (G²OAT)

Závěrečné práce

Bakalářské práce

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.
Oponenti
Ing. Václav Blažej
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í.

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.

FPT Algoritmy vícedimenzionálního párování

Autor
Jakub Puchýř
Rok
2014
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.

Diplomové práce

Kombinatorické hry typu Taking and Breaking

Autor
Šimon Lomič
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Anotace
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ě.

Parametrizované algoritmy pro Steinerovské stromy

Autor
Peter Mitura
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
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.

Podchycování cest v grafech

Autor
Radovan Červený
Rok
2018
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
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)).

Algoritmus pro hledání podgrafu založený na barevném kódování

Autor
Josef Malík
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
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ů.

Paralelní vyhledávání repetic v grafech

Autor
Jiří Stránský
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
RNDr. Ondřej Suchý, Ph.D.
Anotace
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.

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.