İçeriğe atla

Dinamik programlama

Bilgisayar bilimi, matematik, ekonomi ve biyoinformatikte dinamik programlama (ya da dinamik optimizasyon) karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir.[1] Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar. Dinamik programlama algoritmaları optimizasyon problemlerinin çözümünde yaygın olarak kullanılır.

Genel bakış

Dinamik programlama hem bir matematiksel optimizasyon hem de bir bilgisayar mühendisliği yöntemidir. Her iki bağlamda da karmaşık problemlerin özyinelemeli alt problemlere bölünmesini ifade eder.

Eğer alt problemler özyinelemeli olarak daha geniş problemlerle iç içe geçmişse daha geniş problem ile alt problemlerin değerleri arasında bir ilişki vardır.[2] Optimizasyon literatüründe bu ilişki Bellman denklemi olarak adlandırılır.

Matematiksel optimizasyon

Matematiksel optimizasyonda, dinamik programlama bir kararın daha küçük alt kararlar dizisine bölünerek basitleştirilmesidir. Bunu yapmak için bir değer fonksiyonları dizisi V1, V2, ..., Vn tanımlanır. Her Vi fonksiyonu sistemin 1'den n'ye kadarki her i anındaki durumuna bağlıdır. Vn(y) fonksiyonu, sistemin son n anında, y durumunda aldığı değerdir. Daha erken Vi değerleri, n'den geriye doğru (i = n −1, n − 2, ..., 2, 1) özyinelemeli Bellman denklemi kullanılarak hesaplanır. i'nin 1'den büyük değerleri için, Vi−1'in herhangi bir y durumundaki değeri i − 1'de alınacak kararların kazancını maksimize ederek bulunur. Vi değeri zaten hesaplanmış olduğu için bu işlemle Vi−1'ye ulaşılabilinir. Son adımda bulunan V1 değeri, sistemin ilk anında en iyi kararın alınması durumundaki kazançtır. Daha sonra, zaten yapılmış olan hesaplamalar geri sarılarak, her adımda alınacak en iyi kararların değerleri de bulunur.

Örnekler

En kısa yol problemi

Ana madde: En kısa yol problemi

Bir çizgedeki bir noktadan başka bir noktaya giden en kısa yolu bulma problemi dinamik programlama ile çözülebilir. 1956 yılında bulunan bu çözüm, mucidinin adıyla Dijkstra algoritması olarak bilinir.[3]

Dijkstra algoritması, dinamik programlama yaklaşımına göre, bir P noktasından Q noktasına en kısa yolu bulmak için, P'den Q'ya en kısa yolun üzerinde bulunan her nokta için en kısa yolu bularak ilerler. Yani, P'den Q'ya en kısa yol ana problemi için, Q'dan daha yakındaki noktalardan P'ye en yakın yolların bulunmaları alt problemlerdir.

Fibonacci dizisi

Fibonacci dizisinin n'inci sayısının bulunması probleminin doğrudan tanımını kullanmak yerine, dinamik programlama kullanmak daha hızlı sonuç verir. Doğrudan tanıma dayalı program: 

fonksiyon fib(n)
    eğer n <= 1 döndür n
    döndür fib(n − 1) + fib(n − 2)

Bu program ile 5. Fibonacci sayısının bulunması aşağıdaki özyinelemeleri içerir:

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Burada aynı değer defalarca sıfırdan hesaplanmaktadır. Örneğin, fib(2) fonksiyonu 3 defa tekrar hesaplanmıştır. Bu durum, hesaplama süresinin, hesaplanan sayıyla üstel ilişkili bir şekilde büyümesine, yani büyük sayılar için bu hesaplamanın çok uzun sürmesine sebep olur.

Dinamik programlama kullanılarak, tekrar hesaplanan alt problemler hatırlanır ve büyük bir performans kazancı sağlanır. Bir eşleme fonksiyonu ile, hesaplanan her alt problemi hafızaya kaydeden aşağıdaki program yalnızca O(n) karmaşıklığa sahiptir. Yani çok daha büyük sayılar kısa zamanda hesaplanabilir. 

değişken m := eşleme(0 → 0, 1 → 1)
fonksiyon fib(n)
    eğer n eşleme m'de değilse 
        m[n] := fib(n − 1) + fib(n − 2)
    döndür m[n]

