Sujet NSI — Terminale — Métropole — Bac 2024

EXERCICE 1 (6 points) Cet exercice porte sur l’exécution d’un programme Python et sur la décidabilité. Dans cet exercice, on dira qu’un appel , où est une fonction Python prenant un f(x) f argument et est une valeur, termine lorsque l’évaluation de renvoie toujours x f(x) une valeur au bout d’un nombre fini d’étapes. A l’opposé, un tel appel ne termine pas s’il est possible qu’il effectue des instructions à l’infini. Partie A : boucle while Commençons par un premier exemple, avec une fonction prenant un entier en argument et utilisant une boucle . while 1 def f1(n): 2 i = n 3 while i != 10: 4 i = i + 1 5 return i 1. Sur votre copie, donner les valeurs successives de la variable lors de i l’exécution de , et indiquer si termine. f1(7) f1(7) 2. Indiquer si l’appel se termine. Si oui, indiquer la valeur renvoyée. f1(-2) 3. Sur votre copie, donner les 5 premières valeurs prises par la variable lors de i l’exécution de , et indiquer si l’appel va terminer ou non. f1(12) f1(12) 4. Préciser pour quels entiers l’appel se termine. n f1(n) Partie B : fonction récursive Prenons maintenant un deuxième exemple, avec une fonction récursive (prenant elle aussi un entier en argument). 1 def f2(n): 2 if n == 0: 3 return 0 4 else: 5 return n + f2(n-2) 5. L’appel termine-t-il ? Si oui, indiquer la valeur renvoyée par ; sinon, f2(4) f2(4) justifier brièvement. 6. L’appel termine-t-il ? Si oui, indiquer la valeur renvoyée par ; sinon, f2(5) f2(5) justifier brièvement. 7. Déterminer l’ensemble des entiers naturels pour lesquels l’appel n f2(n) termine. 8. Écrire une fonction Python , récursive, telle que l’appel ne infini infini(n) termine pour aucun entier . n 24-NSIJ2ME3 Page : 2 / 12 Partie C : le problème de l’arrêt On se demande maintenant s’il est possible d’écrire une fonction qui prend en arret arguments une chaîne de caractères contenant le code d’une fonction et un code_f f argument de , et tel que renvoie si l’appel va x f arret(code_f, x) True f(x) terminer et sinon. False Dans la suite de cet exercice, on suppose disposer d’une telle fonction et on arret implémente la fonction suivante, utilisant cette fonction , ainsi que la fonction arret de la question précédente dont l’appel ne termine jamais quelle infini infini(n) que soit la valeur