CS-251 / 6 crédits

Enseignant: Göös Mika Tapani

Langue: Anglais

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

## Dans les plans d'études

• Semestre: Printemps
• Forme de l'examen: Ecrit (session d'été)
• Matière examinée: Theory of computation
• Cours: 2 Heure(s) hebdo x 14 semaines
• Exercices: 2 Heure(s) hebdo x 14 semaines
• Type: obligatoire
• Semestre: Printemps
• Forme de l'examen: Ecrit (session d'été)
• Matière examinée: Theory of computation
• Cours: 2 Heure(s) hebdo x 14 semaines
• Exercices: 2 Heure(s) hebdo x 14 semaines
• Type: optionnel
• Semestre: Printemps
• Forme de l'examen: Ecrit (session d'été)
• Matière examinée: Theory of computation
• Cours: 2 Heure(s) hebdo x 14 semaines
• Exercices: 2 Heure(s) hebdo x 14 semaines
• Type: obligatoire

## Cours connexes

Résultats de graphsearch.epfl.ch.