Étudier les fondements théoriques de l'informatique afin de comprendre quelles sont les propriétés et les limites des ordinateurs.
Formalisation des notions de problème et de langage. Automates finis, expressions régulières et langages réguliers. Automates à pile et langages hors-contextes. Machines de Turing, langages récursifs et récursivement énumérables. Indécidabilité. Réductibilité. Classes de complexité. Hiérarchies.
Préalable(s): (8INF259 et 8MAT122)
Formule pédagogique : Cours Magistral
| 0711 | Programme court de premier cycle en informatique pour étudiants en séjour d'études |
| 6596 | Baccalauréat en développement de jeux vidéo |
| 6801 | Baccalauréat avec majeure en mathématique |