| 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 | Flipped Classroom | ||||
| Level of Course | Introductory | ||||
| Semester | Bahar | ||||
| 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 |
||||
| Expected Prior Knowledge | Formal Languages and Automata | ||||
| Co-requisites | None | ||||
| 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 Description in Turkish | Biçimsel dil ve otomat tipleri ve özyinelemeli sıralanabilen dillerin gözden geçirilmesi, hesaplama modelleri ve hesaplanabilirlik, karar verilebilirlik ve indirgenebilirlik, hesaplama teorisinde ileri konulara giriş, zaman ve bellek karmaşıklığı, hesaplaması zor problemler, karmaşıklık teorisinde ileri konulara giriş. |
Course Learning Outcomes and CompetencesUpon successful completion of the course, the learner is expected to be able to:1) To be able to apply computability and complexity analysis on a computation problem. 2) To understand and analyze decidability characteristics of a computation problem. 3) To understand complexity classes and to be able to apply reduction on problems. 4) To grasp the basic idea of intractability of a computation problem. |
| Program Learning Outcomes/Course Learning Outcomes | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1) Psikolojideki başlıca kavramlar, teorik perspektifler, deneysel bulgular ve tarihsel eğilimler hakkında kapsamlı bilgi edinilmesi. | ||||
| 2) Psikolojide temel araştırma yöntemlerini, ayrıca araştırma tasarımı, veri analizi ve veri yorumlama anlama ve uygulama becerisi. | ||||
| 3) Davranış ve zihinsel süreçlerle ilgili problemleri çözmek için eleştirel ve yaratıcı düşünme, şüpheci sorgulama ve bilimsel bir yaklaşım kullanma yetkinliği. | ||||
| 4) Psikolojik ilke, beceri ve değerleri kişisel, sosyal ve örgütsel bağlamlarda anlama ve uygulama becerisi. | ||||
| 5) Psikoloji disipliniyle bağlantılı olan kanıtları değerlendirme, belirsizliği tolere etme ve diğer değerleri yansıtma becerisi. | ||||
| 6) Mesleki etik standartların içselleştirilmesi ve yayılması. | ||||
| 7) Psikoloji ve diğer sosyal bilimler alanlarında bilgi edinme amacıyla bilgi teknolojileri, bilgisayar ve diğer teknolojileri kullanma konusunda yetkinlik gösterme. | ||||
| 8) Psikoloji bilimi bilgisini Türkçe ve en azından CEFR B2 düzeyinde İngilizce olmak üzere çeşitli formatlarda etkili bir şekilde iletme becerisi. | ||||
| 9) Sosyokültürel ve uluslararası çeşitliliğin karmaşıklığını tanıma, anlama ve buna saygı gösterme. | ||||
| 10) Yaşam boyu öğrenme, araştırma ve kendini geliştirme ihtiyacını tanıma ve bu doğrultuda beceriler geliştirme. | ||||
| 11) Psikolojik teori ve literatüre dayanarak eleştirel hipotezler oluşturma ve bu hipotezleri test etmek için çalışmalar tasarlama becerisi. | ||||
| 12) Bağımsız olarak bilgi edinme ve kendi öğrenimini planlama becerisi. | ||||
| 13) Yazılı çalışmaların ve sunumların netliği ve düzeni konusunda ileri düzeyde yetkinlik gösterme. |
| N None | S Supportive | H Highly Related |
| Program Outcomes and Competences | Level | Assessed by | |
| 1) | Psikolojideki başlıca kavramlar, teorik perspektifler, deneysel bulgular ve tarihsel eğilimler hakkında kapsamlı bilgi edinilmesi. | N | |
| 2) | Psikolojide temel araştırma yöntemlerini, ayrıca araştırma tasarımı, veri analizi ve veri yorumlama anlama ve uygulama becerisi. | N | |
| 3) | Davranış ve zihinsel süreçlerle ilgili problemleri çözmek için eleştirel ve yaratıcı düşünme, şüpheci sorgulama ve bilimsel bir yaklaşım kullanma yetkinliği. | H | Exam,HW,Participation |
| 4) | Psikolojik ilke, beceri ve değerleri kişisel, sosyal ve örgütsel bağlamlarda anlama ve uygulama becerisi. | N | |
| 5) | Psikoloji disipliniyle bağlantılı olan kanıtları değerlendirme, belirsizliği tolere etme ve diğer değerleri yansıtma becerisi. | N | |
| 6) | Mesleki etik standartların içselleştirilmesi ve yayılması. | N | |
| 7) | Psikoloji ve diğer sosyal bilimler alanlarında bilgi edinme amacıyla bilgi teknolojileri, bilgisayar ve diğer teknolojileri kullanma konusunda yetkinlik gösterme. | N | |
| 8) | Psikoloji bilimi bilgisini Türkçe ve en azından CEFR B2 düzeyinde İngilizce olmak üzere çeşitli formatlarda etkili bir şekilde iletme becerisi. | N | |
| 9) | Sosyokültürel ve uluslararası çeşitliliğin karmaşıklığını tanıma, anlama ve buna saygı gösterme. | S | Participation |
| 10) | Yaşam boyu öğrenme, araştırma ve kendini geliştirme ihtiyacını tanıma ve bu doğrultuda beceriler geliştirme. | S | HW,Participation |
| 11) | Psikolojik teori ve literatüre dayanarak eleştirel hipotezler oluşturma ve bu hipotezleri test etmek için çalışmalar tasarlama becerisi. | N | |
| 12) | Bağımsız olarak bilgi edinme ve kendi öğrenimini planlama becerisi. | S | Exam,HW |
| 13) | Yazılı çalışmaların ve sunumların netliği ve düzeni konusunda ileri düzeyde yetkinlik gösterme. | H | Exam,HW |
| Prepared by and Date | , November 2023 |
| Course Coordinator | ŞENİZ DEMİR |
| Semester | Bahar |
| Name of Instructor |
| Hafta | Konu |
| 1) | Formal Languages and Automata Theory |
| 2) | Recursively Enumerable Languages |
| 3) | Computation Models |
| 4) | Computability |
| 5) | Decidability – Decidable Languages |
| 6) | Decidability – Undecidable Languages |
| 7) | Reducibility |
| 8) | Advanced Topics in Computability Theory |
| 9) | Practical Applications of Complexity Theory |
| 10) | Time Complexity – Complexity Measurement and P Class Problems |
| 11) | Time Complexity – NP Class Problems and NP-Completeness |
| 12) | Space Complexity |
| 13) | Intractability |
| 14) | Advanced Topics in Complexity Theory |
| 15) | Final Exam/Project/Presentation Period |
| 16) | Final Exam/Project/Presentation Period |
| 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 | ||||||