Enumerace ternárních balancovaných slov
| školitel: | prof. Ing. Edita Pelantová, CSc. |
| e-mail: | zobrazit e-mail |
| typ práce: | bakalářská práce, diplomová práce |
| zaměření: | MI_MM, MINF |
| klíčová slova: | sturmovská slova, ternární balancovaná slova, enumerace faktorů |
| popis: | Balancovaná slova hrají důležitou úlohu např. v navrhování výrobních schémat (viz téma Bc. práce s názvem Toyota problem), v diskretizaci spojitých geometrických útvarů pro účely jejich zobrazování na monitorech atp. Konstrukce balancovaných slov nad k prvkovou abecedou je dobře známa od roku 2000 (P. Hubert). Známý je rovněž počet balancovaných slov délky n nad dvouprvkovou abecedou (J. Berstel, M. Pacchiola). Analogicky výsledek není však znám pro víceprvkové abecedy. Cílem práce bude nastudovat konstrukci ternárních balancovaných slov a vytvořit program pro jejich generování. Seznámit se s různými důkazy enumerace binárních balancovaných slov. Na základě počítačového experimentu navrhnout horní a dolní odhady počtu ternárních balancovaných slov dané délky a pokusit se je odvodit. |
| literatura: | Arseny M. Shur: Languages with a Finite antidictionary: some growth Questions. Int. J. Found. Comput. Sci. 25(8): 937-954 (2014) Pascal Hubert: Suites équilibrées. Theor. Comput. Sci. 242(1-2): 91-108 (2000) Jean Berstel, Michel Pocchiola: A Geometric Proof of the Enumeration Formula for Sturmian Words. Int. J. Algebra Comput. 3(3): 349-356 (1993) |
| naposledy změněno: | 07.09.2022 17:10:29 |
za obsah této stránky zodpovídá:
Čestmír Burdík | naposledy změněno: 9.9.2021