Scomposizione funzionale
La scomposizione funzionale è una metodologia di analisi dei problemi, basata sulla scomposizione di un problema complesso in più sottoproblemi elementari. È una metodologia di analisi utilizzata nella programmazione informatica nello sviluppo degli algoritmi di risoluzione dei problemi ( problem solving ) ed è alla base dell'euristica additiva. Nell'analisi del problema l'analista informatico individua nel problema generale la presenza degli eventuali sottoproblemi, tali da poter essere scorporati dal problema generale e risolti in modo indipendente ( scomposizione in sottoproblemi ). Ogni sottoproblema deve essere indipendente dagli altri, in caso contrario la sua risoluzione non potrebbe essere isolata e separata dal problema generale ( sottoproblemi indipendenti ). Ogni sottoproblema indipendente, a sua volta, può essere scomposto in altri sottoproblemi indipendenti di grado inferiore, e così via. Questo processo consente di scomporre un problema generale complesso in un insieme di sottoproblemi indipendenti elementari che possono essere risolti in modo isolato. Per risolvere ogni singolo sottoproblema viene sviluppato un sottoprogramma/algoritmo specifico.
La soluzione di tutti i sottoproblemi ( down ) consente, indirettamente, di concorrere alla soluzione del problema complesso ( top ) da cui derivano. Il problema complesso ( top ) è caratterizzato da un elevato livello di astrazione. Man mano che il processo di scomposizione funzionale lo suddivide in sottoproblemi, questi sono caratterizzati da un livello di dettaglio superiore ma anche da un maggiore grado di semplicità nella risoluzione. Questa metodologia di analisi dei problemi è anche detta top-down. In tal modo, l'operazione di sviluppo dei sottoprogrammi ( es. SP1, SP2 e SP3 ) necessari per risolvere ogni singolo sottoproblema elementare, è più semplice rispetto allo sviluppo di un unico programma informatico in grado risolvere il problema generale.
Minore complessità di calcolo. Un problema composto da n variabili, ognuna delle quali ha una dimensione del dominio pari a d, richiede un tempo di elaborazione pari a O(dn). La complessità del lavoro cresce in modo esponenziale con il numero delle variabili (n). Suddividendo il problema in c sottoproblemi indipendenti, ogni dei quali è composto da c/n variabili, il tempo di elaborazione è pari a O(dc·c/n). In questo caso la complessità del lavoro cresce in modo lineare con il numero delle variabili (n) ed è, pertanto, più semplice da risolvere rispetto al primo caso.
Sottoproblema privo di soluzione. Quando un sottoproblema su N sottoproblemi non ha soluzione, nemmeno il problema generale ha una soluzione, anche se i restanti N-1 sottoproblemi sono risolvibili. La soluzione del problema generale ( top ) è possibile soltanto se tutti gli N sottoproblemi indipendenti ( down ) possono essere risolti indipendentemente l'uno dall'altro.
I sottoproblemi indipendenti sono rari. I sottoproblemi indipendenti sono abbastanza rari. È molto più frequente scomporre un problema generale in una collezione di sottoproblemi vincolati ( dipendenti ). Nel caso dei sottoproblemi vincolati ( sottoproblemi dipendenti ) la soluzione di tutti i sottoproblemi è una condizione necessaria ma non sufficiente a risolvere il problema generale. È necessario verificare anche la consistenza delle soluzioni dei sottoproblemi nei confronti dei vincoli che legano tra loro i sottoproblemi. Una metodologia di scomposizione funzionale in problemi vincolai è la tecnica del soddisfacimento dei vincoli distribuiti degli algoritmi CSP.
