PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Kombinatorika na slovech - NMAG444
Anglický název: Combinatorics on Words
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Poznámka: předmět je možno zapsat mimo plán
Garant: doc. Mgr. Štěpán Holub, Ph.D.
Třída: M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Matematika > Algebra
Neslučitelnost : NALG083
Záměnnost : NALG083
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: T_KA (14.05.2013)
Přednáška je úvodem do kombinatorických vlastností volnych monoidů (resp. pologrup). Zabývá se především strukturou podmonoidů, homomorfismy a řešením rovnic. Z pokročilejších partií je věnován prostor ekvivalenčním množinám.
Podmínky zakončení předmětu
Poslední úprava: doc. Mgr. Štěpán Holub, Ph.D. (11.06.2019)

Předmět je zakončen ústní zkouškou.

Literatura
Poslední úprava: T_KA (14.05.2013)

C. Choffrut and J. Karhumäki, Combinatorics on words, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 329-438.

T. Harju and J. Karhumäki, Morphisms, in: Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. I, Springer-Verlag, Berlin Heidelberg 1997, pp. 439-510.

M. Lothaire, Combinatorics on words, Addison-Wesley, Reading Masachusetts, 1983.

M. Lothaire, Algebraic Combinatorics on words, Cambridge University Press, 2002.

J. Berstel and D. Perrin, Theory of Codes, Academic Press, London 1985.

Požadavky ke zkoušce -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (10.06.2019)

Student si vylosuje otázku ze seznamu témat. Po písemné přípravě otázku ústně zodpoví.

Sylabus -
Poslední úprava: T_KA (14.05.2013)

1. Vlastnosti podmonoidů volných monoidů. Definice kódu. Řád pologrupy. F-pologrupy. 2. Homomorfismy. Rovnice a její řešení. Systém rovnic a jejich ekvivalentní podsystémy. Věta o kompaktnosti ( "Ehrenfeuchtova hypotéza"). 3. Testovací množiny. Existence konečné testovací množiny. Ekvivalence s větou o kompaktnosti. 4. Postův problém (PCP) a jeho varianty. Binární ekvivalenční množiny a jejich struktura. Problém regularity ekvivalenčních množin.

Vstupní požadavky -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)

Základy obecné algebry.

 
Univerzita Karlova | Informační systém UK