Kaynakça

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3 bas.). MIT Press. s. 359. ISBN 9780262033848. 10 Şubat 2023 tarihinde kaynağından arşivlendi. Erişim tarihi: 23 Ocak 2018. 
  2. ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, 0-262-03293-7 . pp. 344.
  3. ^ Sniedovich, M. (2006). "Dijkstra's algorithm revisited: the dynamic programming connexion" (PDF). Journal of Control and Cybernetics. 35 (3). ss. 599-620. 15 Şubat 2020 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 6 Mart 2020. 

İlgili Araştırma Makaleleri

Fortran, özellikle sayısal hesaplama ve bilimsel hesaplama için uygun olan genel amaçlı, yordamsal, zorunlu programlama dilidir.

Seyyar satıcı problemi yöneylem araştırması ve teorik bilgisayar bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir.

Paralel hesaplama ya da Koşut hesaplama, aynı görevin, sonuçları daha hızlı elde etmek için çoklu işlemcilerde eş zamanlı olarak işletilmesidir. Bu fikir, problemlerin çözümünün ufak görev parçalarına bölünmesi ve bunların eş zamanlı olarak koordine edilmesine dayanır. Paralel hesaplama ile performans artar, büyük sorunlar daha az sürede çözülür ve bilimdeki gelişmeler paralel hesaplamaya gereksinim duyar.

<span class="mw-page-title-main">Genetik algoritma</span>

Genetik algoritmalar, doğada gözlemlenen evrimsel mekanizmalara benzer mekanizmalar kullanarak çalışan eniyileştirme yöntemidir. Çok boyutlu uzayda belirli bir maliyet fonksiyonuna göre en iyileştirme amacıyla iterasyonlar yapan ve her iterasyonda en iyi sonucu üreten kromozomun hayatta kalması prensibine dayanan en iyi çözümü arama yöntemidir.

<span class="mw-page-title-main">Kalkülüs</span>

Başlangıçta sonsuz küçük hesap veya "sonsuz küçüklerin hesabı" olarak adlandırılan kalkülüs, geometrinin şekillerle çalışması ve cebirin aritmetik işlemlerin genellemelerinin incelenmesi gibi, kalkülüs sürekli değişimin matematiksel çalışmasıdır.

Matematikte matematiksel programlama, eniyileme ya da optimizasyon terimi; bir gerçel fonksiyonu minimize ya da maksimize etmek amacı ile gerçek ya da tam sayı değerlerini tanımlı bir aralıkta seçip fonksiyona yerleştirerek sistematik olarak bir problemi incelemek ya da çözmek işlemlerini ifade eder. Örneğin bu problem şöyle olabilir:

Ağ modeli yöneylem araştırmasında belirlenmiş bir sıra problemin düğümler ve dal veya bağlantilardan oluşan bir şebeke halinde tanımlanıp modellemesi türü olup ve tanımlanan sebeke problemlerinin çözümlenmesi için ortaya çıkartılan özel şebeke problemi algoritmalardan oluşur. Bu türlü çalışmalarda önce problemin ögeleri ve amacı tarif edilir. Sonra problemin şekil olarak veya matris olarak dallar ile birbirlerine bağlı düğümler halinde yapılandırılıp tanımlanması gerekir. Örneğin problem bir şehre kurulacak su borusu şebekesinin, bütün şehre en ucuz maliyet ile nasıl kurulacağıdir. Bu problem bir mümkün olan bütün bağlantı parçalarını, maliyetleri ve kapasiteleri gösteren şebeke halinde ifade edilir. Bu problem ve yapılanan model bir minimum maliyet kapasiteli sebeke problemi olduğu için bu çeşit model problemi çözmek için geliştirilmiş olan özel algoritmalardan birini kullanarak çözülebilir.

<span class="mw-page-title-main">Sırt çantası problemi</span>

Sırt çantası problemi bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.

Matematik biliminde, özellikle yöneylem araştırması uygulamalı dalında, doğrusal programlama problemleri bir doğrusal amaç fonksiyonunun doğrusal eşitlik ve/veya eşitsizlik kısıtlamalarını sağlayacak şekilde optimizasyon yapılmasıdır. Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinin ağırlıklı toplamlarından oluşmalıdır.

Kırmızı-siyah ağaç bilgisayar biliminde bir çeşit kendini-dengeleyen ikili arama ağacı veri yapısıdır. Orijinali ilk olarak 1972 yılında yapıyı "simetrik ikili B-ağaçları" olarak adlandıran Rudolf Bayer tarafından bulunmuştur. Bugünkü ismini 1978 yılında Leo J. Guibas ve Robert Sedgewick tarafından yayımlanan bir makaleyle almıştır. Karmaşık ancak çalışma süresi en kötü durumda bile iyi ve pratikte verimlidir: O(log n) (n ağaçtaki eleman sayısını gösterir) zamanda arama, ekleme ve çıkarma işlemleri yapabilir.

