Lineární verze Holubova algoritmu

• Název práce v češtině: Lineární verze Holubova algoritmu
• Název v anglickém jazyce: Linear version of Holub's algorithm
• Klíčová slova: morfický rozklad, pevný bod, lineární algoritmus
• Klíčová slova anglicky: morphic factorization, fixed point, linear algorithm
• Akademický rok vypsání: 2019/2020
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Štěpán Holub, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 07.11.2019
• Datum zadání: 07.11.2019
• Datum potvrzení stud. oddělením: 21.11.2019
• Datum a čas obhajoby: 29.06.2020 10:00
• Datum odevzdání elektronické podoby: 04.06.2020
• Datum odevzdání tištěné podoby: 04.06.2020
• Datum proběhlé obhajoby: 29.06.2020
• Oponenti: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.

Zásady pro vypracování

Student se seznámí s lineární verzí algoritmu pro testování homomorfní primitivity slov. Popíše jeho fungování a implementuje ho.

Seznam odborné literatury

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Linear-time version of Holub's algorithm for morphic imprimitivity testing, Theoretical Computer Science 602, 7-21 (2015).
Štěpán Holub, Polynomial algorithm for fixed points of nontrivial morphisms, Discrete Mathematics 309, 5069-5076 (2009).
Vojtěch Matocha, Algoritmus pro pevné body homomorfismů na slovech, bakalářská práce, MFF UK, 2011.