Generátory náhodných čísel a kombinatorika na slovech

Nedávno byly navrženy generátory náhodných čísel, které vytvářejí aperiodické posloupnosti čísel. Tyto generátory využívají klasické (tedy periodické) generátory náhodných čísel a jejich výstupy míchají aperiodickým způsobem založeným na uspořádání písmen v aperiodickém nekonečném slově.

Studium tématu bylo započato v bakalářské práci J. Fialy (obhájené v únoru 2013). Byla nalezena vlastnost nekonečných slov, která garantuje, že generátory zkombinované podle takových nekonečných slov nemají mřížkovou strukturu. Na tématu spolupracují S. Puzinyna a M. Bucci z univerzity v Turku (kombinatorika na slovech) a bývalý student MFF UK J. Hladký (implementace generátorů). Při práci na tématu se objevilo mnoho otevřených otázek, na které bude hledat odpověď tato bakalářská či diplomová práce.

Cílem práce je studovat další souvislosti mezi nekonečnými slovy a vzniklými generátory a seznámit se statistickými prostředky pro testování generátorů a těmito testy porovnat kvalitu nových generátorů s periodickými generátory, z nichž vznikají.

Téma vyžaduje nastudování kombinatoriky na slovech a statistiky. Je vhodné pro teoretické matematiky, kteří budou dokazovat vztahy mezi nekonečnými slovy a vzniklými generátory, ale i pro zdatné programátory, kteří budou generátory implementovat a testovat.

1. Studium nejčastějších generátorů pseudonáhodných čísel (PRNG).
2. Seznámení se se statistickými testy PRNG.
3. Nastudování dosavadních výsledků týkajících se aperiodických PRNG.

Výzkumná část práce

1. V testech, ve kterých aperiodické PRNG uspějí lépe než periodické PRNG, jejichž kombinací vznikají, dokázat, proč tomu tak je.
2. Popsat souvislost mezi volbou periodických PRNG a aperiodického slova, podle kterého mícháme jejich výstupy, a vlastnostmi výsledného aperiodického PRNG.
3. Studovat generátory zkombinované podle vícepísmenných nekonečných slov (dosud byly studovány pouze generátory zkombinované podle slov binárních).

1. J. Fiala, Aperiodické generátory náhodných čísel, bakalářská práce FJFI ČVUT v Praze, 2013
2. D. E. Knuth, The Art of Computer Programming volume 2: Seminumerical Algorithms, 3rd ed, Addison-Wesley Boston etc., 1998
3. L. S. Guimond, J. Patera, Statistical Properties and Implementation of Aperiodic Pseudorandom Number Generators, Applied Numerical Mathematics 46(3-4) (2003), 295-318
4. L. S. Guimond, Jan Patera, Jiří Patera,Combining random number generators using cut and project sequences, Czechoslovak Journal of Physics 51(4) (2001), 305-311
5. L. S. Guimond, J. Patera, Proving the Deterministic Period Breakingof Linear Congruential Generators UsingTwo Tile Quasicrystals, Mathematics of Computation 71(237), (2002), 319-332