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:

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:

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:

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:

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:

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.