Témata diplomových (a bakalářských) prácí
Obrácené ypsilon
V chystaném článku popisuje B. Toft metodu, jak určit vítěze ve hře Rex (Reversed Hex), t.j. ve hře Hex,
kde je ovšem cílem nepropojit přidělené dvě strany hrací desky. Cílem práce je ověřit, zda by
tato metoda šla použít i pro analogickou hru Ypsilon (spojování tří stran trojúhelníku).
Viz abstrakt přednášky B. Tofta na BGW workshopu.
... a jiné
Další témata z oblasti výpočetní složitosti problémů z teorie grafů lze domluvit osobně.
(kontrakce na cestu ve spáruprostých grafech; (p,q)-nakrytí na grafy s jemným stupňovým rozdělením,
atd.)
Témata ročníkových projektů
Umlouvátko
Aby úmluvy na naší katedře nebyly tak dlouhé a úmorné, bylo by dobré,
kdyby předem bylo známo, kolik studentů má zájem o který předmět a
které časy by jim vyhovovaly více a které méně.
Cílem projektu je vytvořit program pro sběr a vyhodnocení těchto informací.
Kytarové karaoke
Nápad: rozšířit možnosti webových zpěvníků, aby slova a akordy písničky
byly "přehrány" v nastaveném rytmu, včetně nápovědy hmatů pro akordy, popř.
transpozic do jiných tónin. Možno rozšířit i na jiné nástroje.
Pro inspiraci uvádím několik úspěšně implementovaných projektů
Cílem práce je sestavení interaktivního java apletu, který by předvedl
princip ztrátové komprese použité ve formátu Jpeg. V apletu by mělo jít ovlivnit:
volbu zdrojového obrázku a příslušného výřezu, hloubku komprese, "složky výstupní báze",
zobrazení rozdílu kódovaných dat oproti původnímu zdroji, atd.
Cílem práce je naimplementovat sbírku příkladů. Bude třeba navrhnout vhodnou
strukturu databáze (zadání příkladu, nápověda, řešení, třídění příkladů
podle témat, atd.), vyřešit typografii matematických symbolů a navrhnout
vhodné výstupy (pro samostudium, přípravu cvičení, písemek, atd.).
Předpokládá se implementace na centrálním serveru (SQL apod.) a přístup do
sbírky přes webové rozhraní. Obsah sbírky (t.j. vlastní příklady) nejsou
součástí zadání a budou poskytnuty zadavatelem práce.
Cílem projektu je naimplementovat editor výplní rozličných mřížek
(pravidelných, polopravidelných i neperiodických) a to jak pro rovinné
geometrie, tak pro konkávní resp. konvexní. Grafické vlohy a základní
znalost díla M.C. Eschera výhodou (spíš nutností).
Hra minolovka - výpočetní složitost a implementace hledání řešení
Cílem práce je určení výpočetní složitosti pro řešení pozic ze známé hry
minolovka. Očekává se i implementace navržených algoritmů a heuristik.
Zajímavé otevřené problémy, které by se mohly stát tématem práce
Hranové L(p,q)-značkování grafů
Otázka výpočetní složitosti L(p,q) barvení pro obecné grafy
byla nedávno úspěšně klasifikována. Možým přirozeným rozšířením je
přechod od vrcholového na hranové barvení, popř. k dalším specifickým
třídám.
Viz diplomová práce M. Kupce a přehledový článek T.
Calamoneri.
Zadáno
Paritní barvení rovinných grafů
Silné paritní obarvení rovinného nakreslení grafu je takové ne nutně korektní
obarvení vrcholů tohoto nakreslení grafu takové,
že pro každou stěnu nakreslení platí, že každá barva použitá na dané stěně se
vždy vyskytuje na lichém počtu vrcholů. Podstatné pro tuto definici je, že artikulace se
započítávají tolikrát, kolikrát jsou incidentní tahu podél hranici této stěny.
U dvousouvislých grafů takové obarvení vždy existuje - stačí každému vrcholu dát
unikátní barvu, potom díky neexistenci artikulací se každý vrchol vyskytuje v každé
stěně nejvýše jedenkrát.
Příkladem grafu, který nemá paritní barvení je graf na pěti vrcholech vzniklý
slepením dvou trojúhelníků - artikulace je do vnější stěny započtena dvakrát, tedy
tato barva musí být zopakována na alespoň jednom z trojúhelníků. Pak ale buď některý
z těchto dvou trojúhelníků nebo vnější stěna bude nutně mít sudý počet vrcholů této barvy.
Otevřeným problémem je, zdali lze efektivně rozhodnout, jestli
pro daný ne-dvousouvislý graf existuje alespoň jedno paritní obarvení.
V dalších variantách tohoto problému se lze omezit na souvislé grafy anebo zkoumat
jen taková paritní obarvení, která jsou zároveň korektní obarvení grafu (t.j. vrcholy
stejné barvy nejsou spojené hranou). Dále lze zkoumat relevantní otázky ke
slabému paritnímu barvení - zde stačí, aby na každé stěně byla alespoň jedna barva
užita na liché počtu vrcholů (opět měřeno s násobností podél tahu na hranici stěny).
Viz práce S. Jendroľa a kol. o paritních barveních; GRAFY 2010
Dvourozměrná pásmová šířka (bandwidth) a zkreslení (distortion) stromů
Pokusme se vnořit strom (např. i omezeného stupně) do dvourozměrné mřížky,
aby vzdálenosti mezi body v mřížce co nejlépe odpovídaly vzdálenosti v grafu.
V obecnosti nelze očekávat lineární závislost (ale spíše logaritmickou).
Lze zkoumat celou škálu otázek ohledně mezí na změnu vzdálenosti
pro příbuzné třídy grafů, popřípadě určit
výpočetní složitost. Pro zajímavost uveďme, že bandwidth je problém, u něhož je notoricky známo, že je
NP-těžký pro stromy.
Pro reference viz práce A. Proskurovského, P. Heggernes a D. Meistera
Jak chytit Conwayovy krále?
Uvažme hru dvou hráčů na nekonečné mřížce: První má na mřížce svoji figurku-krále a v každém svém
tahu ji posune na sousední políčko (jako v šachu), je-li volné. Druhý hráč ve svém tahu obsadí
libovolné pole, vyjma políčka na kterém stojí král, a to už zůstane obsazené až do konce hry.
Je známo, že druhý hráč má vyhrávající strategii, t.j. v konečném počtu tahů t1 může obklopit
krále a ten není schopen tahu.
Uvažme variantu této hry, kdy na začátku je na stejném políčku n králů a první hráč ve svém
tahu každého posune. Hra končí, když jsou obklíčeni všichni králové.
Podobně jako v předchozím případě má druhý hráč vítěznou strategii.
Otázkou je určit co nejpřesnější odhad výsledného času tn.
Pro dost velká n lze ukázat zlepšení obou triviálních mezí:
t1 < tn < nt1.
Pro reference viz práce M. Aignera a A. Pora.
Problém pěstování vážených stromů
Pro daný soubor přirozených čísel (t.j. čísla se mohou opakovat) se hledá jejich uspořádání
do stromu tak, aby každý vrchol měl přiřazeno číslo ostře větší než je součet jeho dětí.
Známé částečné výsledky: Pokud je omezený počet opakování, nebo pokud je omezený počet různých čísel v souboru,
lze úlohu vyřešit v polynomiálním čase. Pokud je strom předepsaný, je úloha NP-úplná (redukcí z problému batohu).
Autor F. Ruskey, Univ. of Victoria, BC
Problém váženého barvení stromů
Pro strom s ohodnocenými vrcholy hledáme obarvení vrcholů takové, aby součet
maxim ze všech tříd byl co nejmenší.
Známé částečné výsledky: Pokud má strom omezený stupeň lze úlohu vyřešit v polynomiálním čase.
Více informací v článku z ICTCS'05.
Problém hledání středu množiny bodů v rovině
Pro daných n bodů je cílem nalézt takový bod (střed), aby úhly určené polopřímkami vedenými ze středu
k jednotlivým bodům byly co nejblíže úhlu 2pi/n.
Známé částečné výsledky: Pokud požadujeme, aby úhly byly úplně stejné, lze úlohu vyřešit (rozhodnout) v lineárním čase.
V tomto případě ovšem takový střed nemusí existovat.
Více informací v článku z ICTCS'05.
Jiří Fiala
fiala
kam.mff.cuni.cz
září 2008