Concetti Chiave
- Il paradigma divide et impera scompone problemi complessi in problemi più semplici, risolvibili con algoritmi ricorsivi.
- Esistono due approcci: "divide and conquer", che riduce la complessità del problema con un valore maggiore di 1, e "decrease and conquer", che diminuisce la complessità di uno per passo.
- Algoritmi comuni che utilizzano questo paradigma includono il calcolo del fattoriale, il massimo comun divisore e i numeri di Fibonacci.
- Altri algoritmi, come il problema delle torri di Hanoi, sono meno efficaci con il paradigma divide et impera per problemi di grandi dimensioni.
- Il paradigma è particolarmente utile per problemi che possono essere facilmente scomposti e le cui soluzioni possono essere ricombinate.
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
