INFO3102 : Fondements de l'informatique
Foundations of computer science
- Responsable(s) :
-
- Eric Thierry
- Enseignant(s) :
-
- Pascal Koiran
Niveau
L3 / 1e année
Discipline
Informatique
Public externe (ouverts aux auditeurs de cours)
Informations générales sur le cours : INFO3102
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).
Une bonne aisance avec les raisonnements mathématiques est recommandée, mais il n'y pas vraiment d'autres prérequis. En particulier, durant les premières séances nous reverrons rapidement la théorie des automates finis (déjà abordée par en classes préparatoires par de nombreux étudiants).
Enseignant : Pascal Koiran
- Michael Sipser. Introduction to the theory of computation.