Hesaplama Teorisi

Hesaplama Teorisi

Düzenli bir ifadenin NFA ve DFA’sını çizen çevrimiçi bir web sayfası

Düzenli bir ifadenin NFA ve DFA’sını çizen çevrimiçi bir web sayfası: http://hackingoff.com/compilers/regular-expression-to-nfa-dfa Thompson-McNaughton-Yamada temelli NFA ve bu NFA’nın DFA’sını çizerek bizlere sunuyor. Örneğin a*(b|a)* ifadesinin NFA’sı: Aynı ifadenin DFA’sı: HackingOff sitesinde başka faydalı içerikler de bulunuyor. İncelemekte fayda var.

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)…

İ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…

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…

Özyineleme (Recursion) teoremi nedir?

Özyineleme (Recursion) teoremi nedir? T, t:Ʃ^*×Ʃ^*→Ʃ^* fonksiyonunu hesaplayan bir Turing makinesi olsun. Ve bir r:Ʃ^*→Ʃ^* fonksiyonunu hesaplayan, her bir w için r(w)=t(,w) olan bir R Turing makinesi olsun. Kendi tanımını elde edip ardından bununla hesaplama yapabilen bir Turing makinesi yapmak…

Hesaplanabilir Fonksiyon (Computable Function) nedir?

Hesaplanabilir Fonksiyon (Computable Function) nedir? Bir f:Ʃ^*→Ʃ^* fonksiyonu, her bir w girdisinde, herhangi bir M Turing makinesi teybinde yalnızca f(w) ile sonlanırsa (halt) hesaplanabilir bir fonksiyondur. Basitçe bir fonksiyonun hesaplanabilir olması o fonksiyonun bir sonucunun çıkması anlamına gelir. Örneğin Church-Turing…

Algoritma nedir?

Algoritma nedir? Bir Turing makinesinde uygulanabilir her şey algoritmadır. Algoritma, bir problemi çözmek veya bir amaca ulaşmak için tasarlanan yoldur. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu…