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

Druhý místopředseda Akademického senátu

Závěrečné práce

Bakalářské práce

Plugin pro MediaWiki

Autor
Petr Bárta
Rok
2013
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Ing. František Štampach, Ph.D.

Rozšíření portálu Gamesites.cz

Autor
Jiří Levý
Rok
2013
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Ing. František Štampach, Ph.D.

FPT Algoritmy vícedimenzionálního párování

Autor
Jakub Puchýř
Rok
2014
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.

Algoritmy pro (NP-) těžké problémy

Autor
Petr Urban
Rok
2016
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Tato bakalářská práce se zabývá asymetrickým problémem listonoše - speciálním případem optimalizační úlohy z teorie grafů - čínského problému listonoše. Listonošův úkol je stejný jako v tradičním zadání - projít všechny ulice (hrany grafu) a vrátit se do výchozího místa (vrcholu). Oproti tradičnímu zadání tato úloha ale uvažuje graf, jehož neorientované hrany mohou být v každém směru ohodnoceny rozdílně (odtud pochází i anglický název - v ulicích fouká a po větru se jde snáz než opačným směrem proti větru). Cílem práce je vytvoření algoritmu řešícího tento NP-těžký problém. V teoretické části autor vysvětlí zadání problému a jeho variant, popíše možnosti jejich využití v praxi a možné způsoby jejich řešení. V praktické části pak v jazyce C++ implementuje algoritmus řešící tento problém pro případ, kdy jsou v grafu pouze jednotky neorientovaných hran.

Přesné algoritmy pro geodetické číslo a metrickou dimenzi grafu

Autor
Marek Jílek
Rok
2016
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Tato bakalářská práce se zabývá vytvořením parametrizovaného algoritmu hledajícího geodetické číslo na grafech s nízkým vrcholovým pokrytím. Geodetické číslo je velikost minimální množiny takové, že na nejkratších cestách mezi jednotlivými dvojicemi vrcholů množiny leží všechny vrcholy grafu. Na začátku jsou rozebrány řešení podobných problémů, například parametrizovaný algoritmus pro hledání metrické dimenze grafu. V práci je ukázáno, že lze využít určitých vlastností bipartitních grafů a grafů s nízkým vrcholových pokrytím pro zjednodušení složitosti algoritmu. Popsaný algoritmus je parametrizovaný velikostí množiny vrcholového pokrytí. Algoritmus je implementován v jazyce C++. Testováním byla potvrzena očekávaná redukce složitosti. Tento algoritmus lze tedy s úspěchem používat na zmíněných specifických grafech.

Maximální hranové barvení ve speciálních třídách grafů

Autor
Vojtěch Hruša
Rok
2019
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Dušan Knop, Ph.D.
Anotace
Tato práce se zabývá problémem maximálního hranového q-barvení. Podstatou problému je obarvení hran grafu za použití co nejvyššího počtu barev tak, aby byly hrany vedoucí z jednoho vrcholu obarveny maximálně q různými barvami. Nejdříve zkoumáme již známe algoritmy zabívající se tímto problémem a některé z nich detailně popíšeme. Poté představíme nově vymyšlené algoritmy - jednoduchý algoritmus pro stromy s lineární složitostí a algoritmus pro intervalové grafy s časovou složitostí O(n*(q+1)^p*k^(pq+1)*(q+p)^p), kde n je počet vrcholů grafu, p je velikost největšího úplného podgrafu a k je počet barev v optimálním obarvení. Součástí práce je také implementace algoritmu pro intervalové grafy.

Přidání podpory pro stromové rozklady do grafové knihovny Boost

Autor
Václav Král
Rok
2020
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Ing. Michal Valenta, Ph.D.
Anotace
Cílem této bakalářské práce je rozšířit C++ knihovnu Boost Graph Library (BGL) o algoritmy pro získávání stromové dekompozice grafu a příklad algoritmu, který využívá tuto stromovou dekompozici. V práci se čtenář seznámí nejen s jednotlivými algoritmy, ale i se samotnou knihovnou, která bude rozšiřována. Dále se práce zabývá samotnou úspěšnou implementací algoritmů, kde je kladen důraz především na dodržení konvencí knihovny BGL a pravidel generického programování. Závěrem práce hodnotí kvalitu implementace a navrhuje možná zlepšení. Výsledkem práce je funkční rozšíření BGL.

