Theory of computation
Summary
This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematically precise understanding of their fundamental capabilities and limitations.
Content
- Basic models of computation (finite automata, Turing machine)
- Elements of computability theory (undecidability, reducibility)
- Introduction to time complexity theory (P, NP and theory of NP-completeness)
Keywords
theory of computation, Turing machines, P vs. NP problem, complexity theory, computability theory, finite automata, NP-completeness
Learning Prerequisites
Required courses
CS-101 Advanced information, computation, communication I
CS-250 Algorithms
Learning Outcomes
By the end of the course, the student must be able to:
- Perform a rigorous study of performance of an algorithm or a protocol
- Classify computational difficulty of a decision problem
- Define the notion of NP-completeness
- Analyze various computation models
- Design a reduction between two computational problems
- Characterize different complexity classes
- Explain P vs. NP problem
Transversal skills
- Use a work methodology appropriate to the task.
- Continue to work through difficulties or initial failure to find optimal solutions.
Teaching methods
Ex cathedra with exercises
Assessment methods
Written exam and continuous control
In the programs
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Theory of computation
- Courses: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: mandatory
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Theory of computation
- Courses: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: mandatory
- Semester: Spring
- Exam form: Written (summer session)
- Subject examined: Theory of computation
- Courses: 2 Hour(s) per week x 14 weeks
- Exercises: 2 Hour(s) per week x 14 weeks
- Type: optional