Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 308)
Detail práce
  
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Název práce v češtině: Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Název v anglickém jazyce: Hamiltonian cycles in hypercubes with removed vertices
Klíčová slova: hyperkrychle, vadný vrchol, Hamiltonovská laceabilita, izometrický cyklus, izometrický strom
Klíčová slova anglicky: hypercube, fault tolerance, Hamiltonian laceability, isometric cycle, isometric tree
Akademický rok vypsání: 2012/2013
Typ práce: bakalářská práce
Jazyk práce: angličtina
Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Vedoucí / školitel: doc. Mgr. Petr Gregor, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 24.10.2012
Datum zadání: 31.10.2012
Datum potvrzení stud. oddělením: 23.11.2012
Datum a čas obhajoby: 20.06.2013 00:00
Datum odevzdání elektronické podoby:20.05.2013
Datum odevzdání tištěné podoby:21.05.2013
Datum proběhlé obhajoby: 20.06.2013
Oponenti: doc. RNDr. Tomáš Dvořák, CSc.
 
 
 
Zásady pro vypracování
Využití hyperkrychlí jako propojovacích sítí vede ke studiu jejich robustnosti vzhledem k výskytům chybných vrcholů. Obvyklý počet tolerovatelných chyb je lineární vzhledem k dimenzi hyperkrychle. U hamiltonovských problémů je ale možné dosáhnout exponenciálního počtu, pokud odstraněné vrcholy splňují jisté podmínky na svou vzdálenost. Cílem práce je seznámit se s výsledky v této oblasti a některé snadnější zesílit či zobecnit.
Seznam odborné literatury
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, California (1992).

P. Gregor and R. Škrekovski, Long cycles in hypercubes with distant faulty vertices, Discrete Mathematics & Theoretical Computer Science 11 (2009), 185-198.

T. Dvořák and P. Gregor. Hamiltonian fault-tolerance of hypercubes, Electronic Notes in Discrete Mathematics 29 (2007), 471-477.
 
Univerzita Karlova | Informační systém UK