Problém monitorovaní hran vzdálenostmi vzhledem ke strukturálním parametrům

Autor
Václav Lepič
Rok
2022
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. RNDr. Dušan Knop, Ph.D.
Anotace
Tato práce se zabývá problémem monitorování hran pomocí vzdáleností. Problém je nejdříve popsán a poté je k němu přistoupeno z pohledu strukturálních parametrů. Algoritmus parametrizovaný velikostí vrcholového pokrytí byl navržen a jeho korektnost byla dokázána. Následně byl implementován a jeho rychlost byla otestována. Algoritmus, jehož parametrem je velikost feedback edge set byl navržen, a následně implementovaný a otestovaný.

Problém nejkratší cesty s minimální excentricitou vzhledem ke strukturálním parametrům

Autor
Martin Kučera
Rok
2020
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Dušan Knop, Ph.D.
Anotace
Problém nejkratší cesty s minimální excentricitou spočívá v nalezení takové nejkratší cesty v daném grafu, jejíž excentricita je minimální. O problému je známo, že je NP-úplný a W[2]-těžký vzhledem k minimální excentricitě. V práci představujeme FPT algoritmy pro tento problém parametrizované velikostí "maximum leaf number", "neighborhood diversity", "twin cover", "distance to cluster" a kombinací "distance to disjoint paths" s minimální excentricitou. Dále představujeme experimentální vyhodnocení posledního z algoritmů, který jsme také naimplementovali.

Podpora rozpoznávání intervalových grafů pro knihovnu Boost

Autor
Juraj Bielik
Rok
2021
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Ing. Jiří Novák, Ph.D.
Anotace
Náplňou tejto bakalárskej práce je rozšírenie externej knižnice Boost Graph Library, pracujúcej s grafovou reprezentáciou dát pre programovací jazyk C++. Je pridaná funkcionalita rozpoznávania intervalových grafov a s tým súvisiacich funkcií. Čitateľ je oboznámený s knižnicami Boost Graph Library, Interval Container Library a algoritmami Zjemenie partície, Lex-BFS, Test chordálnosti grafu, Strom klík, Rozpoznávanie intervalového grafu a Konštrukcia intervalového grafu. Následne je rozoberaná implementácia daných algoritmov a použitých štruktúr, s dôrazom na genericitu rozhraní funkcií poskytnutých používateľovi. Časť práce sa venuje testovaniu vypracovaného riešenia. Na záver sú diskutované dosiahnuté časové zložitosti a možné vylepšenia implementácie. Výstupom práce je použiteľné rozšírenie funkcionality Boost Graph Library, dodržiavajúce jej princípy.

Parametrizované algoritmy pro problém zkrácené metrické dimenze

Autor
Jiří Jirásek
Rok
2024
Typ
Bakalářská práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Mgr. Michal Opler, Ph.D.
Anotace
Tato práce se zabývá FPT algoritmy řešící problém Zkrácené Metrické Dimenze. Představíme dva již známé algoritmy řešící problém Metrické Dimenze. Pro algoritmus parametrizovaný šířkou modulu ukážeme jeho jednoduchou modifikaci tak, aby řešil problém Zkrácené Metrické Dimenze. Pro algoritmus parametrizovaný maximálním počtem listů vysvětlíme důvod, který nám zabránil jeho úpravám. Poté nastíníme implementaci algoritmů parametrizovaných šířkou modulu a ukážeme vybrané výkonnostní metriky.

Diplomové práce

Algoritmus pro hledání podgrafu založený na barevném kódování

