Divide et impera (informatica)
Da Wikipedia, l'enciclopedia libera.
Divide et impera (locuzione in lingua latina «dividi e domina») viene talvolta tradotto in italiano anche come dividi e impera, separa e conquista o dividi e conquista (che traduce anche l'espressione inglese analoga, sebbene non strettamente equivalente, divide and conquer).
In informatica il divide et impera rappresenta un approccio molto potente per la risoluzione di vari problemi computazionali. In particolare si parla di algoritmi divide et impera. Questi algoritmi dividono ricorsivamente un problema in due o più sotto-problemi sino a che questi ultimi diventino di semplice risoluzione, quindi, si combinano le soluzioni al fine di ottenere la soluzione del problema dato. Questo approccio permette di affrontare in modo "semplice" problemi anche molto complessi, inoltre la natura del "divide" permette di parallelizzare la computazione aumentandone l'efficienza su sistemi distribuiti o multiprocessore. Questo tipo di approccio è di tipo top down in contrapposizione al paradigma di programmazione dinamica che risolve prevalentemente problemi in maniera bottom up.
Un programma sviluppato secondo questa tecnica è sostanzialmente diviso in tre parti:
- Caso base: posto all'inizio della funzione da sviluppare, e risolve in modo diretto il problema qualora la taglia risulti inferiore alla soglia prevista;
- Divide: in questa parte si procede alla suddivisione dell'input in altri di taglia inferiore e alla chiamata ricorsiva della stessa procedura con l'input appena creato;
- Impera: l'ultima fase del paradigma prevede di ricombinare l'output ottenuto dalle precedenti chiamate ricorsive al fine di ottenere il risultato finale.
In informatica questo principio viene applicato in modo diffuso per la risoluzione di molteplici problemi. Le applicazioni più conosciute, sono due dei più usati algoritmi di ordinamento, il quick sort e il merge sort, oltre che l'algoritmo veloce per il calcolo della Trasformata discreta di Fourier (FFTs).
Si può parlare anche di divide et impera applicato al campo dell'analisi e del progetto del software.
