|
| Course Description |
|
| Course Name |
: |
Introduction to Theory of Computation |
|
| Course Code |
: |
CENG-529 |
|
| Course Type |
: |
Optional |
|
| Level of Course |
: |
Second Cycle |
|
| Year of Study |
: |
1 |
|
| Course Semester |
: |
Fall (16 Weeks) |
|
| ECTS |
: |
6 |
|
| Name of Lecturer(s) |
: |
Assoc.Prof.Dr. MUSTAFA GÖK
|
|
| Learning Outcomes of the Course |
: |
Expresses the algorithms using deterministic and non deterministic finite automatas.
Develops a context free language and codes using this language
Computes using Turing Machines.
Expresses the computational complex of an algorithm using mathematics
Performs computer simulation of finite state machines.
|
|
| Mode of Delivery |
: |
Face-to-Face |
|
| Prerequisites and Co-Prerequisites |
: |
None |
|
| Recommended Optional Programme Components |
: |
None |
|
| Aim(s) of Course |
: |
To provide a background for the understanding of general theory of computation. |
|
| Course Contents |
: |
Algebraic theorems, finite automata, context-free languages, Turing Machines, Undecidability,computational complexity |
|
| Language of Instruction |
: |
Turkish |
|
| Work Place |
: |
Department of Computer Engineering Graduate Lecture Room |
|
|
Course Outline /Schedule (Weekly) Planned Learning Activities |
| Week | Subject | Student's Preliminary Work | Learning Activities and Teaching Methods |
|
1 |
Automata computability and complexity |
Review graph theory. |
Lecture |
|
2 |
Mathematical notation and Terminology |
Read lecture notes |
Lecture |
|
3 |
Finite Automata |
Read lecture notes |
Lecture |
|
4 |
Nondeterminism |
Read lecture notes |
Lecture |
|
5 |
Context free languages |
Read lecture notes |
Lecture |
|
6 |
Turing Machines |
Read lecture notes |
Lecture |
|
7 |
Midterm |
Review lecture notes |
Written exam |
|
8 |
Decidability |
Read lecture notes |
Lecture |
|
9 |
Recursion Theorem |
Read lecture notes |
Lecture |
|
10 |
Information Definition |
Read lecture notes |
Lecture |
|
11 |
Time Complexity |
Read lecture notes |
Lecture |
|
12 |
The Class NP |
Read lecture notes |
Lecture |
|
13 |
Space Complexity |
Read lecture notes |
Lecture |
|
14 |
Intracibility |
Read lecture notes |
Lecture |
|
15 |
Probabilistic Algorithms |
Read lecture notes |
Lecture |
|
16/17 |
Final Exam |
Review lecture notes |
Written exam |
|
|
|
Required Course Resources |
| Resource Type | Resource Name |
| Recommended Course Material(s) |
 Theory of Computing, Efim Kinber, Carl Smith
|
| |
| Required Course Material(s) | |
|
|
|
Assessment Methods and Assessment Criteria |
|
Semester/Year Assessments |
Number |
Contribution Percentage |
|
Mid-term Exams (Written, Oral, etc.) |
1 |
50 |
|
Homeworks/Projects/Others |
5 |
50 |
|
Total |
100 |
|
Rate of Semester/Year Assessments to Success |
40 |
| |
|
Final Assessments
|
100 |
|
Rate of Final Assessments to Success
|
60 |
|
Total |
100 |
|
|
| Contribution of the Course to Key Learning Outcomes |
| # | Key Learning Outcome | Contribution* |
|
1 |
Reaches wide and deep knowledge through scientific research in the field of computer engineering, evaluates, implements, and comments. |
5 |
|
2 |
Describes and uses information hidden in limited or missing data in the field of computer engineering by using scientific methods and integrates it with information from various disciplines. |
4 |
|
3 |
Follows new and emerging applications of computer engineering profession, if necessary, examines and learns them |
4 |
|
4 |
Develops methods and applies innovative approaches in order to formulate and solve problems in computer engineering. |
5 |
|
5 |
Proposes new and/or original ideas and methods in the field of computer engineering in developing innovative solutions for designing systems, components or processes. |
4 |
|
6 |
Designs and implements analytical modeling and experimental research and solves the complex situations encountered in this process in the field of Computer Engineering |
5 |
|
7 |
works in multi disciplinary teams and takes a leading role and responsibility. |
4 |
|
8 |
Learns at least one foreign language at the European Language Portfolio B2 level to communicate orally and written |
3 |
|
9 |
Presents his/her research findings systematically and clearly in oral and written forms in national and international meetings. |
3 |
|
10 |
Describes social and environmental implications of engineering practice. |
3 |
|
11 |
Considers social, scientific and ethical values in collection, interpretation and announcement of data. |
3 |
|
12 |
Acquires a comprehensive knowledge about methods and tools of computer engineering and their limitations. |
4 |
| * Contribution levels are between 0 (not) and 5 (maximum). |
|
|
| Student Workload - ECTS |
| Works | Number | Time (Hour) | Total Workload (Hour) |
| Course Related Works |
|
Class Time (Exam weeks are excluded) |
14 |
3 |
42 |
|
Out of Class Study (Preliminary Work, Practice) |
14 |
3 |
42 |
| Assesment Related Works |
|
Homeworks, Projects, Others |
5 |
10 |
50 |
|
Mid-term Exams (Written, Oral, etc.) |
1 |
10 |
10 |
|
Final Exam |
1 |
10 |
10 |
|
Total Workload: | 154 |
| Total Workload / 25 (h): | 6.16 |
| ECTS Credit: | 6 |
|
|
|