Bu ders farklı biçimsel hesaplama modellerini ortaya koyarak başlayacaktır. Sonrasında Church-Turing tezi ele alınacaktır. Ayrıca karar verilebilirlik ve indirgenebilirlik konuları işlenecektir. Son olarak, karmaşıklık ve ilgili kavramlar hakkında ayrıntılı bilgi verilecektir.

Dersin Amacı

Farklı biçimsel hesaplama modellerini tanımlayıp öğretmek. Biçimsel hesaplama modellerine ilişkin ifadelerin ispatlarını oluşturma yeteneğini kazandırmak. Karmaşıklık sınıflarını aktarmak suretiyle karşılaşılan yeni problemlere ilişkin ispatların yapılmasında NP-tamlık kavramlarını kullandırmak.

Kaynakça

L. Harry R., P. Christos H.,‘Elements of the Theory of Computation’, 2nd Ed., Upper Saddle River, NJ: Prentice-Hall, 1998 ,C. Daniel I.A.,’Introduction to Computer Theory’, 2nd Ed., John Wiley & Sons, Inc., 1997 ,L. Peter, ‘An Introduction to Formal Languages and Automata’,4th Ed., Jones and Bartlett Publishers, Inc., 2001 ,R. Elaine,’Automata, Computability, and Complexity Theory and Applications’, Upper Saddle River, NJ: Prentice-Hall, 2008 ,S. Arora and B. Barak, ’Complexity Theory: A Modern Approach’, Cambridge University Press, Cambridge, 2009 ,S. Cook, ‘The complexity of theorem-proving procedures’, In Proceedings of the 3rd ACM Symposium on the Theory of Computing, ACM, NY, pp 151–158, 1971. ,L. Fortnow, ‘The status of the P versus NP problem’, Commun. ACM. 52, 9 pp 78-86, 2009. ,M. Garey and D. Johnson, ‘Computers and Intractability. A Guide to the Theory of NP-Completeness’ , W. H. Freeman and Company, NY, 1979 ,A. Razborov and S. Rudich, ‘Natural proofs’, Journal of Computer and System Sciences 55, 1 pp 24–35, 1997 ,M. Sipser, ‘Introduction to the Theory of Computation’, PWS Pub. Co, 2005

Öğrenme Çıktıları

1. Farklı hesaplama modellerini tanıma

2. Verilen dil tanımları için ilgili hesaplama modeli karşılığını ispatlama

3. Farklı karmaşıklık sınıflarını ayırdetme

4. Bilgisayar bilimlerindeki bazı zor problemleri tanıma ve ilgili ispatları yapma

Notlandırma

Vize: 30%

Ödev: 30%

Final: 40%