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.

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

 Lu Ma Me Je Ve 8-9 9-10 10-11 11-12 12-13 13-14 14-15 15-16 SG1 16-17 17-18 GCC330CE5CE1101CM5CM1100 18-19 19-20 20-21 21-22

Lundi, 15h - 17h: Cours SG1

Lundi, 17h - 19h: Exercice, TP GCC330
CE5
CE1101
CM5
CM1100