Original title:
Generování náhodných matic bez zakázaných vzorů
Translated title:
Generating random pattern-avoiding matrices
Authors:
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee) Document type: Bachelor's theses
Year:
2016
Language:
eng Abstract:
[eng][cze] Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
Keywords:
Markov chain; Monte Carlo method; pattern-avoidance; Markovovy řetězce; metoda Monte Carlo; zakázané vzory
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/80122