:::: MENU ::::
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) 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?
3-Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız?
DFA
4-C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?
5-C={0n1n|n>= 0} dilinin içerikten bağımsız gramerini (context-free grammar) yazınız?
6-Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?
7- Church-Turing tezi nedir? Açıklayınız?
8-∑={0,1} alfabesi ile oluşturulmuş C={w|w#w} dilini tanıyan Turing makinasını tanımlayınız?
9-Bir Turing makinasının biçimsel (formal) tanımını yapınız?
10-Halting problemi nedir?
11- Post Correspondence Problemi nedir? Post Correspondence Probleminin karar verilemez (undecidable) olduğunu gösteriniz?
12-Karar Verilebilirlik (Decidability) nedir?
13-Algoritma nedir?
14-Hesaplanabilir Fonksiyon (Computable Function) nedir?
15-İndirgeme (Reduction) nedir? İndirgenebilirlik (Reducibility) nedir? Örneklerle açıklayınız?
16-Özyineleme (Recursion) teoremi nedir?
17-3-SAT problemini Clique problemine indirgeyiniz?
18-NP, NP-Complete, NP-Hard nedir?
19-İnatçılık (intractability) nedir?


İ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 n)
Verimsiz (inefficient) zamanlar: O(2^n) O(n!)


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: Her adımdaki çözümleme zamanı kendinden önceki adımdaki çözümleme zamanlarından daha fazla olduğu için bu problem tiplerinin çokterimli zamanda (polynomial time) çözülmesi mümkün değildir. NP-Complete bir problem Belirsiz(Non-Deterministic) Turing Makinesi tarafından belirli zamanda çözülebilmektedir.

NP-Hard: Polinomsal zamanda bir çözümü olduğunu ispatlayamadığımız karar problemlerinin karmaşıklık sınıfıdır.3SAT ve Halting problemi NP-Hard problemlerdir.

P=NP? sorusunun cevabı aranmaktadır. P=NP ispatlanabilirse çözümü olmayan problemlere de çözümler üretilecektir.

Aşağıdaki her iki durum için karmaşıklık sınıfları görselleştirilmiştir:

P-NP-NP-Complete-NP-Hard


Sayfalar:12345678