(3.0 cr.)

É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

(06/2024)

Appartenance départementale

Informatique et mathématique

Ce cours n'est dans aucun programme ouvert aux admissions.