CS-251 / 6 credits

Teacher: Göös Mika Tapani

Language: English

## 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

## 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
• Lecture: 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
• Lecture: 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
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Type: optional

## Related courses

Results from graphsearch.epfl.ch.