Témata diplomových (a bakalářských) prácí

Implementace Koebeho věty

Koebeho věta říká, že každý rovinný graf má dotykovou reprezentaci pomocí kruhů. Je-li graf třísouvislý, má tzv. ortogonální dotykovou reprezentaci společně se svým duálem. Cílem práce je implementovat algoritmus pro nalezení dané reprezentace.

Více o větě a jejím důkazu v knize B. Mohar, C. Thomassen: Graphs on Surfaces

Zadáno, pro bakalářskou práci

Algebrogramy

Maematické hříčky, kde je cílem nahradit znaky ciframi, aby platila výsledná rovnost (nebo rovnosti) se nazývá algebrogram, např. jeden z hodně stručných je (AA)B=ABBA.

Patrně hodně prací a projektů se věnovalo řešení algebrogramů (efektivněji než hrubou silou).

V této práci by jednak měly být shrnuty známé postupy pro řešení algbrogramů, ale hlavním cílem by ovšem bylo zkoumání generování algebrogramů - dle předem dané struktury, s klasifikací obtížnosti nalezitelnosti řešení, popř. s ohledem na počet řešení. Zajímavým směrem by mohlo být rozšíření do jiných početních soustav. Očekává se, že příslušné algoritmy budou implementovány.

Vhodné spíše pro bakalářskou práci.

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ů

Jpeg kaleidoskop

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.

Digitální sbírka příkladů

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.

Escherův kaleidoskop

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
fialazavinackam.mff.cuni.cz
září 2008