JOURNAL OF STRUCTURAL ENGINEERING http://ascelibrary.org/journal/jsendh Science Citation Index Science Citation Index Expanded Current Contents – Engineering, Computing & Technology JOURNAL IMPACT FACTOR DETAILS 2015/2016 Impact Factor : 1.7 2013 Impact Factor : 1.488 2012 Impact Factor : 1.206 2011 Impact Factor : 0.955 2010 Impact Factor : 0.834 2009 Impact Factor : 0.928 2008 Impact>>>
Kategori Arşivleri: Lisansüstü Araştırmalar
Lisansüstü Araştırmalar
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>>>
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>>>
Karar Verilebilirlik (Decidability) nedir? Bir dil Turing makinesi tarafından kabul ediliyorsa rekürsif/özyineli veya karar verilebilir (decidable) olarak adlandırılır. Bütün karar verilebilir diller Turing Acceptable’dır. Diller: -Karar Verilebilir (Decidable) -Turing Kabul Eder (Turing Acceptable) -Turing Kabul Etmez (Non-Turing Acceptable) olarak sınıflandırılabilir. Karar verilebilir bir dilde Turing makinesi ya kabul ya da ret sonucunu döndürür: Bir dil>>>