Ing. Šimon Schierreich

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

Katedra aplikované matematiky

Zabýváme se studiem strategických her, které jsou inspirovány Schellingovým segregačním modelem. V těchto hrách zkoumáme, jak se agenti, rozdělení do několika typů, pohybují na neorientovaných grafech. Bereme v potaz dva typy agentů: strategické agenty, kteří se snaží o maximální počet sousedů stejného typu a neústupné agenty, kteří se vůbec nepohybují. V~naší práci zkoumáme dvě nejčastější varianty tohoto modelu, které se rozlišují pohybem strategických agentů. Strategičtí agenti mají k dispozici dva druhy pohybů: skok a výměnu. Na těchto hrách zkoumáme výpočetní složitost a zvýšení sociálního blahobytu při~zvážení sousedů i neústupných agentů. Dále představujeme nový způsob detekce maximálního sociálního blahobytu v ekvilibriu za pomoci grafových neuronových sítí.

Práce na DSpace

Mgr. Michal Opler, Ph.D.

Katedra teoretické informatiky

Problém Maximum Betweenness Centrality spočívá ve výběru skupiny úzlů uživateli zadané velikosti ze sociální sítě tak, abychom maximalizovali pravděpodobnost zachycení komunikace probíhající po nejkratších cestách v rámci sítě. Tento problém je významný pro výzkum sítí modelujících komunikace. Byť Maximum Betweenness Centrality je poměrně probádáný v kontextu klasické složitosti, jeho parametrizováná složitost představovala dosavaď nezdupanou půdu. Tento nedostatek doplníme multivarietní analýzou. Ukázujeme, že Maximum Betweenness Centrality je W[1]-těžký parametrizován velikostí skupiny. Tento výsledek doplňujeme dolní mezí f(b) * n^o(b) pro algoritmy pro Maximum Betweenness Centrality parametrizován velikostí skupiny b, za předpokladu, že platí ETH. Oproti tomu ukazujeme že Maximum Betweenness Centrality je v FPT když je parametrizován buďto parametrem vertex cover number, distance to clique a velikostí skupiny, nebo twin cover number a velikostí skupiny.

Práce na DSpace

Ing. Magda Friedjungová, Ph.D.

Katedra aplikované matematiky

Tato bakalářská práce se zabývá detailním vysvětlením skupinových měr centralit, což je jedna z technik analýzi grafů sítí. Jednotlivé míry jsou zde popsány z hlediska využití a také vysvětleny pricipy algoritmů na zjištění těchto měr. Na reálných datasetech sociálních sítí jsou naměřeny jednotlivé míry a k těmto výsledkům je vedena diskuze.

Práce na DSpace

RNDr. Jiřina Scholtzová, Ph.D.

Katedra teoretické informatiky

V této práci poskytujeme úvod do problematiky skrytých sítí (covert networks) a jejich analýzy, s důrazem na problém Hiding Leaders, který zkoumáme s ohledem na míru centrality měřenou stupněm uzlu (degree centrality) a pomocí frameworku parametrizované výpočetní složitosti. Analyzujeme výsledky pro problém Hiding Leaders uvedené v literatuře a dáváme je do perspektivy parametrizované složitosti. Zdůrazňujeme také, že existuje více definic tohoto problému a přezkoumáváme některé výsledky z literatury s ohledem na námi vybranou definici. Dále přinášíme nové výsledky a ukazujeme, že problém je W[1]-těžký pro parametr b + d i když |L| = 1, a para-NP-těžký vzhledem k |L|, kde b označuje počet hran, které mohou být přidány do dané sítě, d označuje požadovaný počet následovníků, kteří musí mít centralitu alespoň tak vysokou jako kterýkoli z vůdců, a L označuje množinu vůdců. Také ukazujeme, že problém je v XP při parametrizaci parametry b nebo d. V závěru práce spojujeme naše výsledky a jejich důsledky - pro parametry |L|, b, d - s výsledky z literatury - pro parametr l, kde l označuje maximální stupeň mezi vůdci - a vizualizujeme je společně v přehledném grafu, který poskytuje snadno dostupné shrnutí současného stavu výzkumu Hiding Leaders problému vzhledem k rozhodovací verzi tohoto problému, centralitě měřené stupněm uzlu a čtyřem výše uvedeným parametrům.

Práce na DSpace

Ing. Jan Pokorný

Katedra teoretické informatiky

Tato práce se zaobírá zkoumáním strukturálních vlastností infrastrukturních sítí z pohledu teorie grafů. V práci byly měřeny tyto sítě: evropská elektrorozvodná síť, evropská síť plynovodů, severoamerická elektrorozvodná síť, česká železniční síť, česká dálniční síť, slovenská dálniční síť, maďarská dálniční síť a polská dálniční síť. Na sítích bylo měřeno pět grafových parametrů. Vzhledem k tomu, že většinu těchto parametrů nelze měřit v polynomiálním čase, bylo nutné pro některé parametry na některých datasetech provést pouze aproximaci. Aproximací se podařilo určit horní mez většiny parametrů pro všechny grafy. Parametry feedback edge set number, vertex cover number a feedback vertex set number vyšly pro dané sítě velké. Horní odhad parametru treewidth se pohyboval pro všechny sítě okolo hodnoty logaritmu počtu vrcholů. Parametr twinwidth vyšel pro všechny sítě ostře menší než logaritmus počtu vrcholů, a zároveň ne větší než 5.

Práce na DSpace

RNDr. Radek Hušek, Ph.D.

Katedra teoretické informatiky

V této práci analyzujeme reálné chodníkové sítě z pohledu grafové teorie. Začínáme získáním dat chodníkových sítí z OpenStreetMap a jejich serializací do různých datových formátů. Za pomocí řešičů celočíselného lineárního programování a řešičů jiných NP-těžkých problémů, měříme rozličné netriviální grafové vlastnosti chodníkových sítí z různých míst na planetě Zemi. Na základě našich výsledků, přinášíme odhady vztahů mezi parametry grafů, jejichž měření je výpočetně náročné. Zároveň přinášíme několik pozorování pro tvorbu algoritmu, jež by byl schopen vygenerovat chodníkovou síť ze silniční sítě a půdorysů budov.

Práce na DSpace

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

Katedra aplikované matematiky

Tato práce se zabývá studiem karetní hry Krabčáci, a to jak z hlediska složitosti i nalezení optimální výherní strategie. Bude představen obecný matematický model pro hru ze kterého je možné tvořit jednodušší varianty hry. Provede se analýza hry pro jednoho hráče a bude dokázáno, že se řadí mezi NP-úplné problémy. Dojde k vytvoření několika heuristických algoritmů pro hraní hry. Kromě toho ke stejnému účelu bude trénována i neuronová síť pomocí posilovaného učení a na konci dojde ke srovnání obou přístupů.

Práce na DSpace