CS-251 / 4 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

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

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

Semaine de référence

 LuMaMeJeVe
8-9     
9-10     
10-11     
11-12     
12-13     
13-14     
14-15     
15-16     
16-17     
17-18     
18-19     
19-20     
20-21     
21-22