Calculabilité et décidabilité⚓︎
Intentions⚓︎
Introduction
Un ordinateur peut-il tout calculer ? Existe-t-il toujours un algorithme pour résoudre un problème? Le pouvoir de l’algorithmique est-il infini ?
La réponse est bien évidemment non, mais la notion de calculabilité permet de mieux définir les possibilités et limites de l’algorithmique.
Une autre notion, fondamentalement liée à ces questions est la notion de décidabilité qui sépare les problèmes dits « de décision » en deux classes : ceux auxquels on peut apporter une réponse et les autres.
Déroulé
On propose le déroulé suivant :
- un point de cours pour comprendre qu'un programme est aussi une donnée ;
- un notebook pour illustrer cette notion ;
- un point de cours interactif pour présenter les notions de calculabilité et de décidabilité.
Cours⚓︎
Cours (complet)
Exercices (un programme est une donnée)
- Accès via Capytale : dans la zone
Titrede la bibliothèque de Capytale, taper la phrase ci-dessous :
NSI Terminale Partie 1 Chapitre 5 Programme vs donnée
- Accès sans Capytale : télécharger le notebook dans la rubrique Ressources ci-dessous