EE546 SWITCHING AND AUTOMATA THEORY II
| Course Code: | 5670546 |
| METU Credit (Theoretical-Laboratory hours/week): | 3 (3.00 - 0.00) |
| ECTS Credit: | 8.0 |
| Department: | Electrical and Electronics Engineering |
| Language of Instruction: | English |
| Level of Study: | Graduate |
| Course Coordinator: | Prof.Dr. KLAUS VERNER SCHMİDT |
| Offered Semester: | Fall Semesters. |
Course Objectives
The objective of this course is to provide an understanding of the theory of automata, computability theory and theory of complexity. The course introduces different models of computation and provides a comparison of these models. In addition, the course elaborates on formal methods and proof techniques.
Course Content
Information lossless machines. Codes. Unique decodability. Introduction to formal languages. Context-free and context-sensitive languages. Turing machines. Computability; decidability; unsolvability.
Course Learning Outcomes
Upon successful completion of this course, a student will
1. Understand regular languages and their modeling tools such as deterministic finite state automata (DFA), nondeterministic finite state automata (NFA) and regular expressions,
2. Be able to apply fundamental proof techniques such as deductive, inductive proofs, and proofs by contradiction,
3. Be familiar with context-free languages and their models such as context-free grammars (CFG) and push-down automata (PDA),
4. Be able to apply the pumping lemma to prove that a given language is not regular/not context-free,
5. Be able to model problems using different types of Turing Machines,
6. Be able to distinguish decidable and undecidable problems,
7. Be familiar with complexity classes such as P and NP..
Program Outcomes Matrix
| Contribution | |||||
| # | Program Outcomes | No | Yes | ||
| 1 | Depth: Our graduates acquire in depth knowledge in one of the various specialization areas of Electrical and Electronics Engineering, they are informed about current scientific research topics and they implement innovative methods. | ✔ | |||
| 2 | Breadth: Our graduates get familiarized in other subspecialty areas related to their specialization in Electrical and Electronics engineering and/or relevant areas in other disciplines. | ✔ | |||
| 3 | Research: Our graduates acquire the skills to conduct and to complete scientific research by accessing contemporary knowledge in their specialty areas. | ✔ | |||
| 4 | Life-long learning: Our graduates develop their life-long learning habits. | ✔ | |||
| 5 | Communication skills: Our graduates concisely communicate their ideas and work related results in written and oral form. | ✔ | |||
| 6 | Ethics: Our graduates internalize rules of research and publication ethics as well as professional ethics. | ✔ | |||