Programmation, tests et calculabilité · NSI Terminale (spé maths)

Spécifier, tester et déboguer

Un programme fiable commence par une spécification : que reçoit la fonction (précondition), que renvoie-t-elle (postcondition) ? On l'écrit dans une docstring, texte placé juste après la ligne def, que help(...) affiche et que les autres développeurs lisent.

def maximum(liste):

    """Renvoie le plus grand élément de liste (non vide)."""

    assert len(liste) > 0, "la liste doit être non vide"

    m = liste[0]

    for x in liste:

        if x > m:

            m = x

    return m

L'instruction assert condition, message arrête le programme avec une AssertionError si la condition est fausse. On l'utilise pour deux choses :

vérifier une précondition au début d'une fonction ;
écrire un test : assert maximum([3, 9, 4]) == 9.

Tester ne prouve pas qu'un programme est correct : cela montre seulement l'absence d'erreur sur les cas essayés. Mais un bon jeu de tests détecte la plupart des bogues.

assert maximum([3, 9, 4]) == 9

assert maximum([5]) == 5

assert maximum([-7, -2, -9]) == -2

Trouver et corriger un bogue

On veut calculer la moyenne d'une liste.

def moyenne(liste):

    s = 0

    for i in range(1, len(liste)):

        s = s + liste[i]

    return s / len(liste)

Chercher un jeu de test révélateur. Pour [2, 4, 6], on attend 4. Le programme calcule $(4+6)/3 \approx 3{,}33$ : le test échoue.

Localiser la cause. range(1, len(liste)) commence à l'indice 1 : le premier élément est oublié. C'est une erreur classique de bornes.

Corriger. On parcourt tous les indices : for i in range(len(liste)), ou plus simplement for x in liste.

À toi. Que se passe-t-il pour moyenne([]) ? Propose une protection.

Division par zéro (ZeroDivisionError). On ajoute en début de fonction assert len(liste) > 0, "liste vide".

Entraîne-toi★☆☆

On considère la fonction : a) Écrire trois tests sous forme d'assert : un cas général, un cas à un seul élément et un cas avec des valeurs négatives. b) Écrire une…

On considère la fonction :

def maximum(liste):

    """Renvoie le plus grand élément de liste (non vide)."""

    m = liste[0]

    for x in liste:

        if x > m:

            m = x

    return m

a) Écrire trois tests sous forme d'assert : un cas général, un cas à un seul élément et un cas avec des valeurs négatives.

b) Écrire une précondition avec assert sur la liste.

c) Expliquer le rôle de la docstring.

Résoudre

Entraîne-toi★★☆

La fonction suivante doit renvoyer la moyenne d'une liste de nombres : a) Trouver le bogue et donner un jeu de test qui le met en évidence. b) Corriger la fonction. c)…

La fonction suivante doit renvoyer la moyenne d'une liste de nombres :

def moyenne(liste):

    s = 0

    for i in range(1, len(liste)):

        s = s + liste[i]

    return s / len(liste)

a) Trouver le bogue et donner un jeu de test qui le met en évidence.

b) Corriger la fonction.

c) Indiquer le comportement pour une liste vide et proposer une protection.

Résoudre

Objets et modules

Le paradigme objet regroupe des données et les fonctions qui les manipulent dans une classe.

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

c = Compte("Camille", 100)

c.deposer(50)

print(c.solde)   # 150

Compte est la classe ; c est un objet (une instance).
titulaire et solde sont des attributs ; deposer est une méthode.
__init__ est le constructeur ; self désigne l'objet courant.
On accède à un attribut ou une méthode avec la notation pointée : c.solde, c.deposer(50).

Interface et implémentation

L'interface d'une structure est la liste de ses opérations et de leur effet. L'implémentation est la manière dont elles sont codées. Une pile (LIFO) a pour interface empiler, depiler, est_vide. On peut l'implémenter avec une liste Python, ou avec une liste chaînée : l'utilisateur n'a pas à le savoir.

class Pile:

    def __init__(self):

        self.contenu = []

    def est_vide(self):

        return len(self.contenu) == 0

    def empiler(self, x):

        self.contenu.append(x)

    def depiler(self):

        """Renvoie et retire le sommet (pile non vide)."""

        assert not self.est_vide(), "pile vide"

        return self.contenu.pop()

Modularité

Un module est un fichier Python réutilisable : from math import sqrt. Son API est l'ensemble des fonctions et classes qu'il propose, décrit dans sa documentation. On utilise sqrt(x) sans connaître son code. Cela permet de découper un gros programme, de réutiliser du code, de travailler à plusieurs et de tester chaque morceau séparément.

Entraîne-toi★☆☆

On définit une classe : a) Identifier la classe, les attributs et les méthodes. b) Écrire les instructions qui créent un objet c pour « Camille » avec 100 €, puis…

On définit une classe :

