Divide et impera (informatică)

Divide et impera (în italiană «divide and dominate», «divide and rule», «separate and conquer» sau «divide and conquer») indică, în informatică , o abordare pentru rezolvarea problemelor de calcul.

Descriere

Termenul este mai strict legat de un algoritm . Împarte recursiv o problemă în două sau mai multe subprobleme de dimensiuni egale până când acestea din urmă devin simple de rezolvat; apoi soluțiile sunt combinate pentru a obține soluția problemei date.

Această abordare permite abordarea chiar și a problemelor foarte dificile într-un mod simplu (nu complex, unde complexitatea este ireductibilă sau neliniară); în plus, natura divizării permite paralelizarea calculului, sporind eficiența acestuia pe sisteme distribuite sau multiprocesor. Acest tip de abordare se numește de obicei de sus în jos .

Un program dezvoltat conform acestei tehnici este practic împărțit în trei părți:

Împărțiți : în această parte procedăm la împărțirea problemelor în probleme de dimensiune mai mică;
Impera : în a doua parte problemele sunt rezolvate recursiv. Când subproblemele ajung să aibă o dimensiune suficient de mică, ele sunt rezolvate direct prin carcasa de bază;
Combinați : ultima fază a paradigmei implică recombinarea rezultatului obținut din apelurile recursive anterioare pentru a obține rezultatul final.

În informatică, acest principiu este aplicat pe scară largă pentru rezolvarea problemelor multiple. Cele mai cunoscute aplicații sunt doi dintre cei mai utilizați algoritmi de sortare, sortarea rapidă și sortarea de îmbinare , precum și algoritmul rapid pentru calcularea transformatei Fourier rapide (FFT).

De asemenea, putem vorbi despre divizare și cucerire aplicate în domeniul analizei și proiectării software- ului .