TechCodeview

Böl ve Fethet algoritmik bir modeldir. Algoritmik yöntemlerde tasarım, büyük bir girdiyle ilgili anlaşmazlığı ele almak, girdiyi küçük parçalara ayırmak, küçük parçaların her birinde soruna karar vermek ve ardından parçalı çözümleri küresel bir çözümde birleştirmektir. Sorunu çözmenin bu mekanizmasına Böl ve Fethet Stratejisi denir.

Böl ve Fethet algoritması aşağıdaki üç adımı kullanan bir anlaşmazlıktan oluşur.

BölmekOrijinal problem bir dizi alt probleme dönüştürülür.Fethetmek:Her alt problemi teker teker, yinelemeli olarak çözün.Birleştir:Sorunun tamamına çözüm bulmak için alt problemlerin çözümlerini bir araya getirin.

Genel olarak takip edebiliriz böl ve fethet üç adımlı bir süreçte yaklaşılmaktadır.

Örnekler: Belirli bilgisayar algoritmaları Böl ve Yönet yaklaşımına dayanmaktadır:

1. Maksimum ve Minimum Sorun
2. Ikili arama
3. Sıralama (birleştirme sıralaması, hızlı sıralama)
4. Hanoi kulesi.

Böl ve Fethet Stratejisinin Temelleri:

Böl ve Fethet Stratejisinin iki temeli vardır:

1. İlişkisel Formül
2. Durdurma Durumu

1. İlişkisel Formül: Verilen teknikten ürettiğimiz formüldür. Formülün oluşturulmasından sonra D&C Stratejisini uyguluyoruz, yani sorunu yinelemeli olarak çözüyoruz ve bozuk alt problemleri çözüyoruz.

2. Durdurma Durumu: Böl ve Fethet Stratejisini kullanarak sorunu çözdüğümüzde, ne kadar süre boyunca böl ve Fethet uygulamamız gerektiğini bilmemiz gerekir. Yani D&C'nin özyineleme adımlarımızı durdurmamız gereken duruma Durma Durumu denir.

Böl ve Fethet Yaklaşımının Uygulamaları:

Aşağıdaki algoritmalar Böl ve Fethet Tekniği konseptine dayanmaktadır:

Ikili arama:İkili arama algoritması, yarım aralıklı arama veya logaritmik arama olarak da adlandırılan bir arama algoritmasıdır. Hedef değeri, sıralanmış bir dizide mevcut olan orta öğeyle karşılaştırarak çalışır. Karşılaştırmayı yaptıktan sonra değer farklıysa, hedefi içeremeyen yarı eninde sonunda elenir ve ardından diğer yarıda aramaya devam edilir. Yine ortadaki unsuru ele alacağız ve onu hedef değerle karşılaştıracağız. Hedef değere ulaşılıncaya kadar süreç tekrarlanmaya devam eder. Aramayı sonlandırdıktan sonra diğer yarısının boş olduğunu görürsek hedefin dizide olmadığı sonucuna varabiliriz.Hızlı sıralama:Partition-exchange sort olarak da bilinen en verimli sıralama algoritmasıdır. Bir diziden bir pivot değeri seçerek ve ardından dizi öğelerinin geri kalanını iki alt diziye bölerek başlar. Bölümleme, her bir öğenin pivot değeriyle karşılaştırılmasıyla yapılır. Öğenin pivottan daha büyük veya daha küçük bir değere sahip olup olmadığını karşılaştırır ve ardından dizileri yinelemeli olarak sıralar.Birleştir Sırala:Bir diziyi karşılaştırma yaparak sıralayan bir sıralama algoritmasıdır. Bir diziyi alt dizilere bölerek başlar ve ardından her birini yinelemeli olarak sıralar. Sıralama tamamlandıktan sonra bunları tekrar birleştirir.En Yakın Nokta Çifti:Bu bir hesaplamalı geometri problemidir. Bu algoritma, bir metrik uzayda n nokta verildiğinde en yakın nokta çiftini bulmayı vurgular, böylece nokta çifti arasındaki mesafe minimum olmalıdır.Strassen'in algoritması:Adını Volker Strassen'den alan bir matris çarpım algoritmasıdır. Büyük matrisler üzerinde çalışırken geleneksel algoritmadan çok daha hızlı olduğu kanıtlanmıştır.Cooley-Tukey Hızlı Fourier Dönüşümü (FFT) algoritması:Hızlı Fourier Dönüşümü algoritması, adını J. W. Cooley ve John Turkey'den almıştır. Böl ve Fethet Yaklaşımını izler ve O(nlogn) karmaşıklığını empoze eder.Hızlı çarpma için Karatsuba algoritması:1960 yılının sonlarında Anatoly Karatsuba tarafından icat edilen ve 1962 yılında yayınlanan, geleneksel zamanın en hızlı çarpma algoritmalarından biridir. N basamaklı iki sayıyı en fazla tek haneye indirgeyerek çarpar.

Böl ve Fethet'in Avantajları

• Böl ve Fethet, bir matematik bulmacası olan Hanoi Kulesi gibi en büyük sorunlardan birini başarıyla çözme eğilimindedir. Hakkında hiçbir temel fikrinizin olmadığı karmaşık sorunları çözmek zordur, ancak böl ve yönet yaklaşımının yardımıyla, ana sorunu iki yarıya bölerek ve daha sonra tekrar tekrar çözerek çabayı azalttığı için çabayı azaltmıştır. Bu algoritma diğer algoritmalara göre çok daha hızlıdır.
• Daha yavaş olan ana belleğe erişmek yerine önbellek içindeki basit alt sorunları çözdüğü için fazla yer kaplamadan önbelleği verimli bir şekilde kullanır.
• Muadili Brute Force tekniğinden daha yetkindir.
• Bu algoritmalar paralelliği engellediğinden herhangi bir değişiklik gerektirmez ve paralel işlemeyi içeren sistemler tarafından gerçekleştirilir.

Böl ve Fethet'in dezavantajları

• Algoritmalarının çoğu özyinelemeyi içerecek şekilde tasarlandığından yüksek bellek yönetimi gerektirir.
• Açık bir yığın alanı aşırı kullanabilir.
• Özyinelemenin CPU'da bulunan yığından daha büyük bir titizlikle gerçekleştirilmesi durumunda sistemin çökmesine bile neden olabilir.