Smanjivanje grafova

Из Википедије, слободне енциклопедије

U računarstvu, redukcija grafova predstavlja efikasnu verziju non'strict evaluacije, strategije izračunavanja gde se argumentima funkcije ne dodeljuje vrednost odmah. Ova forma evaluacije se naziva 'lenjo izračunavanje' i koristi se u funkcionalnom programiranju. Ovu tehniku je razvio Kris Wadswort 1971 godine.

Motivacija[уреди]

Prost primer evaluacije aritmetičkog izraza:


\begin{align}
& {} \qquad ((2+2)+(2+2))+(3+3) \\
& {} =((2+2)+(2+2))+ 6 \\
& {} =((2+2)+ 4)+6 \\
& {} =(4+4)+6 \\
& {} =8+6 \\
& {} =14
\end{align}

Gornji primer prikazuje strategiju poznatu kao redukcija krajnjeg drveta. Isti izraz se može izračunati koristeći redukciju najdubljeg kraja drveta, prikazanu u sledećem primeru:


\begin{align}
& {} \qquad ((2+2)+(2+2))+(3+3) \\
& {} = ((2+2)+4)+(3+3) \\
& {} = (4+4)+(3+3) \\
& {} = (4+4)+6 \\
& {} = 8+6 \\
& {} = 14
\end{align}

Primetimo da redosled redukcije se eksplicitno zadaje dodavanjem zagrada. Ovaj izraz se mogao jednostavno izračunati sa desna na levo jer je sabiranje asocijativna operacija.

Predstavljeni kao stablo, gornji izraz izgleda ovako:

Expression Tree.svg

Odavde dolazi termin redukcije stabla.

Kada predstavljena kao stablo, možemo posmatrati redukciju najdubljeg dela kao da ide od dna ka vrhu, dok redukcija najudaljenijeg dela ide od vrha ka dnu.

Izaz se takodje može predstaviti kao struktura podatakagraf, sto omogućava podizrazima da se medjusobno povezuju:

Expression Graph.svg

Sto se tiče stabla, redukcija najudaljenijeg i najdubljeg dela se takodje može primeniti na grafove.


Sada evaluacija koja koristi redukciju najudaljenijeg može izgledati ovako:

Expression Graph Reduction.svg

Primetimo da izračunavanje sada zahteva samo 4 koraka.Redukcija najudaljenijeg dela grafa se naziva lenjo izračunavanje a redukcija najdubljeg dela grafa se naziva nestrpljivo izračunavanje.

Kombinatorna redukcija grafa[уреди]

Kombinatorna redukcija grafa je osnovna tehnika imeplementacije u jezicima funkcionalnog programiranja, u kojima se program prevodi u kombinatornu reprezentaciju koja se preslikava u usmereni graf u memoriji računara, a izvršavanje programa se sastoji od prepisivanja delova ovog grafa (smanjujući ga) tako da se kreće ka potrebnim rezultatima.


Istorija[уреди]

Koncept redukcije grafa koji dozvoljava izračunatim vrednostima da se dalje medjusobno povezuju je prvi razvio Kris Wadsort u svojoj doktorskoj disertaciji.