Autor
Josef Malík
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Tato práce popisuje řešení problému izomorfismu podgrafů pomocí techniky barevného kódování. V práci je popsán problém izomorfismu podgrafů, jeho varianty a jeho aplikace. Dále je rozebrán problém tvorby hezkého stromového rozkladu optimální šířky pro zadaný graf, jelikož takováto struktura je pro daný přístup vyžadována. Jako hlavní část práce je popsáno několik modifikací a optimalizací původního algoritmu založeného na barevném kódování. Praktickým výsledkem práce je modul implementovaný v jazyce C, který je navržen pro řešení velkých instancí problému izomorfismu podgrafů včetně výpisu nalezených výsledků.

Podchycování cest v grafech

Autor
Radovan Červený
Rok
2018
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
RNDr. Tomáš Valla, Ph.D.
Anotace
Problém zvaný d-Path Vertex Cover, d-PVC spočívá v nalezení podmnožiny F vrcholů daného grafu G=(V,E) takové, že G \ F neobsahuje žádnou cestu na d vrcholech. Cesty, které chceme takto podchytit, nemusí být indukované. Je známo, že problém d-PVC je NP-úplný pro každé d >= 2. Dále je známo, že problém 5-PVC parametrizovaný velikostí řešení k je řesitelný v čase O(5^k*n^O(1)). V této práci přicházíme s algoritmem používající iterativní kompresi, který řeší problém 5-PVC v čase O(4^k*n^O(1)).

Parametrizované algoritmy pro Steinerovské stromy

Autor
Peter Mitura
Rok
2019
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Je-li dán vážený graf a podmnožina jeho vrcholů zvaných terminály, problém Steinerova stromu spočívá v nalezení souvislého podgrafu s nejmenší váhou, který obsahuje všechny terminály. Jedná se o známý NP-těžký problém, který nalézá užití kupříkladu v návrhu integrovaných obvodů, nebo počítačových a dopravných sítích. V této práci rozebereme algoritmus od Dreyfuse a Wagnera, od Ericksona, Monmy a Veinotta, a Nederlofův algoritmus, které řeší verzi tohoto problému parametrizovanou počtem terminálů, a algoritmus využívající dynamické programování a matici řezů pro parametrizaci dle stromové šířky. Pro všechny popsané algoritmy vytvoříme optimalizovanou implementaci a pro porovnání s jinými řešeními ukážeme její výsledky v soutěži PACE 2018.

Rozklad grafu na indukované hvězdy vzhledem ke strukturálním parametrům

Autor
Xuan Thang Nguyen
Rok
2023
Typ
Diplomová práce
Vedoucí
RNDr. Ondřej Suchý, Ph.D.
Oponenti
Mgr. Michal Opler, Ph.D.
Anotace
Zabýváme se problémem Rozdělení na indukované hvězdy na neorientovaných grafech. Cílem je rozdělit graf na q množin S_1, ..., S_q tak, že každá množina S_i indukuje hvězdu (graf izomorfní grafu K_{1, r} pro nějaké r >= 0). Je známo, že pro každé pevné q >= 3 je tento problém NP-úplný. Existuje ale exaktní algoritmus, který dokáže rozdělit graf na q indukovaných hvězd v čase 3^n n^{O(1)} a použije polynomiálně mnoho paměti. Není nám známo, že by existoval exaktní parametrizovaný algoritmus pro tento problém. V této práci předvedeme následující výsledky: (1) Problém patří do třídy FPT pokud budeme parametrizovat vrcholovým pokrytím grafu a existuje exaktní algoritmus běžící v čase O(k^{2k+1} n^2), kde k je velikost minimálního vrcholového pokrytí grafu. (2) Problém patří do třídy FPT pokud budeme parametrizovat stromovou šířkou grafu a a existuje exaktní algoritmus běžící v čase O(tw(G)^{2tw(G)}* n), kde tw(G) je stromová šířka grafu. (3) Pro každé pevné q platí, že problém lze vyřešit v lineárním čase na grafech s omezenou klikovou šířkou. Také poskytujeme jednoduchou implementaci algoritmu parametrizovaného vrcholovým pokrytím grafu v jazyce C++ a vyhodnotili jsme výkonnost implementace.