# Fiches de cours

## Theory of computation

#### Enseignant(s) :

Svensson Ola Nils Anders

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

### Dans les plans d'études

• Semestre
Printemps
• Forme de l'examen
Pendant le semestre
• Crédits
4
• Matière examinée
Theory of computation
• Cours
2 Heure(s) hebdo x 14 semaines
• Exercices
2 Heure(s) hebdo x 14 semaines
• Passerelle HES - IN, 2018-2019, Semestre printemps
• Semestre
Printemps
• Forme de l'examen
Pendant le semestre
• Crédits
4
• 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
Pendant le semestre
• Crédits
4
• 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
Pendant le semestre
• Crédits
4
• 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-12CO3
12-13
13-14
14-15CM1221
CM5

15-16
16-17
17-18
18-19
19-20
20-21
21-22

Cours
Exercice, TP
Projet, autre

### légende

• Semestre d'automne
• Session d'hiver
• Semestre de printemps
• Session d'été
• Cours en français
• Cours en anglais
• Cours en allemand