Informatique · Terminale · 1 exercice vérifié
S’entraîner : Programme comme donnée, calculabilité et problème de l'arrêt
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Tout programme est aussi une donnée, que peuvent lire ou produire d'autres programmes (interpréteur, compilateur, système d'exploitation, téléchargement) ; la calculabilité ne dépend pas du langage de programmation utilisé ; le problème de l'arrêt (décider, pour tout programme et toute entrée, si le programme s'arrête) est indécidable : aucun programme ne peut le résoudre dans tous les cas, ce que montre un raisonnement par l'absurde.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Programmes récursifs — Une fonction récursive s'appelle elle-même sur une donnée plus petite ; elle comporte au moins un cas de base, traité sans appel récursif, qui garantit l'arrêt ; analyser un appel par la pile des appels ou l'arbre des appels ; compter les appels effectués ; écrire une version récursive d'un calcul (factorielle, puissance, somme des chiffres).
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (1). Difficulté 4 sur 5. Environ 5 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 4 sur 5 · ≈ 5 minutes
Énoncé
Le programme commence avec n=521 puis répète « n = n − 22 » tant que n > 0. Combien d’itérations exécute-t-il ? Démontrer ce cas particulier ne fournit pas de décideur universel du problème de l’arrêt.
Donnez la valeur numérique demandée, avec au moins six chiffres significatifs si nécessaire.
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.