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ə | mənbəni redaktə 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).[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ə | mənbəni redaktə et]
Çətin məsələləri həll etmək[redaktə | mənbəni redaktə et]
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ə | mənbəni redaktə et]
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ə | mənbəni redaktə et]
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ə | mənbəni redaktə et]
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ə | mənbəni redaktə et]
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.