doc. RNDr. Tomáš Valla, Ph.D.

doc. RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

RNDr. Tomáš Valla, Ph.D.

Ing. Martin Šlapák, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

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

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Ing. Zdeněk Konfršt, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Ing. Václav Blažej

Katedra teoretické informatiky

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.

Práce na DSpace

doc. RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

RNDr. Tomáš Valla, Ph.D.

Mgr. Jan Starý, Ph.D.

Katedra teoretické informatiky

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

Práce na DSpace