Název:
Lineární verze Holubova algoritmu
Překlad názvu:
Linear version of Holub's algorithm
Autoři:
Tvrdý, David ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
cze
Abstrakt: [cze][eng] Tato práce studuje lineární algoritmus, který pro zadané slovo rozhodne, zda existuje netriviální homomorfismus, jehož je dané slovo pevným bodem. Dále jsou v práci popsány pomocné datové struktury, které jsou pro lineární časovou složitost důležité. Součástí práce je i vlastní implementace tohoto algoritmu v jazyce Java včetně vizualizace chodu algoritmu pro konkrétní vstupy. 1This work studies a linear agorithm which decides if a given word is a fixed point of any nontrivial morphism. This work also contains a description of auxiliary data structures which are crucial for linear time complexity of the algorithm. A Java implementation of the algorithm is provided along with a step-by-step visualization for particular input words. 1
Klíčová slova:
lineární algoritmus; morfický rozklad; pevný bod; fixed point; linear algorithm; morphic factorization