Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin de içinde bulunduğu pek çok bilim ve mühendislik dalını yakından ilgilendiren hesaplanabilirlik teorisi (computability theory) konusundaki problemlerden birisidir.

Problemi basitçe tanımlama gerekirse bir koşulun (ki biz buna karar ismini vereceğiz) sağlanıp sağlanamadığını evet-hayır şeklinde ikili olarak (duality) sorgulamaktır.

Örneğin x gibi bir sayının ikiye tam bölünüp bölünememesi bir karar problemidir.

Bir karar probleminin sonucunun bulunup bulunamayacağı belirliyse bu tip problemlere kararı mümkün problemler (kararlaştırılabilir problemler, decidable problems) denilmektedir. Örneğin bir sayının ikiye bölümünden kalanın 0 olup olmaması bu tipten bir problemdir. Ancak bazı problemler bu gruba girmez. Örneğin pi sayısının noktadan sonraki bütün hanelerinin bulunamsı gibi. Bu problemin çözülüp çözülemeyeceği belirsizdir. Dolayısıyla problem kararı mümkün problem sınıfından değildir.

Bilgisayar bilimleri mantığı ile konuya yaklaşacak olursak bir problemin algoritmik olarak gösterilmesi veya göterilememesi karar probleminin mümkün olup olmamasını belirlemektedir.

Örneğin durma problemi (halting problem) bu anlamda önemli kararı mümkün olmayan problemlerdendir (undecidable problems).

Bu anlamda kararı mümkün problemleri üç grupta incelemek mümkündür:

kararı mümkün problemler (decidable problems): Şayet algoritma bir özyineli küme (recursive set) ise çözümü mümkün problemdir

Kararı kısmen mümkün problemler (semidecidable, partially decidable, provable, solvable) : Şayet algoritma özyineli sayılabilir küme ise (recursively enumarable set) bu durumda algoritmaya çözümü kısmen mümkün problem ismi verilir

Kararı mümkün olmayan problemler (undecidable problems): kararı kısmen mümkün problemler de dahil olmak üzere şayet bir algoritma özyineli bir küme (recurise set) üretemiyorsa bu gruba dahil edilir.

Yorumlar

  1. pesvin

    merhabalar gelecek hakkında mesela bir yatırımın minimax maximax yada minregret ve laplace hangissinin uzun vadede karlı olduğunu görmek için simulasyon yapabilirmiyiz mesela c plus da nasıl yapabiliriz sizce

  2. Şadi Evren ŞEKER Article Author

    Yapabilirsiniz, tamamının kodlanarak sentetik veri üzerinden çalışmanız en mantıklısı olacaktır.

    Veri sentezlemek için ayrıca bir program yazarak dilediğiniz aralıkta ve özellikte veriyi üretin. Ardından bu algoritmaları kodlayarak aynı sentetik veri üzerinde çalıştırıp zaman ölçümleri yapın. Sonuçları karşılaştırın.

    Kodlanan dilin pek bir önemi yok, algoritmalar dil bağımsızdır.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir