Exercices: Programmation, tests et calculabilité

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

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

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

1. c) Expliquer le rôle de la docstring.

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

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

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

1. c) Donner la valeur de c.solde ensuite.

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

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

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

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

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

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

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

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)

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

1. b) Corriger la fonction.

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

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

1. b) Dérouler somme_chiffres(4 276).

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

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.

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

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

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

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)

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

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

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

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

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

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

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

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

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