Parçala və idarə et (alqoritm)

İnformatikada parçala və idarə et () rekursiyaya əsaslanan alqoritm dizayn paradiqmasıdır. Parçala və idarə et alqoritmi məsələni rekursiv olaraq iki və ya daha çox alt məsələrə bölərək, ən sadə hal üçün həll edir. Alt həllərin sonradan birləşməsi ana məsələnin həllini verir. 

Parçala və idarə et bir çox tip məsələni, o cümlədən sıralama (quicksort, mergesort və s), böyük rəqəmlərin vurulması (misal üçün Karatsuba alqoritmi), ən yaxın cüt nöqtələrin tapılması, sintaktik analiz və kəsilən Furye tansformasiya (FFT) məsələlərini həll etmək üçün effektiv texnikadır. 

 Parçala və idarə et 
Parçala və idarə et bəzən alqoritmlərdə istifadə edilərək məsələni yalnız bir alt məsələyə bölür. Misal üçün [[ikili axtarış]] alqoritmində axtarılan qiymət bu üsulla tapılır (və ya analoji olaraq ədədi hesablamalarda, kökün tapılması üçün istifadə olunan bisection alqoritmi).Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000). Belə məsələləri parçala və idarə et alqoritmindən daha effektiv üsulla həll etmək olar. Belə ki, əgər bu məsələlərdə quyruq rekursiyası () istifadə edilsə, onları sadə dövrə çevirmək olar. Parçala və idarə et alqoritminin geniş mənada tərifi: Əgər alqoritm rekursiya və ya dövr istifadə edirsə, belə alqoritmi "parçala və idarə et" alqoritmi ilə əlaqələndirmək olar. Ona görə də bəzi müəlliflər "parçala və idarə et" adından məsələ iki və daha artıq alt məsələyə bölündükdə istifadə edirlər.Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996. Əgər məsələ bir alt məsələyə parçalanırsa, o zaman azalt və idarə et ({{Dil-en| ing. decrease and conquer}}) demək daha doğru olar.Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

 Üstünlükləri 

 Çətin məsələləri həll etmək 
Parçala və idarə et konseptual olaraq çətin məsələləri həll etmək üçün çox güclü alətdir: tələb olunan yalnız məsələni alt məsələlərə bölməyin yolun tapıb və sadə variant üçün həll etdikdən sonra alt məsələləri birləşdirib, orijinal məsələni həll etməkdir. 

 Effektiv alqoritm 
Parçala və idarə et çox vaxt effektiv alqoritmlər tapmağa kömək edir. O, Karatsubanın sürətli vurma metodu, quicksort və mergesort alqoritmləri, matrisləri vurmaq üçün istifadə olunan Strassen alqoritmi və sürətli Furye çevirilmələrində (FFT) açar rolunu oynayıb. 

 Paralelləşdirmə 
Parçala və idarə et alqoritmləri təbii olaraq çoxlu prosessorlu maşınlarda, xüsusi ilə paylanmış yaddaş sistemlərində təbii olaraq geniş istifadə olunur. 

 Yaddaşa giriş 
Parçala və idarə et alqoritmləri yaddaşda cachedən effektiv istifadə etməyə kömək edir. Səbəbi budur ki, əgər məsələ balaca alt məsələlərə parçalanarsa, bu alt məsələ balaca yaddaş tələb etdiyi üçün cache də saxlanıla bilər və daha böyük yaddaşa girişə ehtiyac qalmaya bilər. 

 Yuvarlaq idarə etmə 
Yuvarlaq cəbri hesablamalarda və ya ədədlərin yuvarlaqlaşdırılmasında, parçala və idarə et alqoritmi iterasiya ilə olunan hesablamalardan daha dəqiq nəticələr verir. 

 İstinadlar 

Kateqoriya:Alqoritmlər