Pour chaque question, une seule réponse est correcte.
Question 1. Le problème de l’arrêt consiste à déterminer :
Correction publiée après la séance.
Question 2. Un problème est dit « décidable » si :
Correction publiée après la séance.
Question 3. Le problème de l’arrêt est :
Correction publiée après la séance.
Question 4. (Complément hors programme.) Un problème de la classe NP est un problème :
Correction publiée après la séance.
Question 5. (Complément hors programme.) La question ouverte « P = NP ? » demande si :
Correction publiée après la séance.
La question 3 utilise la fonction suivante :
def double(x):
return 2 * x
Expliquer en quelques phrases pourquoi un programme peut être considéré comme « une donnée comme une autre ».
Un programme est un texte, enregistré dans un fichier comme n’importe quelle donnée : que peut-on faire avec un texte ?
Citer deux programmes qui reçoivent un programme comme donnée, et dire ce que chacun en fait.
Penser aux outils utilisés en NSI : que reçoit l’interpréteur quand on lance un fichier .py ? que fait Thonny du code que l’on tape ? que fait le correcteur de Capytale ?
Écrire une fonction appliquer_deux_fois(f, x) qui reçoit une fonction f et une valeur x, et renvoie f(f(x)). Par exemple, appliquer_deux_fois(double, 5) renvoie 20.
Le paramètre f s’utilise comme le nom d’une fonction : f(x) calcule l’image de x, puis on applique f à ce résultat.
Écrire une fonction nombre_de_print(source) qui reçoit le code source d’un programme sous forme de chaîne de caractères et renvoie le nombre de lignes qui contiennent print(. Par exemple, avec source = "x = 3\nprint(x)\nprint(x + 1)\n", l’appel nombre_de_print(source) renvoie 2.
source.split("\n") découpe le texte en lignes ; l’expression "print(" in ligne teste si une ligne contient print(.
La fonction nombre_de_print permet-elle de savoir combien de lignes un programme affichera quand on l’exécutera ? Justifier avec un exemple.
Imaginer un print placé dans une boucle, ou dans une condition jamais vraie.
Correction publiée après la séance.
Une élève met 5 € de côté chaque semaine. La fonction suivante compte le nombre de semaines nécessaires pour atteindre un objectif :
def epargner(objectif):
total = 0
semaines = 0
while total != objectif:
total = total + 5
semaines = semaines + 1
return semaines
Que renvoie epargner(20) ? Donner les valeurs successives de total.
total part de 0 et augmente de 5 à chaque tour ; la boucle s’arrête quand total vaut exactement l’objectif.
Que se passe-t-il lors de l’appel epargner(12) ? Justifier.
Écrire les valeurs successives de total : 0, 5, 10, 15… L’une d’elles vaut-elle 12 ?
Que renvoie epargner(0) ?
La condition de la boucle est-elle vraie dès le départ ?
Modifier la condition de la boucle pour que epargner s’arrête pour tout objectif positif ou nul. Que renvoie alors epargner(12) ?
La boucle doit continuer tant que le total est inférieur à l’objectif, et non tant qu’il en est différent.
Correction publiée après la séance.
On reprend la fonction du cours :
def syracuse(n):
etapes = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
etapes = etapes + 1
return etapes
Écrire à la main les valeurs successives de n lors de l’appel syracuse(7). Que renvoie cet appel ?
7 est impair : la valeur suivante est 3 × 7 + 1 = 22. Continuer jusqu’à 1, en comptant les étapes.
Écrire une fonction hauteur_max(n) qui renvoie la plus grande valeur prise par n au cours du calcul, valeur de départ comprise. Par exemple, hauteur_max(7) renvoie 52.
Reprendre la boucle de syracuse et garder dans une variable maximum la plus grande valeur rencontrée, mise à jour après chaque calcul de n.
Les ordinateurs ont vérifié que syracuse(n) s’arrête pour tous les entiers jusqu’à plus de 1020. Peut-on en conclure que syracuse(n) s’arrête pour tout entier n ? Justifier.
Combien y a-t-il d’entiers ? Combien en a-t-on vérifié ?
Correction publiée après la séance.
meme et le programme contraireOn suppose, comme dans le cours, qu’il existe une fonction arret(programme, donnee) qui renvoie True si l’appel programme(donnee) s’arrête, et False sinon. On écrit le programme meme, qui suit la prédiction de arret au lieu de la contredire :
meme et le programme contraire (suite)def meme(programme):
if arret(programme, programme):
return "terminé"
else:
while True:
pass
On suppose que arret(meme, meme) renvoie True. Que fait l’appel meme(meme) ? La prédiction de arret est-elle juste ?
Suivre le code de meme avec programme = meme : quelle branche du if est exécutée ? Comparer avec ce qu’affirme arret(meme, meme).
Même question si arret(meme, meme) renvoie False.
Même démarche avec l’autre branche.
meme et le programme contraire (suite)Le programme meme permet-il de démontrer que la fonction arret n’existe pas ? Justifier.
Une démonstration par l’absurde a besoin d’une contradiction. En obtient-on une dans l’un des deux cas ?
Modifier meme pour obtenir un programme qui met arret en défaut dans les deux cas, puis rédiger la démonstration.
Le programme doit faire l’inverse de la prédiction : s’arrêter quand arret annonce qu’il ne s’arrête pas, et boucler quand arret annonce qu’il s’arrête.
Correction publiée après la séance.
Pour chacun des problèmes suivants, indiquer s’il est décidable ou indécidable. Justifier brièvement.
Un problème est décidable s’il existe un algorithme qui répond, en un temps fini, pour toute entrée. Les questions sur ce que fait un programme quand on l’exécute (ce qu’il affiche, ce qu’il calcule) sont en général indécidables ; celles qui portent seulement sur son texte, ou sur un nombre, se décident par un examen direct.
"bonjour" au moins une fois.while.Correction publiée après la séance.
Classer les problèmes suivants dans la catégorie qui convient (P, NP, NP-complet). Justifier.
P : on sait résoudre le problème en temps polynomial. NP : on sait vérifier en temps polynomial une solution proposée. NP-complet : les problèmes les plus difficiles de NP, pour lesquels on ne connaît pas d’algorithme polynomial. Penser aux algorithmes du cours : tri, dichotomie, Dijkstra.
Correction publiée après la séance.
Pour chaque affirmation, indiquer si elle est vraie ou fausse et justifier. Les affirmations 2 à 5 portent sur les classes P et NP, complément hors programme.
Relire chaque affirmation mot à mot : un seul mot trop fort, comme « toute » ou « difficile », suffit à la rendre fausse. Revenir aux définitions précises du cours.
Correction publiée après la séance.
On veut montrer que le problème suivant est indécidable : « étant donné un programme prog, est-ce que prog(0) renvoie la valeur 42 ? »
Supposons qu’il existe un programme test42(prog) qui renvoie True si prog(0) renvoie 42, et False sinon. Construire, à partir de test42, un programme capable de résoudre le problème de l’arrêt.
Suivre l’indication placée sous la question 2 : q exécute d’abord p(x), puis renvoie 42. Que répond alors test42(q) selon que p(x) s’arrête ou non ?
En déduire que le problème « prog(0) renvoie-t-il 42 ? » est indécidable.
Si test42 existait, le problème de l’arrêt serait décidable : or l’exercice 4 montre le contraire.
Indication : pour un programme p et une entrée x donnés, construire un nouveau programme q tel que q(0) renvoie 42 si et seulement si p(x) s’arrête.
Correction publiée après la séance.
Le sudoku généralisé, joué sur une grille de taille quelconque, est un problème NP-complet ; la grille 9×9 habituelle en est un cas particulier.
Expliquer ce que signifie « la vérification d’une solution est polynomiale » pour le sudoku. Quelle est la complexité de cette vérification ?
Vérifier une grille remplie, c’est contrôler chaque ligne, chaque colonne et chaque bloc : combien d’opérations pour une grille de n × n cases ?
Pourquoi ne suffit-il pas de « vérifier toutes les grilles possibles » pour résoudre un sudoku ? Estimer le nombre de grilles à tester.
Si k cases sont vides, chacune peut recevoir 9 valeurs : combien de grilles différentes faut-il essayer ? Faire le calcul pour une grille où 50 cases sont vides.
Le problème du tri d’une liste est dans P. Est-il aussi dans NP ? Justifier.
Si l’on sait résoudre un problème en temps polynomial, peut-on vérifier une solution proposée en temps polynomial ?
Correction publiée après la séance.