Cílem práce je vyvinout metodu, která umožní generovat náhodné binární matice neobsahující zadané podmatice, pomocí vhodné varianty schématu Markov chain Monte Carlo. Obsahem práce bude jak teoretický návrh, včetně důkazu správnosti, tak i následná praktická implementace. Metoda použitá ke generování náhodných matic musí být teoreticky dokazatelně korektní, tj. navržený Markovův řetězec musí mít dokazatelně stacionární rozdělení totožné s rovnoměrným rozdělením na uvažované třídě matic. Zároveň musí být implementace této metody v maximální možné míře optimalizovaná, aby umožnila praktické použití pro co největší velikost generovaných matic. Implementovaný algoritmus musí dostatečně efektivně pracovat pro zcela libovolný zakázaný vzor, ale zároveň by měl obsahovat i specializované efektivnější implementace klíčových procedur fungující pro vzory se speciální strukturou.
Seznam odborné literatury
Neal Madras and Hailong Liu: Random pattern-avoiding permutations, Contemporary Mathematics 520 (2010), 173-194.
Další aktuální časopisecká literatura dle pokynů vedoucího.
- zadáno a potvrzeno stud. odd.