Calculabilité et décidabilité en Terminale
Calculabilité et décidabilité, c'est une notion de nsi du chapitre « Langages et programmation », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Calculabilité et décidabilité : le cours
La calculabilité demande si on peut écrire un programme pour résoudre un problème. La décidabilité demande si on peut écrire un programme qui répond par oui ou non à une question en temps fini.
Exemple
Calculer la somme de deux nombres ? Calculable. Savoir si un nombre est pair ? Décidable. Prédire si un programme s'arrêtera un jour (Problème de l'arrêt) ? Non décidable — aucun algorithme ne peut le garantir.
À retenir
Certains problèmes mathématiques ne peuvent pas être résolus par un algorithme, quelle que soit sa puissance.
S'entraîner sur calculabilité et décidabilité
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction récursive qui calcule la somme des entiers de 1 à n. Puis modifie-la pour afficher combien de fois elle s'appelle elle-même.
Corrige cet exercice avec le tuteur →Exercice 2
Un programme demande l'âge de l'utilisateur et doit afficher « Adulte » ou « Mineur ». Écris le code sans try/except d'abord, puis avec gestion d'erreur.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Langages et programmation (NSI Terminale).