Informatická I
24. 9. 2008
Mala programatorska pohadka o hladovem algoritmu
Matous Jirak
Existovalo jednou jedno kralovstvi K jakozto mnozina vsech konecnych grafu
G=(V,E); [tex2html_wrap_inline1445] . Kralovstvi po dlouha leta moudre a
prozirave kraloval monarcha Petersenuv graf.
Jak uz to u panovniku byva, mivaji nekdy dceru nebo syna, pro ktere
zvelebuji sve panstvi. Nas vladar Petersenuv graf byl stastnym otcem jedne
dcery, krasne Fanovy roviny. Ta zrovna slavila dvacetiny a uz se ohlizela
po napadnicich.
Jako na potvoru, prave kdyz s tatinkem prisli na bajecny napad usporadat
pro rytire a prince z okolnich kralovstvi hostinu a pak pomoci axiomu
vyberu z nich vybrat toho praveho, donesla se k uchu mocnarovu zla novina -
hranice kralovstvi prekrocil smerem dovnitr zly hladovy algoritmus HA a
zere lidi. Vzkazuje pry, ze nedostane-li princeznu Fanynku, jak Fanove
rovine take rikali, za manzelku, sni cele kralovstvi.
Kral lomil rukama i nohama. Princezna se nejdriv poptavala dvoranstva,
jakze ten hladovy algoritmus vlastne vypada, byla zvedava; jakmile ji vsak
ukazali fotografii, zhrozila se: ``Takovy otesanek! Toho si nevezmu, ani
kdyby me mel sezrat.''
Co vsak bylo platno lametovani! HA se kolebal krajem, zral lidi, zvirectvo
a vyplivovsl jenom kosticky. Kdyz potkal strom, popadnul ho za koreny,
strcil do ust, povalel trochu na jazyku a zase vyplivnul. Z jabloni sklidil
aspon jablka, z jehlicnanu otrhal vsechny sisky. Kraj pustnul a povalovaly
se v nem jen same kostry, ktere slunce brzy vysisovalo dobela.
Jak se HA blizil ke kralovskemu mestecku, zavladla panika i tam. Kral
svolal vsechny dvorany, ctihodne eulerovske grafy, bral si na pomoc vetu o
skore, vetu o potrasani rukou i lemma o usich, bral Kuratowskeho vetu
nadarmo, ale nebylo mu to co platno. Az jeden dvoran, eulerovsky multigraf,
poradil mu navstivit mocnou carodejku rekurzi, kterazto se skryva hluboko v
lesich binarnich dokonale vyvazenych stromu.
Tonouci se i stebla chyta, i chytil se kral rady, nazul pohory a vydal se
do hlubokych modrinovych haju dokonale vyvazenych stromu, kdezto nasel nad
kotlikem s nejakym podezrelym svinstvem sedet maticku rekurzi. Pekne
pozdravil, a jal se rekurzi slibovat vysokych odmen, pomuze-li mu hladoveho
algoritma zahubit nebo aspon vypudit za hranice mnoziny K.
Jenze s rekurzi nebyla kloudna rec. Sotva ji clovek neco rekl, zavolala
treba stokrat sama sebe, a po navratu z rekurze uz nevedela vubec nic.
Dokonce zapomnela i na vareni a recene svinstvo v kotliku se ji palilo a
pachlo, az z binarnich stromu padali mrtvi spacci, drozdi a suvy.
S neporizenou odsoural se kral. Smutne dosedl na trun, sepsal zavet, pak si
zul trepky, odlozil korunu a zalezl pod perinu, aby jeho zrak zustal
usetren pohledu na tu spoust, co zde za chvili HA natropi.
Zatim se do kralovstvi K pritoulal z algebry jeden slicny a rovnez urozeny
monoid, ktery byl krome toho take chytry a vsemi mastmi mazany. Podival se
opatrne, jak je HA implementovan a vsiml si, ze hladovy algoritmus muze
snist jen graf s nezapornym ohodnocenim hran. A tak se podrbal na hlave,
vyklepal z kapes par peknych zapornych cisel a ohodnotil jimi jednu tucnou
kravu na kraji pole kousek od mista, kde zrovinka HA konzumoval ponekud
tuhou slepici.
``Aaa, papani!'' zajasal HA , vida kravu na kraji pole, a pustil se do ni,
jenze beda!, zaporne ohodnoceni zpusobilo behovou chybu, algoritmu se
udelalo spatne a zacal cyklit, cyklil a cyklil, a jak cyklil, tak nemohl
jist, a tak byl cim dal hladovejsi a hladovejsi, az nakonec docela chcipnul
hlady.
Kral, kdyz ho dvorane radostne vytahli zpod kralovskych duchen, potrasl
princi monoidu po zasluze rukou (podle vety o potrasani rukou) a po
patetickem projevu diku a uznani ho za pomoci axiomu vyberu vybral coby
zenicha pro Fanovu rovinu, jiz se slisny monoid od zacatku libil.
Nemohlo nasledovat nic jineho nez svatba, vsemi sitemi tekly velke toky
piva, vina i koralky, kecupu i horcice, sjeli se vsichni pribuzni
novomanzelskeho paru, prijel i strycek K3,3 s
tetickou K5 .
Ani na mocnou carodejku rekurzi pritom nezapomneli. Poslali ji mailem
zalozni buffer, ve kterem by si mohla pamatovat, co zrovna vari a kdo ji
odkud vola.
Matous Jirak
Existovalo jednou jedno kralovstvi K jakozto mnozina vsech konecnych grafu
G=(V,E); [tex2html_wrap_inline1445] . Kralovstvi po dlouha leta moudre a
prozirave kraloval monarcha Petersenuv graf.
Jak uz to u panovniku byva, mivaji nekdy dceru nebo syna, pro ktere
zvelebuji sve panstvi. Nas vladar Petersenuv graf byl stastnym otcem jedne
dcery, krasne Fanovy roviny. Ta zrovna slavila dvacetiny a uz se ohlizela
po napadnicich.
Jako na potvoru, prave kdyz s tatinkem prisli na bajecny napad usporadat
pro rytire a prince z okolnich kralovstvi hostinu a pak pomoci axiomu
vyberu z nich vybrat toho praveho, donesla se k uchu mocnarovu zla novina -
hranice kralovstvi prekrocil smerem dovnitr zly hladovy algoritmus HA a
zere lidi. Vzkazuje pry, ze nedostane-li princeznu Fanynku, jak Fanove
rovine take rikali, za manzelku, sni cele kralovstvi.
Kral lomil rukama i nohama. Princezna se nejdriv poptavala dvoranstva,
jakze ten hladovy algoritmus vlastne vypada, byla zvedava; jakmile ji vsak
ukazali fotografii, zhrozila se: ``Takovy otesanek! Toho si nevezmu, ani
kdyby me mel sezrat.''
Co vsak bylo platno lametovani! HA se kolebal krajem, zral lidi, zvirectvo
a vyplivovsl jenom kosticky. Kdyz potkal strom, popadnul ho za koreny,
strcil do ust, povalel trochu na jazyku a zase vyplivnul. Z jabloni sklidil
aspon jablka, z jehlicnanu otrhal vsechny sisky. Kraj pustnul a povalovaly
se v nem jen same kostry, ktere slunce brzy vysisovalo dobela.
Jak se HA blizil ke kralovskemu mestecku, zavladla panika i tam. Kral
svolal vsechny dvorany, ctihodne eulerovske grafy, bral si na pomoc vetu o
skore, vetu o potrasani rukou i lemma o usich, bral Kuratowskeho vetu
nadarmo, ale nebylo mu to co platno. Az jeden dvoran, eulerovsky multigraf,
poradil mu navstivit mocnou carodejku rekurzi, kterazto se skryva hluboko v
lesich binarnich dokonale vyvazenych stromu.
Tonouci se i stebla chyta, i chytil se kral rady, nazul pohory a vydal se
do hlubokych modrinovych haju dokonale vyvazenych stromu, kdezto nasel nad
kotlikem s nejakym podezrelym svinstvem sedet maticku rekurzi. Pekne
pozdravil, a jal se rekurzi slibovat vysokych odmen, pomuze-li mu hladoveho
algoritma zahubit nebo aspon vypudit za hranice mnoziny K.
Jenze s rekurzi nebyla kloudna rec. Sotva ji clovek neco rekl, zavolala
treba stokrat sama sebe, a po navratu z rekurze uz nevedela vubec nic.
Dokonce zapomnela i na vareni a recene svinstvo v kotliku se ji palilo a
pachlo, az z binarnich stromu padali mrtvi spacci, drozdi a suvy.
S neporizenou odsoural se kral. Smutne dosedl na trun, sepsal zavet, pak si
zul trepky, odlozil korunu a zalezl pod perinu, aby jeho zrak zustal
usetren pohledu na tu spoust, co zde za chvili HA natropi.
Zatim se do kralovstvi K pritoulal z algebry jeden slicny a rovnez urozeny
monoid, ktery byl krome toho take chytry a vsemi mastmi mazany. Podival se
opatrne, jak je HA implementovan a vsiml si, ze hladovy algoritmus muze
snist jen graf s nezapornym ohodnocenim hran. A tak se podrbal na hlave,
vyklepal z kapes par peknych zapornych cisel a ohodnotil jimi jednu tucnou
kravu na kraji pole kousek od mista, kde zrovinka HA konzumoval ponekud
tuhou slepici.
``Aaa, papani!'' zajasal HA , vida kravu na kraji pole, a pustil se do ni,
jenze beda!, zaporne ohodnoceni zpusobilo behovou chybu, algoritmu se
udelalo spatne a zacal cyklit, cyklil a cyklil, a jak cyklil, tak nemohl
jist, a tak byl cim dal hladovejsi a hladovejsi, az nakonec docela chcipnul
hlady.
Kral, kdyz ho dvorane radostne vytahli zpod kralovskych duchen, potrasl
princi monoidu po zasluze rukou (podle vety o potrasani rukou) a po
patetickem projevu diku a uznani ho za pomoci axiomu vyberu vybral coby
zenicha pro Fanovu rovinu, jiz se slisny monoid od zacatku libil.
Nemohlo nasledovat nic jineho nez svatba, vsemi sitemi tekly velke toky
piva, vina i koralky, kecupu i horcice, sjeli se vsichni pribuzni
novomanzelskeho paru, prijel i strycek K3,3 s
tetickou K5 .
Ani na mocnou carodejku rekurzi pritom nezapomneli. Poslali ji mailem
zalozni buffer, ve kterem by si mohla pamatovat, co zrovna vari a kdo ji
odkud vola.
