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 - e più precisamente nell'analisi e nel progetto del software - il principio del divide et impera (detto anche approccio top-down, "dall'alto in basso") consiste nel definire l'algoritmo complessivo o l'architettura di un sistema software secondo il seguente procedimento ricorsivo: si suddivide il problema dato in sottoproblemi di dimensione inferiore (e quindi di più agevole risoluzione), procedendo ricorsivamente finché i sottoproblemi non sono sufficientemente semplici da essere risolti direttamente; quindi, si combinano le soluzioni al fine di ottenere la soluzione al problema dato.
Il principio del divide et impera applicato allo sviluppo del software prende il nome di sviluppo per raffinamenti successivi.
Come caso particolare, è possibile che un problema si possa scomporre in sottoproblemi della stessa natura del problema originale. Per esempio, la visita (attraversamento) di un albero binario può essere scomposta come segue:
- visita del sottoalbero di sinistra;
- visita della radice dell'albero;
- visita del sottoalbero di destra.
In casi come questo, l'espressione divide et impera può anche essere riferita alla natura stessa dell'algoritmo usato (che divide l'insieme dei dati da trattare, elaborandone una parte per volta) piuttosto che al processo con cui l'algoritmo viene progettato. In questa accezione, "algoritmo basato sul divide et impera" diventa sinonimo di algoritmo ricorsivo.
Il progetto top-down, dominante nell'ingegneria del software degli anni Sessanta e Settanta è oggi meno apprezzato in quanto poco adatto a favorire la riusabilità e il riuso del software; a questo proposito, vedi progetto bottom-up.
