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

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

Resources

Moodle Link

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

Reference week

Related courses

Results from graphsearch.epfl.ch.