| Abstrakt: | V práci reprezentujeme sieť pomocou jednoduchého neorientovaného grafu. V
tejto sieti vrcholy nemajú žiadne identifikátory, a teda z pohľadu siete sú
rovnaké. Jediné používané identifikátory sú označenia hrán z pohľadu
vrcholu, tie musia byť jednoznačné (toto voláme lokálna orientácia). Ďalej
definujeme jednoduchého agenta -- tzv. RH-agenta, ktorý sa v tomto grafe
pohybuje podľa pravidla pravej ruky (z vrcholu vždy odíde hranou
nasledujúcou po tej, ktorou prišiel). Naším cieľom je navrhnúť algoritmus
pre agenta -- predpočítavateľa, ktorý je vložený do grafu pred RH-agentom a
jeho cieľom je výmenami identifikátorov hrán vo vrcholoch zabezpečiť, aby sa
RH-agent v grafe vedel svojím prechádzaním dostať do všetkých vrcholov.
Tento cieľ sa snažíme dosiahnuť s minimalizáciou množstva použitej pamäte.
Ukazujeme polynomiálny algoritmus riešiaci náš problém, ktorý potrebuje na
predspracovanie grafu s $N$ vrcholmi $O(\log N)$ pamäte pre predpočítavateľa
a jeden pebble. Ďalej ukazujeme, ako sa dá tento algoritmus upraviť tak, aby
stačilo $O(1)$ pamäte pre predpočítavateľa. V tomto prípade nie je vyriešené
zastavenie predpočítateľa v takej malej pamäti.
|
|---|