Synchronizace automatů

• Název práce v jazyce práce (slovenština): Synchronizace automatů
• Název práce v češtině: Synchronizace automatů
• Název v anglickém jazyce: Synchronizing automata
• Akademický rok vypsání: 2012/2013
• Typ práce: bakalářská práce
• Jazyk práce: slovenš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í: 03.10.2012
• Datum zadání: 31.10.2012
• Datum potvrzení stud. oddělením: 23.11.2012
• Datum a čas obhajoby: 12.09.2013 00:00
• Datum odevzdání elektronické podoby: 01.08.2013
• Datum odevzdání tištěné podoby: 02.08.2013
• Datum proběhlé obhajoby: 12.09.2013
• Oponenti: RNDr. Michal Hojsík, Ph.D.

Zásady pro vypracování

Student popíše Trahtmanovo řešení problému barvení grafu a související barvící algoritmus. Zpracuje také známé informace o složitosti tohoto algoritmu.

Seznam odborné literatury

A.N. Trahtman,"An Algorithm for Road Coloring." J. of Discrete Algorithms, 16 (2012), Springer, 213--223
A.N. Trahtman, "Synchronizing road coloring", in: 5th IFIP WCC–TCS, 2008, in: SSCS, vol. 273, Springer, 2008, pp. 43–53.
A.N. Trahtman, "The road coloring problem", Israel J. Math. 172 (1) (2009) 51–60.
M.P. Béal, D. Perrin, "A quadratic algorithm for road coloring", arXiv:0803.0726v2 [cs.DM], 2008.