CENG 512
İleri Hesaplama Kuramı
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
Konu |
Giriş ve Genel Bakış |
Matematik Tekrarı |
Sonlu Otomata ve Düzenli Diller |
Bağlamdan Bağımsız Diller ve Pushdown Otomata |
Turing Makineleri ve Church-Turing Tezi |
Karar Verilebilirlik |
Gözden Geçirme |
İndirgenebilirlik |
Zaman Karmaşıklığı, P ve NP |
NP-tamlık |
Gözden Geçirme |
Yer karmaşıklığı |
Rastgeleleştirme |
Paralel karmaşıklık |
Notlandırma
Vize: 30%
Ödev: 30%
Final: 40%
- CENG 501
- CENG 502
- CENG 503
- CENG 504
- CENG 505
- CENG 506
- CENG 507
- CENG 508
- CENG 509
- CENG 511
- CENG 513
- CENG 514
- CENG 515
- CENG 516
- CENG 517
- CENG 518
- CENG 521
- CENG 522
- CENG 523
- CENG 524
- CENG 525
- CENG 531
- CENG 532
- CENG 533
- CENG 534
- CENG 541
- CENG 542
- CENG 543
- CENG 544
- CENG 551
- CENG 552
- CENG 555
- CENG 556
- CENG 557
- CENG 561
- CENG 562
- CENG 563
- CENG 564
- CENG 565
- CENG 566
- CENG 600
- CENG 608
- CENG 611
- CENG 612
- CENG 613
- CENG 631
- CENG 632
- CENG 641
- CENG 642
- CENG 643
- CENG 651
- CENG 661
- CENG 662
- CENG 663
- CENG 690