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 efficace 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 difficili (non complessi, dove la complessità sia irriducibile o non-lineare), 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:

  • Divide: in questa parte si procede alla suddivisione dei problemi in problemi di dimensione minore;
  • Impera: nella seconda parte i problemi vengono risolti in modo ricorsivo. Quando i sottoproblemi arrivano ad avere una dimensione sufficientemente piccola, essi vengono risolti direttamente tramite il caso base;
  • Combina: 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.

Voci correlate[modifica | modifica sorgente]