| School/Faculty/Institute | Faculty of Engineering | ||||
| Course Code | COMP 454 | ||||
| Course Title in English | Theory of Computation | ||||
| Course Title in Turkish | Hesaplama Kuramı | ||||
| Language of Instruction | EN | ||||
| Type of Course | Ters-yüz öğrenme | ||||
| Level of Course | Başlangıç | ||||
| Semester | Spring | ||||
| Contact Hours per Week |
|
||||
| Estimated Student Workload | 118 hours per semester | ||||
| Number of Credits | 6 ECTS | ||||
| Grading Mode | Standard Letter Grade | ||||
| Pre-requisites |
MATH 321 - Automata Theory and Formal Language |
||||
| Co-requisites | None | ||||
| Expected Prior Knowledge | Formal Languages and Automata | ||||
| Registration Restrictions | None | ||||
| Overall Educational Objective | To be able to obtain a scientific prespective on the natüre of computational problems. | ||||
| Course Description | Overview of types of formal languages and automata and recursively enumerable languages, computation models and computability, decidability and reducibility, introduction of advanced topics in theory of computation, space and time complexity, intractability, introduction of advanced topics in theory of complexity. |
Course Learning Outcomes and CompetencesUpon successful completion of the course, the learner is expected to be able to:1) Hesaplamalı problemler üzerinde hesaplanabilirlik ve karmaşıklık analizi uygular 2) Hesaplama problemi karar verilebilirlik özelliklerini anlar ve analiz eder. 3) Karmaşıklık sınıflarını anlar ve problem üzerinde indirgeme uygular. 4) Bir hesaplama probleminin çözülemezliğinin temellerini kavrar |
| Program Learning Outcomes/Course Learning Outcomes | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1) Ekonomi konusunda geniş bir anlayışa sahip olup, diğer sosyal bilimler ve matematikle derin bir etkileşime sahip olmak. | ||||
| 2) Farklı ekonomi alanlarının etkileşimlerini anlama konusunda bilgi ve beceriler sergilemek | ||||
| 3) Mikroekonomik ve makroekonomik teoriyi anlamak | ||||
| 4) Ekonomik kavramları karmaşık sorunları çözmek ve karar verme yeteneğini geliştirmek için uygulamak. | ||||
| 5) Farklı ekonomik sistemleri analiz etmek için nicel teknikler kullanmak. | ||||
| 6) Teorik bilgileri, Türk ve küresel ekonomilere ilişkin sorunları analiz etmek için uygulamak. | ||||
| 7) Ekonomik verileri işlemek ve değerlendirmek için istatistiksel araçlar ve yaygın yazılım programları konusunda yetkinlik göstermek. | ||||
| 8) Ekonomik analizin tüm aşamalarında - veri toplama, yorumlama ve bulguları yayma - bilimsel ve etik değerlere göre davranmak. | ||||
| 9) Bilimsel bilgileri alışverişinde yazılı ve sözlü İngilizceyi etkili bir şekilde kullanmak (en az CEFR B2 seviyesinde). | ||||
| 10) Bireysel ve profesyonel etik davranış sergiler ve sosyal sorumluluk taşımak. | ||||
| 11) Yüksek derecede özerklikle daha ileri çalışmalar için gerekli öğrenme becerilerini sergilemek. |
| N None | S Supportive | H Highly Related |
| Program Outcomes and Competences | Level | Assessed by | |
| 1) | Ekonomi konusunda geniş bir anlayışa sahip olup, diğer sosyal bilimler ve matematikle derin bir etkileşime sahip olmak. | N | |
| 2) | Farklı ekonomi alanlarının etkileşimlerini anlama konusunda bilgi ve beceriler sergilemek | N | |
| 3) | Mikroekonomik ve makroekonomik teoriyi anlamak | N | |
| 4) | Ekonomik kavramları karmaşık sorunları çözmek ve karar verme yeteneğini geliştirmek için uygulamak. | N | |
| 5) | Farklı ekonomik sistemleri analiz etmek için nicel teknikler kullanmak. | N | |
| 6) | Teorik bilgileri, Türk ve küresel ekonomilere ilişkin sorunları analiz etmek için uygulamak. | N | |
| 7) | Ekonomik verileri işlemek ve değerlendirmek için istatistiksel araçlar ve yaygın yazılım programları konusunda yetkinlik göstermek. | N | |
| 8) | Ekonomik analizin tüm aşamalarında - veri toplama, yorumlama ve bulguları yayma - bilimsel ve etik değerlere göre davranmak. | H | |
| 9) | Bilimsel bilgileri alışverişinde yazılı ve sözlü İngilizceyi etkili bir şekilde kullanmak (en az CEFR B2 seviyesinde). | H | |
| 10) | Bireysel ve profesyonel etik davranış sergiler ve sosyal sorumluluk taşımak. | H | |
| 11) | Yüksek derecede özerklikle daha ileri çalışmalar için gerekli öğrenme becerilerini sergilemek. | H |
| Prepared by and Date | ŞENİZ DEMİR , November 2023 |
| Course Coordinator | ŞENİZ DEMİR |
| Semester | Spring |
| Name of Instructor | Doç. Dr. TOLGA OVATMAN |
| Hafta | Konu |
| 1) | Formal diller ve otomata kuramı |
| 2) | Özyinelemeli Sayılabilir Diller |
| 3) | Hesaplama modelleri |
| 4) | Hesaplanabilirlik |
| 5) | Karar verilebilirlik- Karar verilebilen diller |
| 6) | Karar Verilebilirlik – Karar Verilemez Diller |
| 7) | İndirgenebilirlik |
| 8) | Hesaplanabilirlik kuramında ileri konular |
| 9) | Karmaşıklık kuramının pratik uygulamaları |
| 10) | Zaman karmaşıklığı - Karmaşıklık ölçümü ve P Sınıfı problemler |
| 11) | Zaman karmaşıklığı- NĞ Sınıfı problemler ve NP-tamlık |
| 12) | Alan karmaşıklığı |
| 13) | Çözülemezlik |
| 14) | Karmaşıklık kuramında ileri konular |
| 15) | Final Sınavı/Proje/Sunum dönemi |
| 16) | Final Sınavı/Proje/Sunum dönemi |
| Required/Recommended Readings | Sipser M., Introduction to the Theory Of Computation 3rd Edition, Cengage Learning, 2013 Martin J.C., Introduction To Languages And The Theory Of Computation 4th Edition, Mcgraw-Hill, 2011 Attalah M.J., Blanton M., Algorithms And Theory Of Computation Handbook Vol.2:Special Topics And Techniques 2nd Edition, CRC Press, 2010 | ||||||||||||
| Teaching Methods | Lecture only | ||||||||||||
| Homework and Projects | In-class exercises | ||||||||||||
| Laboratory Work | None | ||||||||||||
| Computer Use | None | ||||||||||||
| Other Activities | None | ||||||||||||
| Assessment Methods |
|
||||||||||||
| Course Administration |
ovatman@itu.edu.tr Instructor’s office and phone number, office hours, email address: To be announced Assoc. Prof. Tolga Ovatman - ITU -Office:İTÜ Faculty of Computer and Informatics -Email address: ovatman@itu.edu.tr Rules for attendance: Minimum of 70% attendance required. Missing a quiz: Provided that proper documents of excuse are presented, each missed quiz by the student will be given a grade which is equal to the average of all of the other quizzes. No make-up will be given. Missing a final: Faculty regulations. A reminder of proper classroom behavior, code of student conduct: YÖK Regulations Statement on plagiarism: YÖK Regulations |
||||||||||||
| Activity | No/Weeks | Hours | Calculation | ||||
| No/Weeks per Semester | Preparing for the Activity | Spent in the Activity Itself | Completing the Activity Requirements | ||||
| Ders Saati | 14 | 1.5 | 3 | 1.5 | 84 | ||
| Küçük Sınavlar | 5 | 4 | 1 | 25 | |||
| Final | 1 | 13 | 3 | 16 | |||
| Total Workload | 125 | ||||||
| Total Workload/25 | 5.0 | ||||||
| ECTS | 6 | ||||||