Karar Problemi (Decision Problem)

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.

« Masfuf (Matris , Matrix) | Gellish (Kontrollü Doğal Dil) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Karar Problemi (Decision Problem)' isimli yazı 28 Jun 2009 tarihinde, saat: 04:52 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 480 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, algoritma analizi (teory of algorithms), bilgisayar felsefesi kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar