Ing. Šimon Schierreich

Ing. Šimon Schierreich

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

Ing. Šimon Schierreich

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. Šimon Schierreich

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. Š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

Ing. Šimon Schierreich

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