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

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

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

Semaine de référence

Cours connexes

Résultats de graphsearch.epfl.ch.