|
|
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ě,...
|
|
|
Generování rozmístění nábytku
Dvořák, Ondřej ; Petříčková, Zuzana (oponent) ; Jelínková, Eva (vedoucí práce)
Cílem práce je vytvořit program, který na základě stanovených omezujících podmínek generuje různé návrhy rozestavení nábytku v místnosti. Tento program se jmenuje Spaceout a jeho základem jsou genetické algoritmy. Práce zároveň podává stručný přehled existujících programů pro vytváření návrhů interiérů a exteriérů. Její součástí je i programátorská a uživatelská dokumentace programu Spaceout.
|
|
| |
|
|
Snímky webových stránek
Benhák, Tomáš ; Mareš, Martin (oponent) ; Jelínková, Eva (vedoucí práce)
Tato práce vytvář program pro Linux, který generuje snímky webových stránek bez použití okenního systému. K vykreslení webových stránek je použita komponenta GtkMozEmbed webového prohlížeče Mozilla. Součástí práce je úprava knihovny GTK+ tak, aby grafický výstup probíhal do zvoleného souboru bez účasti okenního systému.
|
|
|
Bombič 2
Fišer, Karel ; Jelínková, Eva (oponent) ; Lidický, Bernard (vedoucí práce)
Název práce: Bombič 2 Autor: Karel Fišer Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Bernard Lidický E-mail vedoucího: bernard@kam.mff.cuni.cz Abstrakt: Cílem práce bylo analyzovat nedostatky první verze hry Bombič a navrhnout hru a editor map odstraňující tyto nedostatky. Návrh poté realizovat, vytvořit programátorskou a uživatelskou dokumentaci. Výsledkem práce je programátorské dílo, které sestává ze dvou programů. V textu této práce jsou popsané zjištěné nedostatky první verze hry, koncepci uložení dat a architekturu obou programů. V kapitole 6. se nachází uživatelská dokumentace. Obsahuje popis ovládání hry i editoru map. Klíčová slova: Bombič, plošinová hra, arkáda, souboj
|
|
|
Barvení grafů pomocí mravenčí kolonie
Vámošová, Mária ; Lidický, Bernard (oponent) ; Jelínková, Eva (vedoucí práce)
V této práci se zabýváme problémem barvení grafů. Podáváme přehled existujích algoritmů a zaměřujeme se na algoritmy mravenční kolonie. Pro pozorování jejich principů a provnání jsme vybrali tř esistující algoritmy, otestovali je na známých grafecz a podáváme přehled výsledků. Tyto výsledky jsou dále porovnávnány s dosud nejlepšími známými. Součástí práce je i návrh otestování vlastního algoritmu.
|
|
|
Heuristiky pro problém výměny ledviny
Böhmová, Kateřina ; Mareš, Martin (oponent) ; Jelínková, Eva (vedoucí práce)
V této práci se zabýváme problémem výměny ledviny. Jedná se o kombinatorický model problému rozdělení žijících dárců ledvin pacientům. Přesněji řečeno, máme množinu nekompatibilních dvojic pacient-dárce a snažíme se permutací dárců získat páry vhodné k transplantaci. Požadujeme, aby výsledné řešení bylo stabilní, což ve zkratce znamená, že nepřipouštíme výskyt skupiny dvojic, jejíž všichni členové by si polepšili vytvořením jiné permutace jen mezi sebou. V práci vysvětlíme známé metody pro hledání řešení (algoritmus Top Trading Cycles a heuristiky) a pro testování stability řešení. Popíšeme předchozí známé výsledky pojednávající o těžkosti problému. Navrhujeme hledat dobré stabilní řešení tak, že opakovaně aplikujeme heuristiky na počáteční řešení vygenerované pomocí TTC. Používáme několik známých heuristik spolu se dvěma novými. Předvedeme výsledky provedených testů, které ukazují vylepšení dosažené heuristikami oproti počátečnímu řešení. Také předvedeme nový algoritmus pro testování stability řešení, který běží výrazně rychleji než původní algoritmus.
|
|
|
Výpočetní složitost v teorii grafů
Jelínková, Eva
Seidelovo přepnutí je grafová operace, která změní hrany vycházející z daného vrcholu tak, aby sousedil s právě těmi vrcholy, které původně nebyly jeho sousedy; zbytek grafu zůstane nezměněn. Dva grafy nazveme ekvivalentní v přepnutí, pokud lze pomocí posloupnosti přepnutí jeden z nich převést na izomorfní tomu druhému. V této práci studujeme výpočetní složitost problému S(P) pro určitou grafovou vlastnost P: je daný graf G ekvivalentní v přepnutí nějakému grafu, který má vlastnost P? Neprve podáváme přehled známých výsledků, vlastností P, pro které je problém S(P) polynomiální, i těch, pro které je NP-úplný. Poté ukážeme NP-úplnost následujícího problému pro každé c (0; 1): lze daný graf G přepnout tak, aby obsahoval kliku velikosti alespoň cn, kde n je počet vrcholů grafu G? Zabýváme se také problémem pro pevně zvolený graf H rozhodnout, zda je daný graf G ekvivalentní v přepnutí nějakému H-prostému grafu. Ukážeme, že je-li H izomorfní spáru, tento problém je polynomiální. Dále podáváme charakterizaci grafů, které jsou ekvivalentní v přepnutí nějakému K1;2-prostému grafu, pomocí deseti zakázaných indukovaných podgrafů, z nichž každý má pět vrcholů.
|
|
| |
|
|
III/4465 Horka nad Moravou, úsek: ul. Náměstí osvobození
Jelínková, Eva ; Skalická, Petra (oponent) ; Smělý, Martin (vedoucí práce)
Náplní bakalářské práce je úprava křižovatky ulic Náměstí osvobození, P.Bezruče a 1.máje v obci Horka nad Moravou. Práce obsahuje úpravu zpevněných ploch a zklidnění silnice III/4465 v prostoru ulice Náměstí osvobození. Tím by se měla zpomalit průjezdní rychlost vozidel a zvýšit bezpečnost silničního provozu a chodců. Práce obsahuje řešení statické dopravy, autobusových zastávek, úpravy a napojení chodeckých tras a veřejného osvětlení.
|
host ::
RSS.