Hesaplama Teorisi ile ilgili temel sorular ve cevapları:
Not: Kendime not niteliğinde olduğundan eksikler ve yanlışlar olabilir. Görürseniz uyarınız böylece ben de yanlışımı düzeltmiş olurum. Farklı fikirler, ifadeler ve örnekler ile yorum yazarak cevapları zenginleştirebilirsiniz.
1-Hesaplanabilirlik (Computability) ve Karmaşıklık (Complexity) kavramlarını tanımlayınız?
2-A dili düzenli (regular) ise B dili düzenli ise AUB’nin düzenli olduğunu ispatlayınız?
3-Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız?
4-C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?
5-C={0n1n|n>= 0} dilinin içerikten bağımsız gramerini (context-free grammar) yazınız?
6-Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?
7- Church-Turing tezi nedir? Açıklayınız?
8-∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinasını tanımlayınız?
9-Bir Turing makinasının biçimsel (formal) tanımını yapınız?
10-Halting problemi nedir?
11- Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz?
12-Karar Verilebilirlik (Decidability) nedir?
13-Algoritma nedir?
14-Hesaplanabilir Fonksiyon (Computable Function) nedir?
15-İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?
16-Özyineleme (Recursion) teoremi nedir?
17-3-SAT problemini Clique problemine indirgeyiniz?
18-NP, NP-Complete, NP-Hard nedir?
19-İnatçılık (intractability) nedir?
Yazılarınızdan faydalanıyorum, teşekkür ederim.
Faydalı olabildiysem ne mutlu bana. Ben teşekkür ederim.