|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Automatická kontrola programů v jazyce C
Doucha, Martin ; Spousta, Miroslav (oponent) ; Mareš, Martin (vedoucí práce)
V této práci studuji možnost zjišt'ovat běžné začátenické chyby v jazyce C pomocí statických analýz zdrojového kódu a generování run-time testů. Součástí práce je implementace několika jednoduchých statických analýz a run-time testů zaměřených na začátečnické chyby a jejich co nejpřesnější lokalizaci ve zdrojovém kódu. Jako základ pro jejich implementaci jsem zvolil kompilátorovou infrastrukturu LLVM a frontend Clang. Dále v téeto práci naleznete stručný programátorský úvod do systému LLVM a popis nově implementovaných nástrojů. Hlavním cílem je umožnit využití jazyka C ve výuce základního kurzu programování.
|
host ::
RSS.