Environnement Numérique de Travail
10 Cours
Calculabilité et Décidabilité
Puisque l'informatique est en évolution perpétuelle, une connaissance élémentaire de la théorie de la calculabilité demeure indispensable à l'étudiant en master informatique pour reconnaitre les limites de l'informatique. La théorie de la calculabilité démontre que certains problèmes informatiques ne peuvent pas être résolus par des programmes quelle que soit la machine. Le but de ce cours est de présenter aux étudiants, en mastère informatique ( premier niveau), les éléments essentiels de la calculabilité et par la suite de la décidabilité et cela de façon rigoureuse, mais abordable par de tels étudiants qui ne sont pas nécessairement férus d'abstractions mathématiques. Ce cours aborde, tout d'abord, les langages formels et les automates puis introduit les notions de calculabilité et de décidabilité à travers les machines de Turing et les fonctions récursives.