 | Ve čtvrtek dne 4. září 2025 v době od 20:00 do 22:00 dojde k odstávce webového prostředí a databáze systému WhoIs. Odstávka systému WhoIs se dotkne též systému IS Studium, zejména nebude možné odevzdávání závěrečných prací. Zápisy do předmětů by neměly být jakkoliv ovlivněny. Omlouváme se za komplikace a děkujeme všem, kterých se odstávka jakkoliv dotkne, za pochopení. |
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. |