Informatique théorique — claire, compacte et tournée vers la pratique. L’informatique théorique s’intéresse aux questions fondamentales de la calculabilité et de la structure des langages : quels problèmes sont résolubles par algorithme, quels modèles sont nécessaires et quelles sont les limites du calcul. Cet ouvrage vous guide pas à pas à travers les bases des langages formels, de la calculabilité et de la théorie des automates. Vous découvrirez les principaux modèles — des automates finis aux automates à pile et aux grammaires libres de contexte, jusqu’à la machine de Turing — et vous comprendrez non seulement les constructions formelles, mais aussi les techniques de preuve utilisées pour établir des propriétés de langages et identifier les frontières du calculable. Des concepts complexes comme le lemme de pompage, le théorème de Myhill–Nerode, la diagonalisation ou le théorème de Rice sont expliqués de façon claire et illustrée. De nombreuses figures, exemples et exercices accompagnés de corrigés concrétisent la théorie et garantissent l’assimilation. Les chapitres sont modulaires et pédagogiquement conçus, de sorte que vous puissiez choisir un parcours ciblé ou progresser pas à pas. Les preuves sont présentées de manière complète tout en mettant l’accent sur l’intuition et la portée pratique. Une introduction solide et accessible à l’un des domaines centraux de l’informatique — idéale pour les étudiants, les enseignants et tous ceux qui veulent non seulement comprendre l’informatique théorique, mais aussi l’appliquer.
