|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
|
|
Steinerovská barvení kubických grafů
Tlustá, Stanislava ; Fiala, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá barvením kubických grafů a shrnuje dostupné poznatky o tzv. Steinerovském barvení, což je hranové barvení, kde barvy stýkající se u jednoho vrcholu tvoří trojici nějakého částečného Steinerova systému. Velká pozornost je věnována zejména projektivním a afinním systémům. Následně je vyslovena postačující podmínka pro univerzalitu systému a je konstatováno, že všechny ostatní úplné tranzitivní systémy ji splňují. Součástí práce jsou také postupy vedoucí k nalezení obarvení pomocí Fanovy roviny, afinního systému Z3 3 a univerzálního systému s označením F7 S⊠ 3 vzniklého součinem Fanovy roviny s triviálním systémem. Nakonec je prezentován algoritmus použitelný pro ostatní systémy a kubické grafy s omezenou stromovou šířkou.
|
|
|
Game variants of graph labeling
Jedličková, Nikola ; Šámal, Robert (vedoucí práce) ; Fiala, Jiří (oponent)
Značkovanie na grafe, nazývané tiež labeling, je zobrazenie z množiny vrcholov alebo hrán do množiny značiek L ⊆ N∪{0}. Popri prehl'ade doteraz známych hracích variant predstavíme aj nový typ labelingu - ESD labeling a s ním súvisiacu hraciu variantu, ktorá bola inšpirovaná článkom Tuzu. ESD labeling na grafe G je prosté zobrazenie φ : V (G) → {1, . . . , n}, kde pre každé dve rôzne hrany platí, že súčet značiek na ich koncových vrcholoch je rôzny. Okrem otázky existencie ESD labelingu sa budeme zaoberat' aj hracou variantou, kde labeling po- stupne vytvárajú dvaja hráči. 1
|
|
|
Aproximace nezávislosti rovinných grafů
Berg, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
Problém nezávislé množiny je dobře známý NP-úplný problém, který je NP-úplný i pro rovinné grafy. Ale na rozdíl od obecných grafů, pro rovinné grafy existuje polynomiální aproximační schéma. Popíšeme přesný algoritmus pro hledání největší nezávislé množiny v rovinných grafech založený na dynamickém programování. Tento přesný algoritmus lze jednoduše upravit na polynomiální aproximační schéma. Obě jeho verze jsme implemen- tovali a otestovali. Při tom jsme používali několik generátorů náhodných rovinných grafů. Přesný algoritmus jsme experimentálně srovnávali s dalšími dvěma algoritmy. Aproximační algoritmus jsme srovnávali s jeho přesnou verzí a měřili skutečný aproximační poměr a také jeho časovou náročnost v porovnání s přesnou verzí. Zjistili jsme, že přesný algoritmus na zvolených grafech většinou dokončí výpočet rychleji než ostatní dva algoritmy. Také jsme zjistili, že aproximační verze má vzhledem k teoretickému minimu většinou lepší apro- ximační poměr s dobrou časovou složitostí. 1
|
|
|
Aplikace muzikoterapie speciální pedagogiky pro i-CT Framework
Bártů, Tomáš ; Šátek, Václav (oponent) ; Fiala, Jiří (vedoucí práce)
Tato bakalářská práce popisuje vývoj aplikace pro účely muzikoterapie se zaměřením na kytaru v prostředí speciálního vzdělávání mentálně postižených osob. Práce se zabývá problematikou vývoje podobně zaměřených aplikací, analýzou již existujících aplikací, návrhem nové aplikace a implementací tohoto návrhu. Výsledná aplikace navazuje na návrhové principy projektu " Počítačové terapie " a využívá vzniklý rámec i-CT Framework zjednodušující tvorbu aplikací pro uvedené prostředí. Vývoj je zaměřen na multiplatformnost s podporou operačního systému Android a iOS, přičemž byla provedena verifikace v prostředí osob s mentálním hendikepem. V závěru práce je popsána odezva cílových uživatelů s mentálním postižením a jejich lektorů.
|
|
|
Aplikace AAK speciální pedagogiky pro i-CT Framework
Čajánek, Martin ; Šátek, Václav (oponent) ; Fiala, Jiří (vedoucí práce)
Tato bakalářská práce se zaměřuje na analýzu potřeb komunikace ve speciální pedagogicepři práci s osobami s mentálním postižením a na aplikaci, která danou problematiku řeší. Vyvíjená aplikace umožňuje sestavování vět pomocí výběru obrázkových symbolů reprezentujících slova, či jejich vlastní tvorbu a následnou hlasovou syntetizaci hotové věty. Je určená pro mobilní zařízení se systémy Android a iOS, byla vyvíjena v souladu s návrhovými principy počítačové terapie a slouží jako nadstavba pro i-CT Framework, rámec zastřešující a zjednodušující práci s aplikacemi určené pro speciální pedagogiku.
|
|
|
i-CT Framework a aplikace pro překlad znakového jazyka
Meca, Vojtěch ; Šátek, Václav (oponent) ; Fiala, Jiří (vedoucí práce)
Cílem práce bylo vytvořit dvě aplikace pro využití v prostředí osob se specifickými vzdělávacími potřebami resp. osob s mentálním postižením. Jedna se o rámec i-CT Framework, který je zároveň spustitelnou aplikací pro výše uvedenou cílovou skupinu. Jako spustitelná aplikace rámec pracuje ve formě centrálního nástroje pro správu uživatelů, aplikací, oprávnění a bezpečnostních restrikcí. Dalším cílem práce pak bylo vytvoření nástroje Gesture Translator, díky kterému je možné překládat gesta znakového jazyka daného uživatele v uvedeném prostředí. Obě části práce fungují na operačních systémech Android a iOS.
|
|
|
K analýze vojenského významu olomoucké pevnosti v období válek o rakouské dědictví a sedmileté války
Borovský, Jiří ; Stellner, František (vedoucí práce) ; Županič, Jan (oponent) ; Fiala, Jiří (oponent)
K analýze vojenského významu olomoucké pevnosti v období válek o rakouské dědictví a sedmileté války Jiří Borovský Abstrakt Disertační práce přibližuje roli pevnostního města Olomouc ve válkách o rakouské dědictví (1740-1748) a sedmileté války (1756-1763). V letech 1741-1742 se téměř celá Morava stala hlavním operačním prostorem vojsk pruského krále Fridricha II. Prusové obsadili rovněž město Olomouc, které plnilo funkci jejich nejdůležitější vojenské a logistické základny na obsazeném území. Po ukončení válek o rakouské dědictví došlo k zásadní přestavbě olomoucké pevnosti. Olomouc se během desetiletí neobyčejného stavebního úsilí stala nejmodernější bastionovou fortifikací na území podunajské monarchie. V roce 1758, krátce po dokončení přestavby, vstoupili Prusové na Moravu opět s cílem město obsadit. Základem práce je analýza obou tažení pruských vojsk na Moravu. Zabývá se především podmínkami, za jakých rakouská i pruská strana vstupovaly do války, srovnáním obou vojsk, dále průběhem vojenských kampaní a konečně jejich výsledky. Autor se zaměřuje na srovnání úlohy pevnosti v obou konfliktech a rozdíl mezi taženími. V práci jsou rovněž popsány strategie a taktiky bojujících armád a v šíři odpovídající potřebám práce také historie olomoucké fortifikace a její přestavby. Pozornost je věnována také...
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
Název práce: Výpočetní složitost v teorii grafů Autor: Eva Jelínková Katedra: Katedra Aplikované Matematiky Vedoucí disertační práce: Prof. RNDr. Jan Kratochvíl, CSc., Katedra Aplikované Matematiky Abstrakt: Zabýváme se problémy teorie grafů, zejména z hlediska výpočetní složitosti. V první části práce se věnujeme výpočetní složitosti problémů sou- visejících se Seidelovým přepnutím grafů. Uvažujeme rozhodující problém, zda daný graf lze přepnout tak, aby obsahoval nejvýše daný počet hran. Dokážeme, že tento problém je NP-úplný, dokonce i pro grafy s omezenou hustotou. Částečně tak odpovídáme na otázku Matouška a Wagnera [Dis- crete Comput. Geom. 52, no. 1, 2014]. Popisujeme také nekonečně mnoho grafů H, pro které je NP-těžké rozhodnout, zda pro daný graf existuje graf, který je s ním ekvivalentní v přepnutí, a zároveň neobsahuje H jako induko- vaný podgraf. Tímto řešíme otevřený problém Kratochvíla, Nešetřila a Zýky [Annals of Discrete Math. 51, 1992]. Ve druhé části práce se zabýváme tématem párování s preferencemi. Zaměřujeme se na problém trhu s domy, konkrétně na model s duplicitními domy. Popisujeme 2-aproximační algoritmus pro maximální počet spoko- jených agentů v případě,...
|
host ::
RSS.