Ağustos 15, 2022
Bir bilgisayar programı yazmak söz konusu olduğunda, öncelikle sorunun ne olduğu ve nasıl çözülebileceği hakkında dikkatlice düşünmek gerekir. Bunun için problemi adım adım çözebilen ve her zaman doğru sonucu alan bir algoritma geliştirmek gerekir.
Algoritmalar farklı kategorilere ayrılabilir. Bunlar yaklaşımlarında ve sıklıkla verimliliklerinde farklılık gösterir. Her algoritmanın her problem için uygun olmadığını belirtmek önemlidir. Birçok algoritma, algoritma programlama ilkesine karşılık gelir. Bu yazıda bu terimin ne anlama geldiğini tanıtacağız.
algoritma programlama prensibini uygulayabilmek için onunla çözmek istediğiniz problemin iki temel şartı yerine getirmesi gerekmektedir. Bunlardan ilki, problemin birkaç alt probleme bölünebilmesi ve çözümlerinin kombinasyonunun genel problemin çözümü ile sonuçlanmasıdır. Bu, algoritma programlamanın özyinelemeli bir yaklaşım izlediğini gösterir. Asıl sorunu paylaşıyor. Aynı algoritma daha sonra bu alt problemlere uygulanır. Bu daha sonra yeni bir bölünmeye yol açabilir. Bu süreç birkaç düzeyde devam edebilir – daha fazla bölme gerekmeyene ve ilgili alt problemin net bir çözümü olana kadar.
İkinci koşul ise bu alt problemlerin birbiriyle örtüşmesidir. Bu, tekrar ayrıştırıldığında bir sonraki seviyedeki alt problemlerin aynı olabileceği anlamına gelir. Aynı alt problemler ortaya çıkmazsa, algoritma programlamayı uygulayan bir algoritma da uygulanabilir. Ancak bu durumda diğer yaklaşımlara göre dezavantajları vardır. Üst üste binen alt problemleri olmayan problemler için, genellikle “böl ve yönet” veya “böl ve yönet” ilkesine karşılık gelen bir algoritma kullanmak mantıklıdır.
algoritma programlamanın temel fikri, tüm alt problemlerin sonuçlarını mevcut olduğu anda kaydetmektir. Aynı sorun başka bir yerde ortaya çıkarsa, çözümünü yeniden hesaplamaktan ziyade bellekten almak genellikle çok daha verimlidir.
Şimdi bu biraz soyut açıklamaları biraz daha açık hale getirmek istiyoruz. Bunu yapmak için, Fibonacci dizisi örneğini kullanarak algoritma programlamayı açıklıyoruz. Bu, 1 ve 2 konumları için 1 değerini belirtir. Diğer tüm konumların değeri, önceki iki değerin toplamıdır. Yani bölümün başlangıcı şöyle görünüyor:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
Daha sonra, belirli bir konumdaki değeri hesaplamak istiyorsak, önceki konumdaki değeri ve iki yer önceki konumdaki değeri toplamamız gerekir. Tek istisna, her durumda 1 değerinin sabitlendiği konum 1 ve 2’dir. n konumundaki değeri hesaplamak istiyorsak ve f()’yi bir Fibonacci işlevi olarak belirtirsek, aşağıdaki tüm n > 2 için geçerlidir:
f(n) = f(n – 1) + f(n – 2)
n <= 2 için ise f(n) = 1 geçerlidir.
Bu şekilde, orijinal problemi iki alt probleme böldük ve bundan sonra genel çözümü elde edebiliriz. Böylece problemimiz algoritma programlamanın uygulanması için ilk koşulu sağlıyor.
Şimdi bu algoritmanın nasıl ilerlediğini görelim. n’nin iki alt problemin hiçbiri doğrudan sonuç vermeyecek kadar büyük olduğunu varsayarsak, yukarıda verilen fonksiyonu tekrar uygulamamız gerekir. Kendimizi f(n-1) ile sınırlandırıyoruz:
f(n-1) = f(n-2) + f(n-3)
Bunu yukarıda verilen f(n) formülüne eklersek, şöyle görünür:
f(n) = f(n – 2) + f(n – 3) + f(n – 2)
Burada f(n-2) ifadesinin iki kez geçtiğini görüyoruz. Bu, bazı alt problemlerin aynı olduğu anlamına gelir. Böylece örtüşen alt problemler ortaya çıkmış, böylece ikinci koşul da sağlanmıştır.
Basit bir özyinelemeli algoritma kullanırken, yinelenen alt problemleri iki kez hesaplamamız gerekir. Ek olarak, daha birçok kopya var. Özellikle büyük sayılarda bu, algoritmanın çok verimsiz çalıştığı ve çok fazla hesaplama süresi gerektirdiği anlamına gelir. Algoritma programlama yaklaşımı, hesapladığımız tüm kısmi sonuçları ayrı ayrı saklamaktır. Örneğimizde bu, f(n – 2) değerini hesapladıktan sonra kaydettiğimiz anlamına gelir. Her bir alt problemi belirlerken, önce sonucu önceden hesaplayıp hesaplamadığımızı kontrol ederiz. Eğer durum buysa, basitçe devralabiliriz. Sonra ikinci kez f(n – 2)’yi çağırdığımızda yeni bir hesaplamaya gerek kalmıyor. Bu, gereken bilgi işlem gücünü önemli ölçüde azaltır.
Algoritma programlama, başlangıçta bilgisayar biliminden ziyade matematikle ilişkilendirilen bir terimdir. Amerikalı matematikçi Richard Bellman, onu 1940’larda, bilgisayar biliminin yeni yeni ortaya çıkmaya başladığı zamanlarda tasarladı. Ayrıca Bellman’ın sözde optimallik ilkesini geliştirdi. Bu, bir problem için optimal çözümün, alt problemlerinin optimal çözümlerinden kaynaklandığını belirtir. Bu optimallik ilkesi, Algoritma programlama için önemli bir temeldir.
Algoritma programlama genellikle bir optimizasyon problemini çözmek için kullanılır. Bu, birkaç farklı çözümden ihtiyaçlarımıza en uygun olanı seçtiğimiz anlamına gelir.
Böyle bir optimizasyon probleminin bir örneği, sözde sırt çantası problemidir. Bu, belirli bir taşıma kapasitesine sahip bir sırt çantamız olması gerçeğinden oluşur. Ayrıca çeşitli eşyalar da mevcuttur. Bunların her birinin ağırlığı farklıdır. Ama aynı zamanda farklı bir değeri var. Ağırlık ve değer arasındaki ilişki de farklılıklar göstermektedir. Tüm öğelerin toplam ağırlığı, sırt çantasının taşıma kapasitesini aşıyor. Artık sırt çantasını taşıma kapasitesini aşmadan içindeki maksimum değeri taşıyabileceğimiz şekilde paketlemek istiyoruz.
Bu sorunu yine özyinelemeli bir algoritma ile çözebiliriz. Bunu yapmak için, mevcut öğeleri sırayla listeleriz – her biri kendi ağırlığı ve değeri ile. Daha sonra listeyi yukarıdan aşağıya doğru inceliyoruz. Her durumda, söz konusu öğeyi paketleyip paketlemeyeceğimize karar veririz. Ancak, bu kararı vermek için, optimal bir sonuç için mantıklı olduğunu doğrulamamız gerekiyor.
Buna karar vermek için problemi tekrar iki alt probleme ayırıyoruz. Bir olasılık, öğeyi yanımızda götürmemizdir. Bu durumda sırt çantasındaki boş alan ağırlığı kadar azalır ve değeri değeri kadar artar. İkinci alternatif ise onu yanımızda götürmememiz. Bu durumda, kullanılabilir alan ve içerdiği değer değişmeden kalır. Şimdi her iki alternatif için de en uygun çözümü bulmalıyız. Bunu yapmak için listedeki bir sonraki öğeye atlıyoruz ve aynı hesaplamaları yapıyoruz. Bu, aşağıdaki şekilde gösterilene benzer bir karar ağacına yol açar.
Bu yaklaşım bizi her zaman doğru sonuca götürür. Ancak, çok verimsizdir – özellikle çok fazla miktarda ürünle. Genellikle hesaplamaların tekrarlandığı olur. Bu nedenle sırt çantası problemi için Algoritma programlama kullanmak mantıklıdır. Ancak bunu yapmak için, aynı alt problemden gerçekten ne zaman bahsedebileceğimizi düşünmek gerekir. Bu her zaman aynı kapasite aynı seviyede mevcut olduğunda meydana gelir. Bu durumlarda, alt problemin optimal çözümü her zaman aynıdır – üst seviyelerde hangi öğeleri paketlediğimizden bağımsız olarak. Bu nedenle sırt çantası problemi için dinamik programlamayı kullanmak ve tüm kısmi sonuçları ayrı bir listede not etmek mantıklıdır. Daha sonra, herhangi bir hesaplama yapmadan önce, ilgili alt problem için bir çözümün var olup olmadığını kontrol ederiz. Bu, algoritmayı çok daha verimli hale getirir.
Algoritma programlama ile uğraşırken, Algoritma programlama dilleri ile her zaman karışıklık vardır. Ancak, bunların birbiriyle ilgisiz iki terim olduğuna dikkat etmek önemlidir. Algoritma programlama dilleri, diğer programlama dillerinin derleme sırasında zaten yaptıkları birçok görevi yalnızca çalışma zamanı sırasında gerçekleştirmeleri ile karakterize edilir. Algoritma programlama dillerinin iyi bilinen örnekleri Python, JavaScript, PHP ve Perl’dir. Ancak Algoritma programlama algoritmalarını uygulamak için dinamik bir programlama dili kullanmak gerekli değildir. Bu, diğer herhangi bir üst düzey programlama dili ile de mümkündür.
Algoritma programlama, çok çeşitli problemlerin çözümlerini yüksek verimlilikle hesaplamayı mümkün kılar. Bu problem çözme biçiminin her zaman uygulanamayacağı doğrudur. Ancak gerekli koşullar sağlandığında dinamik programlama her zaman basit ve verimli bir çözüme yol açar.
Algoritma Proglamlama