<span class="mw-page-title-main">Laplace denklemi</span>

Matematikte Laplace denklemi, özellikleri ilk defa Pierre-Simon Laplace tarafından çalışılmış bir kısmi diferansiyel denklemdir. Laplace denkleminin çözümleri, elektromanyetizma, astronomi ve akışkanlar dinamiği gibi birçok bilim alanında önemlidir çünkü çözümler bilhassa elektrik ve yerçekim potansiyeli ile akışkan potansiyelinin davranışını açıklar. Laplace denkleminin çözümlerinin genel teorisi aynı zamanda potansiyel teorisi olarak da bilinmektedir.

<span class="mw-page-title-main">Sayısal analiz</span>

Sayısal analiz, diğer adıyla nümerik analiz veya sayısal çözümleme, matematiksel analiz problemlerinin yaklaşık çözümlerinde kullanılan algoritmaları inceler. Bu nedenle birçok mühendislik dalı ve doğa bilimlerinde önem arz eden sayısal analiz, bilimsel hesaplama bilimi olarak da kabul edilebilir. Bilgisayarın işlem kapasitesinin artması ile gündelik hayatta ortaya çıkan birçok sistemin matematiksel modellenmesi mümkün olmuş ve sayısal analiz algoritmaları burada ön plana çıkmıştır. 21. yüzyıldan itibaren bilimsel hesaplama yöntemleri mühendislik ve doğa bilimleri ile sınırlı kalmamış ve sosyal bilimler ile işletme gibi alanları da etkilemiştir. Sayısal analizin alt başlıklarına adi diferansiyel denklemlerin yaklaşık çözümleri ve özellikle veri biliminde önem taşıyan sayısal lineer cebir ile optimizasyon örnek gösterilebilir.

Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.

Matematiksel model, bir sistemin matematiksel kavramlar ve dil kullanılarak tanımlanmasıdır. Matematiksel model geliştirme süreci, matematiksel modelleme olarak adlandırılır. Matematiksel modeller, doğa bilimlerinde ve mühendislik disiplinlerinde bunun yanı sıra sosyal bilimlerde kullanılır. Matematiksel modelleri daha çok fizikçiler, mühendisler, istatistikçiler, operasyon araştırma analistleri ve ekonomistler kullanır. Model, bir sistemi açıklamaya, farklı bileşenlerin etkilerini incelemeye ve bir davranış hakkında öngörüde bulunmak için yardımcı olabilir.

Programlama paradigmaları, programlama dillerini özelliklerine göre sınıflandırmanın bir yoludur. Diller birden fazla paradigma içinde sınıflandırılabilir.

<span class="mw-page-title-main">Lagrange çarpanı</span>

Optimizasyon yaparken, Lagrange çarpanı methodu, bir fonksiyonun maksimum ve minimum noktalarını bulmak için kullanılan bir yöntemdir.

<span class="mw-page-title-main">Simpleks algoritması</span>

Simpleks algoritması, doğrusal programlama problemlerinde optimum çözümü pratik olarak bulmak amacıyla George Dantzig tarafından 1947 yılında geliştirilen bir algoritmadır.

Bilgisayar biliminde, Floyd-Warshall algoritması kenar ağırlıkları artı ya da eksi değere sahip çizgelerde en kısa yolları bulma algoritmasıdır. Algoritma uygulandığında her düğüm çifti için en kısa yol uzunluklarını bulur. Özgün algoritma yol detaylarını döndürmese de, küçük değişikliklerle yolların oluşturulması da mümkündür. Çizge kuramında ve diğer matematik uygulamalarında kullanılır.

<span class="mw-page-title-main">En kısa yol problemi</span>

Çizge kuramında, en kısa yol problemi, bir çizgedeki iki düğümü bağlayan ve ağırlıkları toplamı en az olan ayrıtlar dizisini bulma problemidir.

Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Çok sayıda verinin girilmesi ve iyi bir sezgisel fonksiyon verildiğinde, probleme yeterince iyi bir çözüm bulmaya çalışmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. İki boyutlu bir grafikte en düşük noktaları arama esnasında yapmış olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıştır.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.