Kategori Arşivleri: Hesaplama Teorisi

Hesaplama Teorisi

İçerikten bağımsız bir gramerin (context-free grammar) üretebileceği ifadeler nelerdir?

Aşağıda içerikten bağımsız bir gramer (context-free grammar) verilmiştir. Başlangıç değişkeni exp ile gösterilmiştir. Bu gramer hangi ifadeleri üretebilir? exp –> INT exp –> exp OP exp exp –> LP exp RP OP –> +|-|*|/ LP –> ( RP –> ) INT –> 0|1|2|3|4|5|6|7|8|9 Cevap: exp->INT’e göre 0-9 arasındaki sayılar tek tek üretilebilir. exp->exp OP exp’e […]

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) 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: […]

Ö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 için yalnızca, makinenin tanımını ekstra bir giriş olarak alan, yukarıda belirtildiği gibi bir T makinesi […]

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?

İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız? İndirgeme bir problemi başka bir probleme dönüştürme işlemidir, böylece ikinci problemin çözümü birinci problemi çözmek için kullanılabilir. İndirgenebilirlik, A ve B gibi iki problemi içerir. Eğer A, B’ye indirgenebilirse, B’yi çözmek için A’yı kullanabilirsiniz. Örneğin bir şehirde yolunuzu bulmak istiyorsunuz. Bir haritanız olmuş olsa yolları daha rahat […]

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 tezine göre bir fonksiyonun hesaplanabilir olması bu fonksiyonun bir makine ile (veya elektronik devre ile […]

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 işlemler kümesidir. İlk algoritmayı Ebu Abdullah Muhammed bin Musa el Harezmi bulmuştur. O yüzden Harezmi […]