Exercices : calculabilité et décidabilité

Exercice 0. QCM d’activation

Pour chaque question, une seule réponse est correcte.

Question 1. Le problème de l’arrêt consiste à déterminer :

• A) si un programme s’exécute en temps polynomial
• B) si un programme finira par s’arrêter pour une entrée donnée
• C) combien de temps un programme met à s’exécuter
• D) si un programme contient des erreurs de syntaxe

Correction publiée après la séance.

Question 2. Un problème est dit « décidable » si :

• A) il admet au moins une solution
• B) il existe un algorithme qui répond toujours correctement par oui ou non en temps fini
• C) il peut être résolu uniquement par un humain
• D) il ne peut être résolu que par force brute

Correction publiée après la séance.

Question 3. Le problème de l’arrêt est :

• A) décidable et de complexité polynomiale
• B) décidable mais de complexité exponentielle
• C) indécidable
• D) décidable uniquement pour les programmes récursifs

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 :

• A) impossible à résoudre
• B) dont on peut vérifier une solution en temps polynomial
• C) qui ne peut être résolu qu’en temps exponentiel
• D) qui n’a pas de solution

Correction publiée après la séance.

Question 5. (Complément hors programme.) La question ouverte « P = NP ? » demande si :

• A) tous les problèmes informatiques sont résolubles
• B) tout problème dont on peut vérifier la solution rapidement peut aussi être résolu rapidement
• C) les machines de Turing sont plus puissantes que les ordinateurs actuels
• D) le problème de l’arrêt peut être résolu

Correction publiée après la séance.

Exercice 1 – Un programme est une donnée

La question 3 utilise la fonction suivante :

def double(x):
    return 2 * x

1. Expliquer en quelques phrases pourquoi un programme peut être considéré comme « une donnée comme une autre ».

   Indice

   Un programme est un texte, enregistré dans un fichier comme n’importe quelle donnée : que peut-on faire avec un texte ?

2. Citer deux programmes qui reçoivent un programme comme donnée, et dire ce que chacun en fait.

   Indice

   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 ?

3. É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.

   Indice

   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.

4. É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.

   Indice

   source.split("\n") découpe le texte en lignes ; l’expression "print(" in ligne teste si une ligne contient print(.

5. La fonction nombre_de_print permet-elle de savoir combien de lignes un programme affichera quand on l’exécutera ? Justifier avec un exemple.

   Indice

   Imaginer un print placé dans une boucle, ou dans une condition jamais vraie.

Correction publiée après la séance.

Exercice 2 – Un programme qui ne s’arrête pas toujours

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

1. Que renvoie epargner(20) ? Donner les valeurs successives de total.

   Indice

   total part de 0 et augmente de 5 à chaque tour ; la boucle s’arrête quand total vaut exactement l’objectif.

2. Que se passe-t-il lors de l’appel epargner(12) ? Justifier.

   Indice

   Écrire les valeurs successives de total : 0, 5, 10, 15… L’une d’elles vaut-elle 12 ?

3. Que renvoie epargner(0) ?

   Indice

   La condition de la boucle est-elle vraie dès le départ ?

4. Modifier la condition de la boucle pour que epargner s’arrête pour tout objectif positif ou nul. Que renvoie alors epargner(12) ?

   Indice

   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.

Exercice 3 – La suite de Syracuse

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

1. Écrire à la main les valeurs successives de n lors de l’appel syracuse(7). Que renvoie cet appel ?

   Indice

   7 est impair : la valeur suivante est 3 × 7 + 1 = 22. Continuer jusqu’à 1, en comptant les étapes.

2. É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.

   Indice

   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.

3. Les ordinateurs ont vérifié que syracuse(n) s’arrête pour tous les entiers jusqu’à plus de 10²⁰. Peut-on en conclure que syracuse(n) s’arrête pour tout entier n ? Justifier.

   Indice

   Combien y a-t-il d’entiers ? Combien en a-t-on vérifié ?

Correction publiée après la séance.

Exercice 4 – Le programme meme et le programme contraire

On 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 :

def meme(programme):
    if arret(programme, programme):
        return "terminé"
    else:
        while True:
            pass

1. On suppose que arret(meme, meme) renvoie True. Que fait l’appel meme(meme) ? La prédiction de arret est-elle juste ?

   Indice

   Suivre le code de meme avec programme = meme : quelle branche du if est exécutée ? Comparer avec ce qu’affirme arret(meme, meme).

2. Même question si arret(meme, meme) renvoie False.

   Indice

   Même démarche avec l’autre branche.

3. Le programme meme permet-il de démontrer que la fonction arret n’existe pas ? Justifier.

   Indice

   Une démonstration par l’absurde a besoin d’une contradiction. En obtient-on une dans l’un des deux cas ?

4. Modifier meme pour obtenir un programme qui met arret en défaut dans les deux cas, puis rédiger la démonstration.

   Indice

   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.

Exercice 5 – Décidable ou indécidable ?

Pour chacun des problèmes suivants, indiquer s’il est décidable ou indécidable. Justifier brièvement.

1. Déterminer si un nombre entier donné est premier.
2. Déterminer si un programme Python donné affiche "bonjour" au moins une fois.
3. Déterminer si une liste triée contient un élément donné.
4. Déterminer si deux programmes Python calculent toujours la même chose pour les mêmes entrées.
5. Déterminer si un entier donné est pair.
6. Déterminer si un programme Python donné contient une boucle while.

Correction publiée après la séance.

Exercice 6 – P, NP, NP-complet (complément hors programme)

Classer les problèmes suivants dans la catégorie qui convient (P, NP, NP-complet). Justifier.

1. Trier une liste de \(n\) nombres.
2. Déterminer si un graphe admet un cycle hamiltonien (passant par chaque sommet exactement une fois).
3. Rechercher un élément dans une liste triée.
4. Le problème du sac à dos (version décision).
5. Calculer les distances les plus courtes depuis un sommet dans un graphe pondéré à poids positifs.

Correction publiée après la séance.

Exercice 7 – Vrai ou faux

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.

1. « Le problème de l’arrêt montre que certains programmes ne s’arrêtent jamais. »
2. « Si un problème est dans NP, alors il est difficile à résoudre. »
3. « Tous les problèmes de P sont aussi dans NP. »
4. « NP signifie “non polynomial”. »
5. « Si on prouvait que P = NP, la cryptographie RSA serait menacée. »
6. « Le théorème de Rice dit que toute question sur un programme est indécidable. »

Correction publiée après la séance.

Exercice 8 – Réduction au problème de l’arrêt

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 ? »

1. 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.

   Indice

   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 ?

2. En déduire que le problème « prog(0) renvoie-t-il 42 ? » est indécidable.

   Indice

   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.

Exercice 9 – Vérification vs résolution (classe NP, complément hors programme)

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.

1. Expliquer ce que signifie « la vérification d’une solution est polynomiale » pour le sudoku. Quelle est la complexité de cette vérification ?

   Indice

   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 ?

2. Pourquoi ne suffit-il pas de « vérifier toutes les grilles possibles » pour résoudre un sudoku ? Estimer le nombre de grilles à tester.

   Indice

   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.

3. Le problème du tri d’une liste est dans P. Est-il aussi dans NP ? Justifier.

   Indice

   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.