| Meno: | Mirko
|
|---|
| Priezvisko: | Zibolen
|
|---|
| Názov: | Šírenie správ na grafoch s proporcionálnym počtom chybných liniek
|
|---|
| Vedúci: | Doc. RNDr. Rastislav Královič, PhD.
|
|---|
| Rok: | 2008
|
|---|
| Blok: | APV
|
|---|
| Kľúčové slová: | šírenie správ, porporcionálny počet chybných liniek, algoritmus spätného šírenia, algoritmus dopredného šírenia, odolnosť voči chybám
|
|---|
| Abstrakt: | Práca sa zaoberá analýzou rôznych aspektov šírenia správ v sieťach s chybnými linkami. Používaný model pripúšťa v každom kroku počet chybných liniek proporcionálne závislý od počtu poslaných správ. Pozornosť je sústredená najmä na všeobecné algoritmy šírenia správ. Analyzujeme ich správanie na rôznych typoch grafov. Práca sumarizuje známe poznatky o greedy algoritme a hľadá prípady, v ktorých poskytuje zlé výsledky. Prezentuje algoritmus spätného šírenia, ktorý garantuje asymptoticky optimálny čas šírenia správy na acyklických grafoch. Hlbšie si všímame aj ďalšie triedy grafov - stromy s konštantnou excentricitou iniciátora a hyperkocky - ktoré sú analyzované tak z pohľadu greedy algoritmu, ako aj z pohľadu optimálneho algoritmu.
|
|---|