Bakalářské práce
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
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.
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
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.
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.
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.
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.
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.
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ů.
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ě.