Témata ročníkových projektů a bakalářských prací

Níže uvádím témata ročníkových projektů související s mým výzkumem. Pro práci na těchto tématech je vhodné, aby student měl jistou míru zájmu o diskrétní matematiku a kombinatoriku. Ve všech případech je nutné, aby výsledný program byl rychlý a paměťově úsporný, a pokud možno také přenositelný. Tomu je nutno přizpůsobit volbu programovacích jazyků. Z práce na těchto tématech se může posléze vyvinout i bakalářská práce, ale není to podmínkou. Rovněž je možné bádat o těchto tématech čistě teoreticky v rámci bakalářské práce, i bez předchozího ročníkového projektu. Všechna níže formulovaná témata jsou poměrně obecná, přesné zadání projektu bych si s případným zájemcem domluvil na osobním setkání.
Jsem ochoten vést i ročníkové projekty na témata, se kterými přijdou studenti. V takovém případě mám podmínku, aby plánovaným výsledkem práce byl program, u kterého lze očekávat, že bude využíván i po úspěšném dokončení projektu. Ideální je třeba implementace nové funkčnosti pro nějaký existující open source software.

Máte-li zájem, abych vedl Váš ročníkový projekt, napište mi mail. Z Vašeho mailu musí vyplývat, že jste četli tuto stránku.

Moje témata:

Počítání Möbiovy funkce kombinatorických objektů. Möbiova funkce je definována pro libovolné (lokálně konečné) částečné uspořádání. Její hodnoty souvisí s kombinatorickými a topologickými vlastnostmi daného uspořádání. V topologii a kombinatorice se zkoumají vlastnosti této funkce pro některé "kombinatoricky přirozené" příklady částečných uspořádání, například pro množinu slov nad konečnou abecedou uspořádanou pomocí relace "být podslovem", pro množinu permutací uspořádanou relací "být podpermutací" atd. Vlastní definice Möbiovy funkce je velmi jednoduchá, ovšem počítat konkrétní hodnoty přímým použitím této definice může být časově i prostorově dosti náročné. Cílem projektu by bylo napsat program, který bude umět pokud možno co nejefektivněji počítat hodnoty této funkce v nějakém vhodně zvoleném "kombinatoricky definovaném" částečném uspořádání.

Generování a vizualizace průnikových reprezentací grafů. Širokým tématem výzkumu na pomezí geometrie a teorie grafů je oblast tzv. průnikových grafů. Existuje například věta, že každý rovinný graf lze reprezentovat jako průnikový graf osově rovnoběžných lomených čar s jediným zlomem. Pro mnohé, i celkem jednoduché, třídy průnikových grafů se ovšem neví, jestli existuje algoritmus, který by pro zadaný graf zjistil, zda pro něj existuje příslušná průniková reprezentace. Pro zkoumání této oblasti se hodí mít program, který pro zadaný graf zkonstruuje a přehledným způsobem zobrazí jeho průnikovou reprezentaci pomocí pevně daných geometrických objektů (například úseček s omezeným počtem směrů, či osově rovnoběžných lomených čar s omezeným počtem zlomů), případně rozhodne, že taková reprezentace neexistuje. V úvahu připadá i algoritmus hledající 'co nejlepší' geometrickou reprezentaci pomocí vhodného heuristického postupu. Program musí obsahovat jednak rozumný a efektivně implementovaný algoritmus generující zvolenou reprezentaci (testování existence netriviálních průnikových reprezentací je často NP-těžký problém) a jednak intuitivní grafické rozhraní pro zadávání vstupních grafů a zobrazování výstupních reprezentací.

Monte Carlo postupy generování náhodných kombinatorických objektů. Jednou z významných oblastí enumerativní kombinatoriky je zkoumání tříd permutací (nebo obecněji 01-matic, či ještě obecněji 01-vyplnění polyomin), které neobsahují nějaký pevně daný zakázaný vzor. Pro pochopení struktury takových permutací je často vhodné umět vygenerovat náhodnou permutaci (nebo matici nebo polyomino) dané (velké) délky bez zakázaného vzoru. Nedávno Madras a Liu popsali, jak lze generovat náhodnou posloupnost permutací pevné délky, která konverguje k rovnoměrně náhodné permutaci bez zvoleného zakázaného vzoru. Obdobný postup se dá využít i při práci s obecnějšími matematickými objekty. Cílem projektu by bylo vyvinout a implementovat pokud možno co nejefektivnější variantu postupu Madrase a Liu, případně vyvinout rozšíření tohoto postupu na obecnější třídy objektů.

Kuszmaulův algoritmus pro generování permutací bez zakázaných vzorů. V kombinatorice se často zkoumají permutace, které neobsahují daný zakázaný permutační vzor. Obecně není snadné zjistit, kolik existuje permutací dané délky neobsahujících daný zakázaný vzor. Nedávno navrhl W. Kuszmaul poměrně jednoduchý algoritmus, který řeší tuto otázku pro "ne moc dlouhé" permutace. Cílem projektu by bylo implementovat tento algoritmus, případně jej vhodně zobecnit na jiné kombinatorické objekty než permutace. Tento projekt může být přípravou na teoreticky orientovanou bakalářskou práci v oblasti kombinatoriky permutací.