Hesaplama Teorisi ile ilgili temel sorular ve cevapları

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? […]

İnatçılık (intractability) nedir?

İnatçılık (intractability) nedir? İlkesel olarak çözülebilen bazı hesaplama problemlerinin uygulamada(gerçek hayatta) kullanılamayacak kadar çok zaman ve bellek gerektirmesi durumunda bu tür problemlere inatçı (intractable) denir. SAT problemi ve diğer NP-complete problemlerin intractable olduğu düşünülmektedir fakat ispatlanmamıştır. Verimli (efficient) bir zamanda çözülebilen problemlere tractable, çözülemeyenlere intractable denmektedir. Verimli (efficient) zamanlar: O(n) O(n log n) O(n^3 log^2 […]

NP, NP-Complete, NP-Hard nedir?

NP, NP-Complete, NP-Hard nedir? Bir problem Evet veya Hayır şeklinde sonuç üretiyorsa buna karar problemi denir. P (Polynomial Time): Polinomsal zamanda çözülebilen karar problemlerinin karmaşıklık sınıfıdır. Yani polinomsal zamanda Evet veya Hayır şeklinde bir çözüm üretilir. NP (Non-deterministic-polynomial Time): Polinomsal zamanda doğrulanabilen karar problemlerinin karmaşıklık sınıfıdır. Burada problemin bir çözümü olup olmadığı ile ilgilenilmiyor. NP-Complete: […]