class Compte:

    def __init__(self, titulaire, solde):

        self.titulaire = titulaire

        self.solde = solde

    def deposer(self, montant):

        self.solde = self.solde + montant

a) Identifier la classe, les attributs et les méthodes.

b) Écrire les instructions qui créent un objet c pour « Camille » avec 100 €, puis déposent 50 €.

c) Donner la valeur de c.solde ensuite.

Résoudre

Entraîne-toi★☆☆

a) Expliquer ce qu'est un module Python et donner l'instruction pour importer la fonction sqrt du module math. b) Expliquer la notion d'interface (API) d'une…

a) Expliquer ce qu'est un module Python et donner l'instruction pour importer la fonction sqrt du module math.

b) Expliquer la notion d'interface (API) d'une bibliothèque en prenant cet exemple.

c) Citer deux avantages de la modularité pour un grand programme.

Résoudre

Entraîne-toi★★☆

On implémente une pile avec une classe Pile contenant la liste contenu. a) Écrire les méthodes empiler, depiler et est_vide. b) Écrire une docstring et une précondition…

On implémente une pile avec une classe Pile contenant la liste contenu.

a) Écrire les méthodes empiler, depiler et est_vide.

b) Écrire une docstring et une précondition (assert) pour depiler.

c) Expliquer la différence entre l'interface d'une pile et son implémentation, en proposant une autre implémentation possible.

Résoudre

Entraîne-toi★★★

On souhaite écrire un module geometrie.py qui gère des points du plan et des segments. a) Proposer une classe Point (attributs x, y) avec une méthode distance(autre),…

On souhaite écrire un module geometrie.py qui gère des points du plan et des segments.

a) Proposer une classe Point (attributs x, y) avec une méthode distance(autre), puis une classe Segment construite à partir de deux points avec une méthode longueur.

b) Écrire une batterie de tests avec assert : le segment de (0 ; 0) à (3 ; 4) mesure 5 ; un segment réduit à un point mesure 0 ; la distance est symétrique.

c) Expliquer pourquoi on teste aussi les cas limites et discuter l'usage de la comparaison de flottants.

d) Rédiger la documentation de l'API publique du module à l'intention d'un autre développeur.

Résoudre

Récursivité

Une fonction est récursive si elle s'appelle elle-même. Elle comporte toujours :

un cas de base qui ne fait pas d'appel ;
un appel récursif sur un problème plus petit.

def somme_chiffres(n):

    if n < 10:

        return n

    return n % 10 + somme_chiffres(n // 10)

Dérouler un appel

Calcul de somme_chiffres(4276).

Décomposer. $4\,276 = 427 \times 10 + 6$, donc somme_chiffres(4276) = 6 + somme_chiffres(427).

Continuer. somme_chiffres(427) = 7 + somme_chiffres(42) puis somme_chiffres(42) = 2 + somme_chiffres(4).

Cas de base. somme_chiffres(4) = 4. On remonte : $2+4=6$, $7+6=13$, $6+13=19$.

À toi. Écris une version itérative avec une boucle while n > 0.

def somme_chiffres_iter(n):

    s = 0

    while n > 0:

        s = s + n % 10

        n = n // 10

    return s

Les deux versions relèvent de paradigmes différents : récursif (on exprime le résultat à partir de problèmes plus petits) et impératif (on modifie des variables dans une boucle). La version récursive est souvent plus proche de la définition mathématique ; la boucle évite l'empilement des appels.

Terminaison, correction, coût

Terminaison : on exhibe une quantité entière positive qui décroît strictement à chaque appel (ici $n$ diminue) ; elle ne peut pas décroître indéfiniment.
Correction : on la montre par récurrence (forte si l'appel porte sur une valeur quelconque plus petite).

Exponentiation rapide

def puissance(x, n):

    if n == 0:

        return 1

    if n % 2 == 0:

        y = puissance(x, n // 2)

        return y * y

    return x * puissance(x, n - 1)

Dérouler puissance(2, 13). $13$ impair : $2 \times$ puissance(2, 12) ; $12$ pair : on élève au carré puissance(2, 6) ; $6$ pair : carré de puissance(2, 3) ; $3$ impair : $2 \times$ puissance(2, 2) ; $2$ pair : carré de puissance(2, 1) ; $1$ impair : $2 \times$ puissance(2, 0) ; enfin puissance(2, 0) vaut $1$. La chaîne est $13 \to 12 \to 6 \to 3 \to 2 \to 1 \to 0$ : 7 appels et 6 multiplications (3 carrés et 3 multiplications par $2$), contre 13 pour la méthode naïve.

Terminaison. À chaque appel, $n$ diminue strictement (soit $n-1$, soit $n/2$) et reste un entier $\geq 0$.

Correction. Pour $n=0$ : $x^0=1$. Si $n$ est pair, $y=x^{n/2}$ par hypothèse, donc $y\cdot y=x^n$. Si $n$ est impair, $x\cdot x^{n-1}=x^n$.

Coût. Après un appel impair, l'appel suivant est pair et divise $n$ par 2 : il y a au plus $2\log_2 n + 2$ appels, soit $O(\log_2 n)$, contre $n$ multiplications pour la méthode naïve.

Entraîne-toi★★☆

a) Écrire une fonction récursive somme_chiffres(n) qui renvoie la somme des chiffres d'un entier $n \ge 0$. b) Dérouler somme_chiffres(4 276). c) Écrire une version…

a) Écrire une fonction récursive somme_chiffres(n) qui renvoie la somme des chiffres d'un entier $n \ge 0$.

b) Dérouler somme_chiffres(4 276).

