2020-2021 bahar yarıyılında Otomata Teorisi ve Biçimsel Diller dersini verirken kullanmam için Selçuk Üniversitesi Teknoloji Fakültesi Bilgisayar Mühendisliği Bölüm Başkanı Prof. Dr. Fatih BAŞÇİFTÇİ hocam tarafından bir kitap hediye edilmiştir. Cinius Yayınları’nın bastığı Dr. Emre Sermutlu’nun yazdığı Otomatlar Biçimsel Diller ve Turing Makineleri başlıklı kitap bu zorlu derste bana çok yardımcı olacaktır. Böyle anlamlı ve>>>
Kategori Arşivleri: Hesaplama Teorisi
Hesaplama Teorisi
Hesaplama Teorisi
İçerikten bağımsız bir gramerin (context-free grammar) üretebileceği ifadeler nelerdir?
27
Eki
Eki
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>>>
22
Eki
Eki
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ı: 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? İ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? 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:>>>
3-SAT problemini Clique problemine indirgeyiniz? 3-SAT problemini polinomsal zamanda Clique problemine indirgeyelim. Aybüke BABADAĞ’ın çözümü için tıklayınız
Ö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 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? 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>>>