- français
- English
Fiches de cours
Theory of computation
CS-251
Enseignant(s) :
Svensson Ola Nils AndersLangue:
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
- SemestrePrintemps
- Forme de l'examenPendant 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
- Passerelle HES - IN, 2018-2019, Semestre printemps
- SemestrePrintemps
- Forme de l'examenPendant 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
- SemestrePrintemps
- Forme de l'examenPendant 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
- SemestrePrintemps
- Forme de l'examenPendant 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
Semaine de référence
Lu | Ma | Me | Je | Ve | |
---|---|---|---|---|---|
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | CO3 | ||||
12-13 | |||||
13-14 | |||||
14-15 | CM1221 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