c) Écrire une version itérative et comparer les deux approches (paradigmes récursif et impératif).

Résoudre

Entraîne-toi★★★

On considère la fonction récursive : a) Dérouler puissance(2, 13) et compter les multiplications. b) Montrer par récurrence forte la correction : puissance(x, n) renvoie…

On considère la fonction récursive :

def puissance(x, n):

    if n == 0:

        return 1

    if n % 2 == 0:

        y = puissance(x, n // 2)

        return y * y

    return x * puissance(x, n - 1)

a) Dérouler puissance(2, 13) et compter les multiplications.

b) Montrer par récurrence forte la correction : puissance(x, n) renvoie $x^n$.

c) Justifier la terminaison à l'aide d'une quantité strictement décroissante.

d) Montrer que le nombre d'appels est en $O(\log_2 n)$ et comparer avec la méthode naïve.

Résoudre

Programme comme donnée et calculabilité

Pour un ordinateur, un programme est un fichier de texte (ou de nombres) comme un autre. Un éditeur, un compilateur, un antivirus reçoivent des programmes en entrée. Un programme est donc une donnée, et on peut écrire des fonctions qui prennent un programme en argument.

Cela soulève une question : peut-on écrire un programme arret(prog, donnee) qui renvoie True si prog(donnee) s'arrête, False si elle boucle indéfiniment ? Ce serait un testeur universel de bogues.

Démonstration par l'absurde

Supposons que arret existe.

Construire un programme piège.

def paradoxe(p):

    if arret(p, p):

        while True:

            pass

    else:

        return 0

L'appliquer à lui-même : paradoxe(paradoxe). Si arret(paradoxe, paradoxe) vaut True, alors paradoxe(paradoxe) boucle indéfiniment : contradiction avec le True.

Autre cas. Si elle vaut False, alors paradoxe(paradoxe) renvoie 0 donc s'arrête : contradiction avec le False.

Conclusion. Dans les deux cas on aboutit à une contradiction : arret ne peut pas exister.

Conséquence : aucun outil automatique ne peut décider, pour tout programme, s'il termine. On vérifie donc les programmes par des tests, des preuves au cas par cas, ou des outils qui ne traitent que certaines familles de programmes. La calculabilité étudie ce qu'un algorithme peut calculer : elle ne dépend pas du langage de programmation.

Entraîne-toi★★★

On veut démontrer que le problème de l'arrêt est indécidable. Supposons qu'il existe une fonction arret(prog, donnee) qui renvoie True si le programme prog appliqué à…

On veut démontrer que le problème de l'arrêt est indécidable. Supposons qu'il existe une fonction arret(prog, donnee) qui renvoie True si le programme prog appliqué à donnee s'arrête, False sinon.

a) Expliquer pourquoi un programme peut être traité comme une donnée.

b) On définit paradoxe(p) : si arret(p, p) renvoie True, la fonction boucle indéfiniment ; sinon elle renvoie 0. Que se passe-t-il pour paradoxe(paradoxe) ?

c) En déduire la conclusion et expliquer ce que cela implique pour un outil de vérification automatique de programmes.

Résoudre

Retour au début : un jeu de tests bien choisi (liste vide comprise) aurait aidé Lucas, mais aucun programme ne peut vérifier automatiquement tous les autres.

À s'entraîner ! 9 exercices dans cette section

★☆☆ On considère la fonction : a) Écrire trois tests sous forme d'assert : un cas général, un…★☆☆ On définit une classe : a) Identifier la classe, les attributs et les méthodes. b) Écrire…★☆☆ a) Expliquer ce qu'est un module Python et donner l'instruction pour importer la fonction…

L'essentiel

Une fonction se spécifie par une docstring ; assert vérifie des préconditions et exécute des tests, dont les cas limites.
Une classe regroupe attributs et méthodes ; l'interface d'une structure est distincte de son implémentation.
Un module est utilisé grâce à son API et facilite le découpage et la réutilisation du code.
Une fonction récursive a un cas de base et un appel sur un problème plus petit ; on justifie terminaison et correction.
Un programme est une donnée ; le problème de l'arrêt est indécidable.