Mgr. Michal Opler, Ph.D.

V poslední době začínáme lépe rozumět vztahu mezi strukturálními vlastnostmi grafů a složitostí grafových problémů. Jako příklad lze uvést efektivnější algoritmy pro řadu úloh na rovinných grafech či grafech s omezenou stromovou šířkou. Cílem práce je zkoumat, jak lze podobné strukturální vlastnosti využít při návrhu efektivních algoritmů, případně k dokázání jejich neexistence za standardních složitostních předpokladů. Uvažované problémy mohou sahat od klasických grafových úloh, jako jsou různé varianty barvení, až po prakticky motivované problémy, například multiagentní plánování nebo návrh dopravních sítí.

Cílem práce je zkoumat strukturální vlastnosti dědičných tříd permutací a jejich využití při analýze složitosti algoritmických problémů a enumeraci. Jedním z předpokládaných nástrojů je konečná teorie modelů, zejména prostřednictvím monadické logiky druhého řádu a interpretací — přístup, který v poslední době vedl k řadě významných výsledků v teorii grafů.

Mgr. Michal Opler, Ph.D.

doc. RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

V bakalářské práci představíme problém Min Power Symmetric connectivity (MinPSC), který je na obecných grafech NP-těžký. Problém MinPSC má uplatněni v sítích, kde pro daný uzel chceme zmenšit jeho spotřebu energii na co nejmenší úroveň a požadujeme přitom, aby každý uzel mohl komunikovat s ostatními. V této práci zkoumáme problém MinPSC ze pohledu dvou strukturálních parametru. A to z vrcholového pokrytí a sousedské různorodosti.

Práce na DSpace

Mgr. Michal Opler, Ph.D.

doc. RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

V této bakalářské práci se zabýváme problémem průzkumu nekonečných mřížek skupinami plně synchronních robotů. Tito roboti mají poměrně omezené schopnosti. Jsou dezorientovaní, nemají paměť, mají pouze omezený rozhled, nedokáží mezi sebou přímo komunikovat a nesmí do sebe při průzkumu narazit. Mají ovšem světlo, které dokáže nabývat několika různých barev a je viditelné pro ostatní roboty. Zaměrujeme se především na nekonečné trojúhelníkové a šestiúhelníkové mřížky. V trojúhelníkové mřížce představujeme tři nové algoritmy. Každý je optimální vzhledem k nějakému parametru, a to k počtu barev, vzdálenosti rozhledu a počtu robotů. Všechny tyto algoritmy pracují s roboty fixních barev a s deterministickými pravidly pro pohyb robotů. Také představujeme první algoritmus, který řeší nekonečný průzkum v šestiúhelníkové mřížce. Používá optimální počet robotů a výhradně deterministická pravidla. Nakonec diskutujeme o možném řešení v šestiúhelníkové mřížce za nejmenší možné viditelnosti.

Práce na DSpace