Lisansüstü Araştırmalar

Lisansüstü Araştırmalar

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…

Karar Verilebilirlik (Decidability) nedir?

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

Durma (Halting) problemi nedir?

Durma (Halting) problemi nedir? Bir programın belli bir zaman sonra durup durmayacağı belirsizdir. D(P,G) şeklinde bir durup durmamayı bilen program yazıldığını düşünelim. Burada P programı G girdisi ile çalıştığı zaman durup durmayacağını D(P,G) programımız söyleyecek olsun. D(P,G)’nin bir sonuç döndüreceğini…

Bir Turing makinasının biçimsel (formal) tanımını yapınız?

Bir Turing makinasının biçimsel (formal) tanımını yapınız? Tip-0 gramerleri tarafından üretilen rekürsif numaralandırılabilir dili tanımlayan makinalara Turing makinesi denir. 1936 yılında Alan Turing tarafından tasarlanmıştır. Turing makinası girdiyi sonsuz hücreli bir teyp üzerindeymiş gibi modelleyen matematiksel bir yaklaşımdır. Teypten verileri…