Paradigma Divide et impera


Il paradigma divide et impera è un paradigma di programmazione per il problem solving su problemi complessi, spesso utilizzato in algoritmi con funzionamento ricorsivo; il paradigma divide et impera consiste nella scomposizione di un problema complesso in più problemi di complessità minore (possibilmente di complessità elementare così da essere facilmente risolvibili), ed infine ricombinare la soluzione cercata.
Tale paradigma può funzionare secondo due diversi dettami di funzionamento, il divide and conquer ed il decrease and conquer.
Il divide and conquer funziona come una ricorsione multivia con fattore o valore di riduzione maggiore di 1 ed ad ogni passo il problema si riduce di complessità coerentemente con il suo fattore di riduzione, differentemente il decrease and conquer effettua una semplice ricorsione lineare con fattore di riduzione uguale ad 1 e quindi ad ogni passo la sua complessità diminuisce di uno fino al grado di complessità elementare conosciuto per il problema in oggetto.
Alcuni esempi di semplici algoritmi che sfruttano il paradigma divide et impera sono:
  • Il calcolo del fattoriale
  • Il massimo comun divisore
  • I numeri di Fibonacci
  • Il determinante di una matrice

Vi sono anche altri algoritmi che sfruttano il paradigma divide et impera, con risultati però molto meno soddisfacenti se il problema supera certe dimensioni, come il problema delle torri di Hanoi o il gioco delle 8 regine.
Hai bisogno di aiuto in Informatica?
Trova il tuo insegnante su Skuola.net | Ripetizioni
Registrati via email