Makaninův a Plandowského algoritmy
| Thesis title in Czech: | Makaninův a Plandowského algoritmy |
|---|---|
| Thesis title in English: | Makanin's and Plandowski's algorithms |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Štěpán Holub, Ph.D. |
| Author: |
| Guidelines |
| Makaninův algoritmus a Plandowského algoritmus jsou dva algoritmy rozhodující, zda daná rovnice ve slovech má řešení. Protože problém je sám o sobě NP-těžký, nejsou určitě praktické v nejhorším případě. Velmi málo je však známo o jejich chování v "typickém" případě. Cílem práce by bylo porozumět struktuře některého z algoritmů a popsat jeho chování na zvolených případech. Zajímavé by bylo nalezení nějakých typů rovnic, pro něž jsou algoritmy reálně použitelné.
Téma bude upřesněno dohodou. |
| References |
| V. Diekert. Makanin's Algorithm. In M. Lothaire, editor, Algebraic Combinatorics on Words. Cambridge University Press, 2001.
Předběžná verze: www-igm.univ-mlv.fr/~berstel/Lothaire/ChapitresACW/C12.ps Wojciech Plandowski: An efficient algorithm for solving word equations. STOC 2006: 467-476 |