INFO3102 : Fondements de l'informatique

Ce cours propose une introduction aux principaux modèles de calcul et aux langages qu'is reconnaissent, des plus faibles aux plus puissants : automates finis et langages rationnels; automates à pile et langages algébriques; fonctions primitives récursives et mu-récursives; machines de Turing, langages décidables et récursivement énumérables, lambda-calcul. On verra aussi quelques notions de base de complexité (problèmes NP-complets). La principale référence est le livre de Michael Sipser (Introduction to the theory of computation).