Parçala və idarə et (alqoritm)
İnformatikada parçala və idarə et (ing. divide and conquer (D&C)) 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
redaktə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).[1] 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ı (ing. ing. tail recursion) 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.[2] Əgər məsələ bir alt məsələyə parçalanırsa, o zaman azalt və idarə et (ing. ing. decrease and conquer) demək daha doğru olar.[3]
Üstünlükləri
redaktəÇətin məsələləri həll etmək
redaktə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
redaktə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ə
redaktə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ş
redaktə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ə
redaktə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.