Dizertační práce
Algoritmická teorie her a problematika návrhu mechanismů
Školitel
Stupeň
Téma dizertační práce
Popis tématu
Teorie her se snaží matematicky modelovat chování účastníků (tj. hráčů nebo agentů) určitého soutěžního nebo kooperativního procesu. Přirozeně vyvstává otázka: Jak dobrý je stav hry z hlediska některých globálních optimalizačních kritérií? To se měří kvantitativně pomocí tzv. účelové funkce, definované na základě výsledků hry, která číselně vyjadřuje „společný užitek” výsledku pro jednotlivé účastníky i pro celou (globální) společnost. Hledáme řešení hry, ve které jednotlivci jednají podle svých interních motivací a sobecky maximalizují svůj zisk.
Pravděpodobně nejpopulárnějším způsobem, jak zachytit tento koncept, je pojem Nashova ekvilibria. Hra může mít mnoho Nashových ekvilibrií s různými hodnotami (globální) účelové funkce. V souladu s worst-case přístupem se efektivita hry měří na základě nejhoršího z nich. Cena anarchie hry je definována jako poměr mezi hodnotou účelové funkce v nejhorším Nashově ekvilibriu a hodnotou v optimálním výsledku, pokud by strategie všech hráčů byly stanoveny centrální autoritou.
Sociální volba znamená zpracování preferencí účastníků v jedno společné rozhodnutí. Mechanism design se snaží implementovat požadované sociální volby ve strategickém prostředí – za předpokladu, že všichni účastníci jednají racionálně, tj. snaží se maximalizovat svůj vlastní zisk. Klasickými příklady použití mechanism designu jsou volby, trhy a aukce. Strategickým chováním zde rozumíme zejména to, že účastník může předložit takové pořadí preferencí, které neodráží jeho skutečné preference – to může ve skutečnosti vést k volbě pro účastníka lepšího výsledku ve volbách. Důležitým požadavkem kladeným na mechanismus je tzv. strategyproofness: žádný hráč nemá prospěch z předložení nepravdivých informací.
Seznam možných směrů výzkumu vyplývajících z těchto témat zahrnuje například problém navrhování her dosahujících nízké ceny anarchie v kontexty některých standardních kombinatorických optimalizačních problémů (jako je vertex cover, set cover, dominující množina, ...), navrhování strategyproof mechanismů pro různé verze problému facility location, studium speciálních variant problémů stabilního párování a mnoho dalších.
Bakalářské práce
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.
Katedra
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.
Perzistentní datové struktury a jejich aplikace
Autor
Josef Malík
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Tomáš Valla, Ph.D.
Oponenti
RNDr. Ondřej Suchý, Ph.D.
Katedra
Experimentální srovnání worst-case optimálních hald
Autor
Hana Volků
Rok
2019
Typ
Bakalářská práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
Ing. Václav Blažej
Katedra
Anotace
V rámci této bakalářské práce je vytvořena implementace Brodalovy haldy, prioritní fronty, která je i v nejhorším případě asymptoticky optimální. Spolu s ní je vytvořen jednoduchý test měřící efektivitu haldy, ten je následně použit na zjištění efektivity poskytnuté implementace oproti existující implementaci Fibonacciho haldy.
Rozvrhovací algoritmy a jejich aplikace
Autor
Jiří Stránský
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Tomáš Valla, Ph.D.
Oponenti
RNDr. Ondřej Suchý, Ph.D.
Katedra
Vehicle routing problem, jeho varianty a metody řešení
Autor
Michal Polívka
Rok
2015
Typ
Bakalářská práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
Ing. Zdeněk Konfršt, Ph.D.
Katedra
Anotace
Tato práce studuje Vehicle Routing Problem (VRP) a jeho varianty. Pro kapacitní verzi problému (CVRP) implementujeme varianty používaných algoritmů a jako naše řešení navrhneme a implementujeme modifikaci dvou local search metod, které ještě nebyli na tento problém nikým použity. Na třech sadách instancí provedeme měření a porovnání těchto algoritmů s nejlepšími známými výsledky a free/open-source programy.
Vyhledávání řetězcových vzorků s použitím záměn
Autor
Václav Blažej
Rok
2015
Typ
Bakalářská práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
RNDr. Ondřej Suchý, Ph.D.
Katedra
Anotace
Vyhledávání řetězcových vzorků s použitím záměn je problém hledání všech výskytů vzorků v textu, přičemž je ve vzorku dovoleno zaměňovat sousední symboly.
Cílem je navrhnout rychlý vyhledávací algoritmus, který využije bitového paralelismu bitových instrukcí koncového stroje.
Nedávno jsme nalezli závažnou chybu v algoritmu od [Ahmed et al.: The swap matching problem revisited, Theor. Comp. Sci. 2014], kterou detailně popíšeme.
Zároveň ukážeme proč tento algoritmus nelze jednoduše opravit.
Many-to-one jednostranné párování
Autor
Emma Hovorková
Rok
2025
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Tomáš Valla, Ph.D.
Oponenti
Ing. Šimon Schierreich, Ph.D.
Katedra
Anotace
Naše téma se zabývá teorií párování, která je podoborem v oblasti algorit-
mické teorie her. V této práci zavádíme následující model nazvaný Agents to
Facilities with Restriction Problem (AFR): Existuje m zařízení (facilities) a n agentů (agents), každý agent má seznam priorit na zařízení, každé zařízení
má omezenou kapacitu a může také obsahovat seznam agentů, které nechtějí
(restricted agents). Navrhujeme mechanismus, který najde Pareto optimální
řešení AFR minimalizující závist. Tento mechanismus je tzn. strategy-proof.
Zavádíme další varianty AFR, a to oboustrannou a váženou variantu.
Vehicle routing problem s časovými okny a metody jeho řešení
Autor
Martin Macho
Rok
2018
Typ
Bakalářská práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
Ing. Martin Šlapák, Ph.D.
Katedra
Anotace
Tato práce studuje Vehicle Routing Problem (VRP) a jeho varianty. Pro
verzi s časovými okénky implementujeme varianty použivaných algoritmů a navhrneme a implementujeme modifikaci genetického algoritmu pro řešeni
problémů lokálniho prohledáváni. Na dvou sadách instanci provedeme měřeni
a porovnáni těchto algoritmů s nejlepšimi známými výsledky.
Diplomové práce
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.
Katedra
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.
Integerové datové struktury
Autor
Miloslav Brožek
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Katedra
Anotace
Cílem této práce je návrh a zrychlení datových struktur a algoritmů na modelu RAM s velkou šířkou slova. Zrychlení se děje zejména za pomoci bitových paralelních instrukcí.
V práci tuto techniku aplikujeme pro zlepšení asymptotické složitost vybraných algoritmů a struktur.
Studujeme zejména datové struktury, které se zaměřují na segmentové operace, kterými jsou například počet prvků na intervalu či maximum na intervalu. Algoritmy, na které se práce zaměřuje jsou pak největší společný dělitel, Sparse Table a Number Theoretic Transform.
Kombinatorické hry typu Taking and Breaking
Autor
Šimon Lomič
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Katedra
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ě.
Online Ramsey teorie
Autor
Václav Blažej
Rok
2017
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
Mgr. Jan Starý, Ph.D.
Katedra
Anotace
Tato práce se zabývá online Ramseyovou teorií.
Problém je definován jako kombinatorická hra Buidera a Paintera.
Je dán libovolný graf H a hrací plocha nekonečně mnoha nezávislých vrcholů.
Každé kolo Builder postaví novou hranu do grafu hrací plochy a Painter ji obarví červeně nebo modře.
Online Ramseyovo číslo grafu H je minimální počet kol, které Builder potřebuje, aby vynutil vznik jednobarevného podgrafu isomorfního s H uvnitř hrací plochy.
Online Ramseyovo číslo se často srovnává se size-Ramsey číslem, což je nejmenší počet hran grafu takového, že libovolné jeho obravení dvěma barvama obsahuje jednobarevnou kopii H.
Size-Ramsey číslo shora omezuje online Ramseyovo číslo, nicméně zdá se obtížné dokázat, že je mezi nimi asymptoticky významný rozdíl.
Existuje pouze jeden výsledek takového typu, od Conlona [On-line Ramsey Numbers, SIAM J. Discrete Math. 2009], který dokázal, že pro nekonečně mnoho úplných grafů je online Ramseyovo číslo asymptoticky menší než size-Ramsey číslo.
V této diplomové práci je popsána nekonečná rodina stromů, pro které je online Ramseyovo číslo asymptoticky menší než size-Ramsey číslo.
Také jsou v ní dokázány horní meze pro online Ramseyovo číslo cyklů a k-podrozdělených hvězd.
A nakonec je přesně určena hodnota omezeného online Ramseyova čísla pro trojúhelníky versus hvězdy na třídě souvislých grafů.