Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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. 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. Optimizasyon literatüründe bu ilişki 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 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 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
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 olarak bilinir.
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:
fib(5)fib(4) + fib(3)(fib(3) + fib(2)) + (fib(2) + fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((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
- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3 bas.). MIT Press. s. 359. ISBN . 10 Şubat 2023 tarihinde kaynağından . Erişim tarihi: 23 Ocak 2018.
- ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, . pp. 344.
- ^ Sniedovich, M. (2006). (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.
 | Bilgisayar ile ilgili bu madde seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz. |
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bilgisayar bilimi matematik ekonomi ve biyoinformatikte dinamik programlama ya da dinamik optimizasyon karmasik bir problemi tekrarlanan alt problemlere bolerek her bir alt problemi yalniz bir kere cozup daha sonra bu cozumu kaydederek karmasik problemin cozumunde kullanma yontemidir Bir alt problem cozuldukten sonra tekrar cozulmesi gerektiginde daha once kaydedilen cozum kullanilarak zaman kazanilir ancak alt problemlerin kaydedilecegi daha fazla alana gereksinim duyulur Yani dinamik programlama algoritmalari alandan odun verilerek zamandan kazanilmasini saglar Dinamik programlama algoritmalari optimizasyon problemlerinin cozumunde yaygin olarak kullanilir Genel bakisDinamik programlama hem bir matematiksel optimizasyon hem de bir bilgisayar muhendisligi yontemidir Her iki baglamda da karmasik problemlerin ozyinelemeli alt problemlere bolunmesini ifade eder Eger alt problemler ozyinelemeli olarak daha genis problemlerle ic ice gecmisse daha genis problem ile alt problemlerin degerleri arasinda bir iliski vardir Optimizasyon literaturunde bu iliski olarak adlandirilir Matematiksel optimizasyon Matematiksel optimizasyonda dinamik programlama bir kararin daha kucuk alt kararlar dizisine bolunerek basitlestirilmesidir Bunu yapmak icin bir deger fonksiyonlari dizisi V1 V2 Vn tanimlanir Her Vi fonksiyonu sistemin 1 den n ye kadarki her i anindaki baglidir Vn y fonksiyonu sistemin son n aninda y durumunda aldigi degerdir Daha erken Vi degerleri n den geriye dogru i n 1 n 2 2 1 ozyinelemeli kullanilarak hesaplanir i nin 1 den buyuk degerleri icin Vi 1 in herhangi bir y durumundaki degeri i 1 de alinacak kararlarin kazancini maksimize ederek bulunur Vi degeri zaten hesaplanmis oldugu icin bu islemle Vi 1 ye ulasilabilinir Son adimda bulunan V1 degeri sistemin ilk aninda en iyi kararin alinmasi durumundaki kazanctir Daha sonra zaten yapilmis olan hesaplamalar geri sarilarak her adimda alinacak en iyi kararlarin degerleri de bulunur OrneklerEn kisa yol problemi Bir cizgedeki bir noktadan baska bir noktaya giden en kisa yolu bulma problemi dinamik programlama ile cozulebilir 1956 yilinda bulunan bu cozum mucidinin adiyla olarak bilinir Dijkstra algoritmasi dinamik programlama yaklasimina gore bir P noktasindan Q noktasina en kisa yolu bulmak icin P den Q ya en kisa yolun uzerinde bulunan her nokta icin en kisa yolu bularak ilerler Yani P den Q ya en kisa yol ana problemi icin Q dan daha yakindaki noktalardan P ye en yakin yollarin bulunmalari alt problemlerdir Fibonacci dizisi Fibonacci dizisinin n inci sayisinin bulunmasi probleminin dogrudan tanimini kullanmak yerine dinamik programlama kullanmak daha hizli sonuc verir Dogrudan tanima dayali program fonksiyon fib n eger n lt 1 dondur n dondur fib n 1 fib n 2 Bu program ile 5 Fibonacci sayisinin bulunmasi asagidaki ozyinelemeleri icerir fib 5 fib 4 fib 3 fib 3 fib 2 fib 2 fib 1 fib 2 fib 1 fib 1 fib 0 fib 1 fib 0 fib 1 fib 1 fib 0 fib 1 fib 1 fib 0 fib 1 fib 0 fib 1 Burada ayni deger defalarca sifirdan hesaplanmaktadir Ornegin fib 2 fonksiyonu 3 defa tekrar hesaplanmistir Bu durum hesaplama suresinin hesaplanan sayiyla ustel iliskili bir sekilde buyumesine yani buyuk sayilar icin bu hesaplamanin cok uzun surmesine sebep olur Dinamik programlama kullanilarak tekrar hesaplanan alt problemler hatirlanir ve buyuk bir performans kazanci saglanir Bir esleme fonksiyonu ile hesaplanan her alt problemi hafizaya kaydeden asagidaki program yalnizca O n karmasikliga sahiptir Yani cok daha buyuk sayilar kisa zamanda hesaplanabilir degisken m esleme 0 0 1 1 fonksiyon fib n eger n esleme m de degilse m n fib n 1 fib n 2 dondur m n Kaynakca Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein 2009 Introduction to Algorithms 3 bas MIT Press s 359 ISBN 9780262033848 10 Subat 2023 tarihinde kaynagindan Erisim tarihi 23 Ocak 2018 Cormen T H Leiserson C E Rivest R L Stein C 2001 Introduction to Algorithms 2nd ed MIT Press amp McGraw Hill 0 262 03293 7 pp 344 Sniedovich M 2006 PDF Journal of Control and Cybernetics 35 3 ss 599 620 15 Subat 2020 tarihinde kaynagindan PDF arsivlendi Erisim tarihi 6 Mart 2020 Bilgisayar ile ilgili bu madde taslak seviyesindedir Madde icerigini genisleterek Vikipedi ye katki saglayabilirsiniz