Смањивање графова

У рачунарству, редукција графова представља ефикасну верзију нон'стрицт евалуације, стратегије израчунавања где се аргументима функције не додељује вредност одмах. Ова форма евалуације се назива 'лењо израчунавање' и користи се у функционалном програмирању. Ову технику је развио Крис Wадсwорт 1971 године.

Мотивација

Прост пример евалуације аритметичког израза:

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

Горњи пример приказује стратегију познату као редукција крајњег дрвета. Исти израз се може израчунати користећи редукцију најдубљег краја дрвета, приказану у следећем примеру:

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

Приметимо да редослед редукције се експлицитно задаје додавањем заграда. Овај израз се могао једноставно израчунати са десна на лево јер је сабирање асоцијативна операција.

Представљени као стабло, горњи израз изгледа овако:

Одавде долази термин редукције стабла.

Када представљена као стабло, можемо посматрати редукцију најдубљег дела као да иде од дна ка врху, док редукција најудаљенијег дела иде од врха ка дну.

Изаз се такодје може представити као структура податакаграф, сто омогућава подизразима да се медјусобно повезују:

Сто се тиче стабла, редукција најудаљенијег и најдубљег дела се такодје може применити на графове.

Сада евалуација која користи редукцију најудаљенијег може изгледати овако:

Приметимо да израчунавање сада захтева само 4 корака.Редукција најудаљенијег дела графа се назива лењо израчунавање а редукција најдубљег дела графа се назива нестрпљиво израчунавање.

Комбинаторна редукција графа

Комбинаторна редукција графа је основна техника имеплементације у језицима функционалног програмирања, у којима се програм преводи у комбинаторну репрезентацију која се пресликава у усмерени граф у меморији рачунара, а извршавање програма се састоји од преписивања делова овог графа (смањујући га) тако да се креће ка потребним резултатима.

Историја

Концепт редукције графа који дозвољава израчунатим вредностима да се даље медјусобно повезују је први развио Крис Wадсорт у својој докторској дисертацији.