Terminale

Langages et programmation

Ce chapitre de Terminale approfondit la pratique de la programmation au-delà de sa syntaxe : comprendre qu'un programme est aussi une donnée et que certains problèmes sont indécidables, écrire et analyser des fonctions récursives, structurer du code en modules documentés, choisir un paradigme de programmation adapté à un problème, et savoir déboguer méthodiquement un programme.

Programme et donnée, calculabilité et décidabilité

Le programme est aussi une donnée

Un programme informatique n'est pas fondamentalement différent des données qu'il manipule : du point de vue de la machine, un fichier source, un fichier exécutable, ou même une fonction, ne sont que des suites de bits. C'est cette absence de différence de nature entre code et donnée qui explique la puissance de nombreux outils informatiques modernes.

L'interpréteur Python comme exemple. Quand on exécute python prog.py, un programme (l'interpréteur) prend en entrée un fichier prog.py — qui est une donnée pour lui — vérifie sa syntaxe, puis l'exécute ligne après ligne avant de s'arrêter. Le cycle d'un interpréteur est : lire une instruction, la vérifier, l'exécuter (ou évaluer l'expression), passer à la suivante. Lorsqu'on lance l'interpréteur en mode interactif pour obtenir l'invite >>>, on parle de REPL (Read Eval Print Loop).

D'autres exemples de programmes qui prennent des programmes en entrée :

Un lanceur de tests comme pytest.main(["test_a.py", "test_b.py"]) prend en entrée une liste de programmes et exécute les tests qu'ils contiennent. Couplé à un système de gestion de versions, cela permet l'intégration continue.
Un décorateur Python est une fonction qui prend en entrée une fonction et en renvoie une autre, « décorée ».
Un antivirus scanne des fichiers exécutables (des programmes) à la recherche de séquences suspectes ; un virus est lui-même un programme qui prend des programmes en entrée pour en produire d'autres, infectés.
Un système d'exploitation gère l'exécution d'autres programmes, en leur donnant accès à des ressources (fichiers, réseau), tout en essayant de ne jamais s'arrêter lui-même.

Cette perméabilité entre code et donnée est un facteur essentiel de progrès en informatique (interpréteurs, compilateurs, systèmes d'exploitation), et se retrouve au cœur des résultats théoriques sur la calculabilité.

La calculabilité ne dépend pas du langage

Un problème est dit calculable s'il existe un algorithme qui le résout en un nombre fini d'étapes. La thèse de Church-Turing affirme que toutes les notions raisonnables d'algorithme ou de procédure effective — machines de Turing, fonctions du λ-calcul, programmes Python, Java, ou tout autre langage — calculent exactement les mêmes fonctions.

Une thèse, contrairement à un théorème, ne se démontre pas : elle affirme qu'une notion intuitive (« ce qui est calculable ») correspond exactement à une notion formelle (« calculable par une machine de Turing »). On ne peut qu'apporter des arguments en sa faveur ou tenter de la réfuter.

Conséquence pratique : ce qu'un programme Python ne peut pas calculer en un temps fini, aucun autre langage de programmation ne pourra le calculer non plus — y compris les futurs ordinateurs quantiques. La calculabilité est donc une propriété du problème, pas du langage utilisé pour l'exprimer.

Le problème de l'arrêt est indécidable

Un problème de décision (dont la réponse est oui/non) est dit décidable s'il existe un algorithme qui le résout et qui s'arrête toujours en donnant la bonne réponse. Le problème de l'arrêt se formule ainsi :

Existe-t-il un programme qui, étant donné le code source d'un programme prog et une entrée x, détermine toujours correctement si prog s'arrête lorsqu'on l'exécute avec l'entrée x ?

Démonstration par l'absurde (raisonnement diagonal). Supposons qu'une telle fonction existe : arret(prog, x), qui termine toujours et renvoie True si prog(x) s'arrête, False sinon. Construisons alors :

def diag(entree):
    if arret(entree, entree):
        while True:
            pass          # boucle infinie
    else:
        return True

Que se passe-t-il si on évalue diag(diag) ?

Si arret(diag, diag) renvoie True (c'est-à-dire que diag(diag) est censé s'arrêter), alors diag entre dans la boucle infinie : diag(diag) ne s'arrête pas.
Si arret(diag, diag) renvoie False (c'est-à-dire que diag(diag) est censé ne pas s'arrêter), alors diag renvoie True : diag(diag) s'arrête.

Dans les deux cas, on obtient une contradiction : diag(diag) s'arrête si et seulement si arret(diag, diag) affirme qu'elle ne s'arrête pas. L'hypothèse de départ est donc fausse : une fonction arret qui répond toujours correctement ne peut pas exister. Le problème de l'arrêt est indécidable.

Ce résultat a été démontré indépendamment par Alan Turing (avec les machines de Turing universelles) et Alonzo Church (avec le λ-calcul), tous deux influencés par le théorème d'incomplétude de Gödel.

Le théorème de Rice (culture)

Le problème de l'arrêt n'est qu'un cas particulier d'un résultat plus général, le théorème de Rice : toute propriété non triviale du comportement d'un programme est indécidable. Par exemple, il n'existe aucun algorithme général capable de répondre systématiquement à des questions comme : « ce programme ne renvoie-t-il jamais 42 ? », « ce programme contient-il un virus ? », « ce programme accède-t-il à un site web ? ». C'est une des raisons pour lesquelles on ne peut pas fabriquer un antivirus parfait, ou un vérificateur universel de bugs : on peut seulement détecter certains cas particuliers.

Exercice — Un décorateur : le programme comme donnée

En programmation, un décorateur est une fonction qui prend une autre fonction en argument (elle la traite donc comme une donnée) et renvoie une nouvelle fonction modifiée.

Écrire une fonction chronometre(f) qui prend une fonction f en argument et renvoie une nouvelle fonction qui, lorsqu'elle est appelée, affiche le nom de f (grâce à f.__name__) avant d'exécuter f et de renvoyer son résultat. Tester en « décorant » une fonction carre(x) qui renvoie x * x.

Exercice — Compléter le raisonnement sur le problème de l'arrêt

On suppose que la fonction arret(prog, x) existe et fonctionne parfaitement (elle termine toujours et répond correctement). On considère :

def diag(entree):
    if arret(entree, entree):
        while True:
            pass
    else:
        return True

Que fait diag(entree) si arret(entree, entree) renvoie False ?
Que fait diag(entree) si arret(entree, entree) renvoie True ?
En étudiant l'appel diag(diag) (c'est-à-dire entree = diag), montrer que l'existence de arret mène à une contradiction.

QCM — Programme, donnée et décidabilité

1. Que peut-on dire d'un décorateur Python (une fonction qui prend une fonction en argument et en renvoie une autre) ?

2. Que peut-on affirmer à propos du problème de l'arrêt ?

3. D'apres le theoreme de Rice evoque dans le cours, laquelle des propositions suivantes est decidable par un algorithme general capable de l'appliquer a n'importe quel programme ?

Récursivité

Qu'est-ce qu'une fonction récursive ?

Une fonction est dite récursive lorsqu'elle s'appelle elle-même dans son propre corps. Elle comporte toujours :

un ou plusieurs cas de base (des valeurs de l'argument pour lesquelles le résultat est connu directement, sans appel récursif) ;
un appel récursif, qui traite un problème de taille strictement plus petite, en se rapprochant du cas de base.

Exemple : la puissance d'un nombre. On sait que $a^0 = 1$ et $a^n = a \times a^{n-1}$ pour $n \geqslant 1$ . Cette définition mathématique se traduit directement en Python :

def puissance(a, n):
    if n == 0:          # cas de base
        return 1
    else:
        return a * puissance(a, n - 1)   # appel recursif

Exemple : la factorielle. De même, $0! = 1$ et $n! = n \times (n-1)!$ pour $n \geqslant 1$ :

def factorielle(n):
    if n == 0:
        return 1
    return n * factorielle(n - 1)

La pile d'exécution

Lorsqu'une fonction récursive s'appelle elle-même, chaque appel « en attente » (qui n'a pas encore reçu son résultat) est stocké dans une structure appelée pile d'exécution (call stack). Une pile fonctionne comme une pile d'assiettes : on peut empiler un élément, ou dépiler le dernier élément posé — mais pas accéder directement à un élément qui n'est pas au sommet.

Pour factorielle(4), la pile se construit ainsi (chaque ligne empile un nouvel appel en attente) :

factorielle(4)  attend  4 * factorielle(3)
factorielle(3)  attend  3 * factorielle(2)
factorielle(2)  attend  2 * factorielle(1)
factorielle(1)  attend  1 * factorielle(0)
factorielle(0)  renvoie 1                     <- cas de base atteint

Puis on dépile en remontant, chaque appel en attente calculant son résultat :

factorielle(0) -> 1
factorielle(1) -> 1 * 1  = 1
factorielle(2) -> 2 * 1  = 2
factorielle(3) -> 3 * 2  = 6
factorielle(4) -> 4 * 6  = 24

Attention au débordement de pile. La pile d'exécution a une taille limitée : au-delà d'un certain nombre d'appels récursifs imbriqués (1000 par défaut en Python), une erreur RecursionError (stack overflow) est levée. C'est pourquoi une fonction récursive doit toujours progresser vers son cas de base.

Méthode pour écrire une fonction récursive

Déterminer le type de la valeur renvoyée.
Identifier le ou les cas de base : pour quelle(s) valeur(s) de l'argument le résultat est-il connu directement ?
Déterminer comment la taille du problème diminue à chaque appel (un entier qui décroît, une liste qui raccourcit, etc.), pour garantir qu'on atteindra le cas de base.
Écrire l'appel récursif, en veillant à ce qu'il renvoie un résultat du même type que le cas de base.

La suite de Fibonacci : une récursivité qui explose

La suite de Fibonacci est définie par $u_0 = 0$ , $u_1 = 1$ et $u_{n+2} = u_{n+1} + u_n$ . Une écriture récursive naïve est immédiate :

def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

Cette fonction renvoie le bon résultat, mais devient très lente dès que n dépasse une trentaine (essayer fibo(37)). En effet, chaque appel fibo(n) déclenche deux appels récursifs : le nombre de nœuds de l'arbre des appels croît de façon exponentielle, de l'ordre de $\Theta(2^n)$ . Par exemple, fibo(5) recalcule plusieurs fois fibo(2) et fibo(1) :

fibo(5)
+-- fibo(4)
|   +-- fibo(3)
|   |   +-- fibo(2) -> fibo(1) + fibo(0)
|   |   +-- fibo(1)
|   +-- fibo(2) -> fibo(1) + fibo(0)   (recalcule !)
+-- fibo(3)                              (recalcule tout !)
    +-- fibo(2) -> ...
    +-- fibo(1)

La mémoïsation consiste à garder en mémoire (dans un dictionnaire, par exemple) les résultats déjà calculés, pour ne jamais les recalculer :

def fibo_memo(n):
    memo = {}
 
    def fib(n):
        if n in memo:
            return memo[n]
        if n < 2:
            memo[n] = n
        else:
            memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]
 
    return fib(n)

Grâce à memo, chaque valeur de fib n'est calculée qu'une seule fois : la complexité passe de $\Theta(2^n)$ à $\Theta(n)$ .

Complexité d'une fonction récursive

Pour analyser la complexité d'une fonction récursive, on note $T_n$ le nombre d'opérations nécessaires pour un problème de taille $n$ , on établit une relation de récurrence sur $T_n$ , puis on la résout. Quelques cas classiques :

Relation de récurrence	Complexité
$T_n = T_{n-1} + \Theta(1)$	$\Theta(n)$
$T_n = T_{n-1} + \Theta(n)$	$\Theta(n^2)$
$T_n = 2\,T_{n-1} + \Theta(1)$	$\Theta(2^n)$
$T_n = T_{n/2} + \Theta(1)$	$\Theta(\log n)$

Ainsi, puissance(a, n) vérifie $T_n = T_{n-1} + \Theta(1)$ , donc $T_n = \Theta(n)$ ; la fonction fibo naïve vérifie $T_n = T_{n-1} + T_{n-2} + \Theta(1)$ , dont la croissance est exponentielle, d'où la lenteur observée en pratique.

Exercice — Tracer la pile d'exécution

On considère la fonction :

def somme(n):
    if n == 0:
        return 0
    return n + somme(n - 1)

Quel est le cas de base de cette fonction ?
Dérouler, comme dans le cours, la construction puis le dépilement de la pile d'exécution pour l'appel somme(4).
En déduire la valeur renvoyée par somme(4).

Exercice — Les tours de Hanoï

Le jeu des tours de Hanoï comporte trois piquets (0, 1 et 2) et $n$ disques de tailles décroissantes, initialement empilés sur le piquet 0. Le but est de déplacer tous les disques sur le piquet 2, en ne déplaçant qu'un seul disque à la fois et sans jamais poser un disque sur un disque plus petit.

Principe récursif. Pour déplacer une pile de $n$ disques du piquet source vers le piquet dest (en utilisant le troisième piquet aux) :

déplacer les $n-1$ disques du dessus de source vers aux ;
déplacer le disque restant (le plus grand) de source vers dest ;
déplacer les $n-1$ disques de aux vers dest.
Quel est le cas de base de cet algorithme (pour quelle valeur de $n$ le problème est-il trivial) ?
Écrire une fonction récursive hanoi(n, source, aux, dest) qui affiche, pour chaque déplacement d'un disque, un message.
Écrire une fonction nb_deplacements(n) qui renvoie le nombre total de déplacements nécessaires pour $n$ disques, sans simuler le jeu. Quelle relation lie nb_deplacements(n) et nb_deplacements(n - 1) ?

Exercice — Bac NSI — Métropole session de remplacement 2022 (exercice 2)

Exercice tiré du bac NSI Métropole (session de remplacement) 2022, sur les classes et la récursivité (villas immobilières).

class Piece:
    def __init__(self, a, b):
        self.nom = a
        self.sup = b   # superficie
 
class Villa:
    def __init__(self, a, b, c, d, e):
        self.nom = a
        self.sejour = b
        self.ch1 = c
        self.ch2 = d
        self.eqCuis = e   # "eq" ou "non eq"
 
    def nom(self):
        return self.nom
 
    def surface(self):
        return ......
 
    def equip(self):
        return self.eqCuis
 
v = []
v.append(Villa("Les quatre vents", Piece("séjour",40), Piece("ch1",10), Piece("ch2",20), "eq"))
v.append(Villa("Les goélands", Piece("séjour",50), Piece("ch1",15), Piece("ch2",15), "eq"))
v.append(Villa("Rêve d'été", Piece("séjour",30), Piece("ch1",15), Piece("ch2",20), "non eq"))
v.append(Villa("Les oliviers", Piece("séjour",30), Piece("ch1",10), Piece("ch2",20), "eq"))
v.append(Villa("Bellevue", Piece("séjour",30), Piece("ch1",10), Piece("ch2",20), "non eq"))

1.a. Combien d'éléments contient v ? 1.b. Que renvoie v[1].nom() ? 1.c. Compléter surface() pour renvoyer la surface totale (séjour + ch1 + ch2). 2. Écrire la portion de programme affichant le nom de chaque villa équipée d'une cuisine.

Récursivité.

3. Laquelle caractérise un appel récursif ? « appel d'une fonction par elle-même » / « appel dont l'exécution est un processus itératif » / « appel d'une fonction comportant une boucle ».

Algorithme pour max_surface(v) : si un seul élément, c'est le résultat ; sinon comparer v[0] et v[1], retirer la plus petite, relancer.

4. Écrire max_surface(v) en Python.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Amérique du Nord 2024 J2 (exercice 3, questions 9 et 10 — calcul récursif du solde)

Exercice tiré du bac NSI Amérique du Nord 2024 (jour 2), exercice 3, sur le calcul récursif d'un solde dans une blockchain.

On veut doter la classe Bloc d'une méthode calculer_solde(self, utilisateur) renvoyant le solde d'un utilisateur donné à l'issue de ce bloc. Le principe : le solde à l'issue d'un bloc est le solde à l'issue du bloc précédent, ajusté des transactions du bloc courant (l'utilisateur perd le montant de chaque transaction dont il est l'expéditeur, en gagne le montant de chaque transaction dont il est le destinataire). Le cas de base est un bloc sans précédent (bloc_precedent is None), où le solde vaut 0.

9. Écrire cette méthode récursive calculer_solde.

10. Écrire l'appel permettant de calculer le solde actuel d'Alice, à partir d'un objet ma_blockchain de type Blockchain.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 09, exercice 2 : conversions décimal-binaire récursives

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°09, exercice 2.

L'objectif de cet exercice est d'écrire deux fonctions récursives dec_to_bin et bin_to_dec, qui assurent respectivement la conversion de l'écriture décimale d'un nombre entier vers son écriture en binaire et, réciproquement, la conversion de l'écriture en binaire d'un nombre vers son écriture décimale. Dans cet exercice, on s'interdit l'usage des fonctions Python bin et int.

L'exemple suivant montre comment obtenir l'écriture en binaire du nombre 25 :

\begin{aligned} 25 &= 2 \times 12 + 1 \\ &= 2 \times (2 \times 6 + 0) + 1 \\ &= 2 \times (2 \times (2 \times 3 + 0) + 0) + 1 \\ &= 2 \times (2 \times (2 \times (2 \times 1 + 1) + 0) + 0) + 1 \\ &= 2 \times (2 \times (2 \times (2 \times (2 \times 0 + 1) + 1) + 0) + 0) + 1 \\ &= 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \\ &= 11001_2 \end{aligned}

L'écriture binaire de 25 est donc 11001.

On rappelle également que :

l'expression a // 2 calcule le quotient de la division euclidienne de a par 2 ;
l'expression a % 2 calcule le reste dans la division euclidienne de a par 2.

On indique enfin qu'en Python, si mot = "informatique", alors :

l'expression mot[-1] vaut 'e', c'est-à-dire le dernier caractère de la chaîne mot ;
l'expression mot[:-1] vaut 'informatiqu', c'est-à-dire la chaîne mot privée de son dernier caractère.

Compléter, puis tester, le code des deux fonctions ci-dessous. La fonction récursive dec_to_bin prend en paramètre un nombre entier et renvoie une chaîne de caractères contenant l'écriture en binaire du nombre passé en paramètre :

>>> dec_to_bin(25)
'11001'

La fonction récursive bin_to_dec prend en paramètre une chaîne de caractères représentant l'écriture d'un nombre en binaire et renvoie l'écriture décimale de ce nombre :

>>> bin_to_dec('101010')
42

def dec_to_bin(nb_dec):
    q, r = nb_dec // 2, nb_dec % 2
    if q == ...:
        return ...
    else:
        return dec_to_bin(...) + ...
 
def bin_to_dec(nb_bin):
    if len(nb_bin) == 1:
        if ... == '0':
            return 0
        else:
            return ...
    else:
        if nb_bin[-1] == '0':
            bit_droit = 0
        else:
            ...
        return ... * bin_to_dec(nb_bin[:-1]) + ...

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 27, exercice 2 : colorier une composante d'une image

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°27, exercice 2.

Soit une image binaire représentée dans un tableau à 2 dimensions. Les éléments M[i][j], appelés pixels, sont égaux soit à 0 soit à 1.

Une composante d'une image est un sous-ensemble de l'image constitué uniquement de 1, ou uniquement de 0, qui sont côte à côte, soit horizontalement soit verticalement.

Par exemple, dans l'image

M = 0 0 1 0
    0 1 0 1
    1 1 1 0
    0 1 1 0

les composantes formées de 1 sont : le pixel de la ligne 0 et de la colonne 2, seul ; le pixel de la ligne 1 et de la colonne 3, seul ; et le groupe des six pixels M[1][1], M[2][0], M[2][1], M[2][2], M[3][1] et M[3][2].

On souhaite, à partir d'un pixel égal à 1 dans une image M, donner la valeur val à tous les pixels de la composante à laquelle appartient ce pixel.

La fonction colore_comp1 prend pour paramètre une image M (représentée par une liste de listes), deux entiers i et j et une valeur entière val. Elle met à la valeur val tous les pixels de la composante du pixel M[i][j] s'il vaut 1 et ne fait rien sinon.

Par exemple, colore_comp1(M, 2, 1, 3) donne

M = 0 0 1 0
    0 3 0 1
    3 3 3 0
    0 3 3 0

Compléter le code récursif de la fonction colore_comp1 donné ci-dessous :

def colore_comp1(M, i, j, val):
    if M[i][j] != 1:
        return
 
    M[i][j] = val
 
    if i-1 >= 0: # propage à gauche
        colore_comp1(M, i-1, j, val)
    if ... < len(M): # propage à droite
        colore_comp1(M, ..., j, val)
    if ...: # propage en haut
        colore_comp1(M, ..., ..., val)
    if ...: # propage en bas
        ...

Exemple :

>>> M = [[0, 0, 1, 0], [0, 1, 0, 1], [1, 1, 1, 0], [0, 1, 1, 0]]
>>> colore_comp1(M, 2, 1, 3)
>>> M
[[0, 0, 1, 0], [0, 3, 0, 1], [3, 3, 3, 0], [0, 3, 3, 0]]

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2024 — Sujet 30, exercice 2 : traduire un nombre en chiffres romains

Banque nationale de sujets 2024 de l'épreuve pratique, sujet n°30, exercice 2.

Le but de cet exercice est d'écrire une fonction récursive traduire_romain qui prend en paramètre une chaîne de caractères, non vide, représentant un nombre écrit en chiffres romains et qui renvoie son écriture décimale.

Les chiffres romains considérés sont : I, V, X, L, C, D et M. Ils représentent respectivement les nombres 1, 5, 10, 50, 100, 500, et 1000 en base dix.

On dispose d'un dictionnaire romains dont les clés sont les caractères apparaissant dans l'écriture en chiffres romains et les valeurs sont les nombres entiers associés en écriture décimale :

romains = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}

Le code de la fonction traduire_romain fournie repose sur le principe suivant :

la valeur d'un caractère est ajoutée à la valeur du reste de la chaîne si ce caractère a une valeur supérieure (ou égale) à celle du caractère qui le suit ;
la valeur d'un caractère est retranchée à la valeur du reste de la chaîne si ce caractère a une valeur strictement inférieure à celle du caractère qui le suit.

Ainsi, XIV correspond au nombre $10 + 5 - 1$ puisque :

la valeur de X (10) est supérieure à celle de I (1), on ajoute donc 10 à la valeur du reste de la chaîne, c'est-à-dire IV ;
la valeur de I (1) est strictement inférieure à celle de V (5), on soustrait donc 1 à la valeur du reste de la chaîne, c'est-à-dire V.

On rappelle que pour priver une chaîne de caractères de son premier caractère, on utilisera l'instruction :

nom_de_variable[1:]

Par exemple, si la variable mot contient la chaîne "CDI", mot[1:] renvoie "DI".

Compléter le code de la fonction traduire_romain et le tester.

def traduire_romain(nombre):
    """ Renvoie l'écriture décimale du nombre donné en chiffres
    romains """
    if len(nombre) == 1:
        return ...
    elif romains[nombre[0]] >= ...:
        return romains[nombre[0]] + ...
    else:
        return ...

Exemples :

>>> traduire_romain("XIV")
14
>>> traduire_romain("CXLII")
142
>>> traduire_romain("MMXXIV")
2024

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2026 — Sujet 05 : empreinte carbone et dictionnaires imbriqués

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°05 (situation d'évaluation d'une heure).

Empreinte carbone

On s'intéresse ici à la notion d'empreinte carbone, qui correspond à la production de CO₂ (un gaz à effet de serre) imputable à un individu ou à un groupe pendant une année, exprimée en kilogrammes.

Dans le cadre de la lutte contre le réchauffement climatique, le site nosgestesclimat.fr propose un simulateur permettant d'obtenir une estimation de son empreinte carbone en répondant à des questions sur sa situation et sa consommation. Les résultats sont compilés dans un dictionnaire qui associe à des catégories (logement, alimentation, etc.) l'empreinte carbone associée.

Une utilisatrice prénommée Ada a réalisé une simulation de son empreinte carbone, dont les résultats vous sont donnés dans les fichiers empreinte_ada.json sous format brut et empreinte_ada_agr.json sous forme agrégée. Le JSON est un format de fichier permettant de stocker des listes ou des dictionnaires dont les clés sont des chaînes de caractères. Le module json permet de convertir des valeurs Python en JSON et réciproquement.

Dans un premier temps, on considère les résultats sous forme agrégée, représentés par un simple dictionnaire associant à chaque catégorie un entier représentant l'empreinte carbone correspondante (en kilogrammes de CO₂).

{
  "Logement": 2660,
  "Alimentation": 1500,
  ...
}

Question 1. Compléter le corps de la fonction total_simple. Ajouter un test permettant d'afficher l'empreinte carbone totale d'Ada, en utilisant les fonctions fournies pour accéder au fichier empreinte_ada_agr.json.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Le fichier réel obtenu par Ada est empreinte_ada.json, qui contient une imbrication de dictionnaires qui permet de préciser les postes de consommation. Par exemple :

{
  "Logement": {
    "Energie": {
      "Electricité": 206,
      "Cuisson": 105,
      "Chauffage individuel": 1500
    },
    "Construction": 650,
    "Location": 37,
    "Ameublement": 162
  },
  ...
}

Question 2. En utilisant la fonction est_dictionnaire qui teste la nature d'une valeur, écrire le corps de la fonction récursive total_rec qui calcule la somme des valeurs numériques présentes dans des dictionnaires imbriqués. Des tests sont fournis dans la fonction test_total_rec ; on pourra les compléter par un cas plus proche de la structure présente dans empreinte_ada.json.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Ada souhaite intégrer une fonctionnalité d'alerte. Il s'agit d'identifier si une source d'émission spécifique dépasse un certain seuil jugé critique. Une fonction nommée alerte_valeur_aberrante(empreinte, limite) a été rédigée à cet effet et figure dans le fichier Python fourni. Elle est censée parcourir l'ensemble du dictionnaire, y compris les sous-catégories, et renvoyer la valeur booléenne True dès qu'une valeur strictement supérieure à la limite est rencontrée.

Question 3. Lorsqu'on exécute la fonction alerte_valeur_aberrante sur le dictionnaire complet d'Ada avec une limite fixée à 1000, elle ne détecte aucune valeur aberrante, alors que le poste "Chauffage individuel" s'élève à 1500. Expliquer précisément l'origine de cette erreur de conception et proposer une version corrigée de la fonction.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 4. Afin de prévenir toute régression future sur la fonction alerte_valeur_aberrante corrigée, il convient de définir une stratégie de validation robuste. Proposer un jeu de tests pertinent pour cette fonction. Pour chaque cas de test envisagé, préciser la structure du dictionnaire fourni en entrée, le résultat attendu et la particularité algorithmique que ce test permet de vérifier.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichiers fournis

Le dossier comporte une version PDF de l'énoncé, le code source de départ empreinte.py et les deux fichiers empreinte_ada.json et empreinte_ada_agr.json. Le module json doit être disponible.

empreinte.py

import json
 
########### Fonctions données ###########
 
 
def chargement_json(nom_fichier):
    """Charge le contenu d'un fichier JSON dans un dictionnaire Python renvoyé"""
    with open(nom_fichier, "r", encoding="utf8") as curseur:
        return json.load(curseur)
 
 
def est_dictionnaire(objet):
    """Teste si un objet est de type dictionnaire"""
    return isinstance(objet, dict)
 
 
##########################################
 
 
# Première fonction à implémenter après avoir découvert le fichier JSON agrégé
# Cf fichier `empreinte_ada_agr.json`
def total_simple(empreinte):
    """Fonction qui renvoie l'empreinte carbone totale d'un dictionnaire associant
    une empreinte carbone à des noms de catégories"""
    pass
 
 
# Deuxième fonction : il faut la récursivité pour le cas des sous-catégories
# Cf fichier `empreinte_ada.json`
def total_rec(empreinte):
    """Fonction récursive qui renvoie l'empreinte carbone totale représentée
    par un dictionnaire dont les valeurs peuvent aussi être des dictionnaires"""
    pass
 
 
def test_total_rec():
    test_dico1 = {"a": 1, "d": 2}
    assert total_rec(test_dico1) == 3
    test_dico2 = {"a": {"b": 1, "c": 2}, "d": {"e": 3}}
    assert total_rec(test_dico2) == 6
 
# ==========================================
# Fonction à analyser et corriger (Question 3)
# ==========================================
 
 
def alerte_valeur_aberrante(empreinte, limite):
    """
    Fonction censée déterminer si au moins une valeur du dictionnaire
    dépasse strictement la limite donnée.
    """
    for categorie, valeur in empreinte.items():
        if est_dictionnaire(valeur):
            return alerte_valeur_aberrante(valeur, limite)
        else:
            if valeur > limite:
                return True
    return False

empreinte_ada_agr.json

{
  "Logement": 2660,
  "Alimentation": 1500,
  "Transport": 708,
  "Consommation": 893,
  "Services sociétaux": 1491
}

empreinte_ada.json

{
  "Alimentation": {
    "Repas": {
      "Viande": {
        "Blanche": 296,
        "Rouge": 814
      },
      "Autre": 97
    },
    "Déchets": 152,
    "Boisson": 141
  },
  "Logement": {
    "Energie": {
      "Electricité": 206,
      "Cuisson": 105,
      "Chauffage individuel": 1500
    },
    "Construction": 650,
    "Location": 37,
    "Ameublement": 162
  },
  "Transport": {
    "Voiture": 563,
    "Avion": 92,
    "En commun": 29,
    "Vélo": 10,
    "Train": 14
  },
  "Consommation": {
    "Textile": 418,
    "Loisirs": 168,
    "Produits manufacturés neufs": 121,
    "Electronique": {
      "Electroménager": 70,
      "Numérique": 90
    },
    "Consommables": 26
  },
  "Services sociétaux": {
    "Public": 1300,
    "Marchand": 191
  }
}

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Récursivité

1. Que se passe-t-il si une fonction récursive ne possède pas de cas de base atteint pour l'argument fourni ?

2. Pourquoi la fonction fibo(n) récursive naïve devient-elle très lente quand n augmente ?

3. En reprenant la version memoisee fibo_memo du cours, combien de valeurs distinctes le dictionnaire memo contient-il au total apres avoir calcule fibo_memo(5) ?

Modularité : API et bibliothèques

Le principe de modularité

La modularité consiste à découper un programme en éléments indépendants et réutilisables. Elle simplifie les tests, favorise la réutilisation du code, et facilite la maintenance. Ce principe s'applique à plusieurs échelles :

découper le code en fonctions ;
regrouper des fonctions liées à un même type d'objet dans une classe (elles deviennent alors des méthodes) ;
regrouper des fonctions par thème dans un fichier séparé, un module ;
regrouper plusieurs modules en une bibliothèque (ou package).

On rencontre la programmation modulaire dans deux situations : quand on écrit du code destiné à être réutilisé ou distribué, et quand on utilise du code écrit par quelqu'un d'autre.

Importer un module

Certains modules font partie de la bibliothèque standard de Python (installée par défaut) ; d'autres, dits modules tiers, s'installent avec un gestionnaire de paquets comme pip. Le dépôt PyPI (Python Package Index, https://pypi.org/) référence la plupart d'entre eux.

import random                     # importe tout le module
a = random.randint(1, 10)         # les fonctions sont prefixees par le nom du module
 
import random as rnd              # importe le module en le renommant (alias)
a = rnd.randint(1, 10)
 
from random import randint        # importe uniquement la fonction randint
a = randint(1, 10)                # plus besoin de prefixe, mais seule randint est disponible

À éviter absolument : from module import *. Cette syntaxe importe toutes les fonctions du module sans préfixe. On perd alors la trace de la provenance de chaque nom, ce qui peut créer des conflits de noms difficiles à déboguer, et rend le code difficile à relire ou à maintenir.

Utiliser une API à travers sa documentation

Une API (Application Programming Interface) est l'ensemble des fonctions, classes et méthodes qu'une bibliothèque met à disposition pour être utilisée, sans que l'on ait besoin de connaître son implémentation interne. Utiliser une bibliothèque, c'est donc avant tout savoir lire sa documentation : quels arguments une fonction attend-elle, que renvoie-t-elle, quelles exceptions peut-elle lever ?

Exemple. Le module standard statistics expose une API simple pour des calculs statistiques :

import statistics
 
notes = [12, 15, 9, 18, 14]
print(statistics.mean(notes))      # moyenne : 13.6
print(statistics.median(notes))    # mediane : 14
print(statistics.stdev(notes))     # ecart-type

On n'a pas besoin de savoir comment mean calcule la moyenne : il suffit de connaître sa signature (arguments attendus, valeur renvoyée), documentée officiellement.

Documenter avec les docstrings

Une docstring est une chaîne de caractères placée en première ligne d'une fonction, d'une classe ou d'un module, qui documente son rôle. Elle est consultable avec la fonction help.

def factorielle(n):
    """Renvoie la factorielle de l'entier naturel n.
 
    >>> factorielle(5)
    120
    """
    resultat = 1
    for i in range(2, n + 1):
        resultat = resultat * i
    return resultat
 
 
help(factorielle)   # affiche la docstring

>>> import random
>>> help(random)     # affiche la docstring du module
>>> help(print)       # affiche la docstring de la fonction print

Créer son propre module

Créer un module revient simplement à écrire des fonctions documentées dans un fichier .py, puis à l'importer depuis un autre fichier situé dans le même dossier. Par exemple, un fichier conversions.py :

"""Module de conversions d'unites de temperature."""
 
 
def celsius_vers_fahrenheit(temp_c):
    """Convertit une temperature de Celsius vers Fahrenheit."""
    return temp_c * 9 / 5 + 32
 
 
def fahrenheit_vers_celsius(temp_f):
    """Convertit une temperature de Fahrenheit vers Celsius."""
    return (temp_f - 32) * 5 / 9

Depuis un autre fichier du même dossier, on l'utilise comme n'importe quel module :

import conversions
 
print(conversions.celsius_vers_fahrenheit(20))    # 68.0
help(conversions.fahrenheit_vers_celsius)          # affiche la docstring

Exercice — Créer et documenter un module

Écrire un module geometrie.py contenant deux fonctions documentées par une docstring : aire_rectangle(longueur, largeur), qui renvoie l'aire d'un rectangle, et perimetre_rectangle(longueur, largeur), qui renvoie son périmètre.

Écrire ensuite le code qui importe ce module (en le renommant geo) et affiche l'aire et le périmètre d'un rectangle de longueur 5 et de largeur 3.

Exercice — Bac NSI — Asie/Pacifique 2022 J2 (exercice 1)

Exercice tiré du bac NSI 2022 (Asie/Pacifique, Jour 2), sur les commandes Linux et le module Python os.

L'entreprise capNSI range les contrats de ses clients dans des sous-dossiers de Contrats, sur une distribution Linux.

1. À partir de ~, écrire l'instruction affichant le contenu de Contrats.

2. Créer un sous-dossier TURING_Alan dans Contrats depuis la racine, puis lui attribuer tous les droits pour l'utilisateur et le groupe, lecture seule pour les autres.

En Python, os.mkdir(chemin) crée un dossier, os.chmod(chemin, 774) en fixe les droits.

tab_clients = [
    ('LOVELACE', 'Ada'), ('BOOLE', 'George'), ('VONNEUMANN', 'John'),
    ('SHANNON', 'Claude'), ('KNUTH', 'Donald'),
]

3. Écrire formatage(tab), qui transforme un tableau de couples (Nom, Prénom) en tableau de chaînes "NOM_Prenom".

4. Écrire creation_dossiers(tab), qui crée, pour chaque chaîne de tab, un dossier dans Contrats avec les mêmes droits que TURING_Alan.

QCM — Modularité, API et bibliothèques

1. Pourquoi l'instruction from module import * est-elle déconseillée ?

2. Quelle instruction permet d'afficher la docstring d'une fonction f ?

3. On a cree le module conversions.py du cours (fonctions celsius_vers_fahrenheit et fahrenheit_vers_celsius), dans le meme dossier qu'un script principal.py qui contient uniquement la ligne : from conversions import celsius_vers_fahrenheit. Que se passe-t-il si principal.py appelle ensuite fahrenheit_vers_celsius(0) ?

Paradigmes de programmation

Qu'est-ce qu'un paradigme de programmation ?

Un paradigme de programmation est une façon d'envisager l'écriture d'un programme, un « style » qui organise la pensée du programmeur. Quel que soit le paradigme choisi, le code est finalement traduit en instructions machine de bas niveau, de nature impérative : des allers-retours entre le processeur et la mémoire. Mais il est souvent plus efficace de rapprocher le langage de programmation de la façon de penser du programmeur plutôt que l'inverse — d'où l'existence de plusieurs paradigmes. Un même langage moderne (comme Python) permet en général de combiner plusieurs paradigmes selon les besoins.

Le paradigme impératif

Dans le paradigme impératif, un programme est une suite d'instructions qui modifient explicitement l'état de variables au fil de l'exécution (affectations, boucles, conditions). C'est le paradigme le plus proche du fonctionnement de la machine, et le plus répandu (C, Python « classique », Fortran…).

def somme_carres_pairs_imperatif(nombres):
    """Version imperative : boucle et accumulateur."""
    total = 0
    for x in nombres:
        if x % 2 == 0:
            total = total + x ** 2
    return total
 
 
print(somme_carres_pairs_imperatif([1, 2, 3, 4, 5, 6]))   # 2**2 + 4**2 + 6**2 = 56

Le paradigme fonctionnel

Le paradigme fonctionnel (Lisp, Haskell, OCaml...) fait partie des paradigmes déclaratifs : on décrit ce que l'on veut obtenir (le rapport entre données et résultat), plutôt que la séquence précise d'instructions pour y parvenir. Ses caractéristiques principales :

pas d'affectation modifiable : une valeur, une fois liée à un nom, n'est jamais modifiée (on crée de nouvelles valeurs plutôt que d'« écraser » les anciennes) ;
les fonctions n'ont pas d'effets de bord : à mêmes arguments, elles renvoient toujours le même résultat (idempotence) ;
les fonctions sont des objets comme les autres : elles peuvent être passées en argument à d'autres fonctions (fonctions d'ordre supérieur), ou créées « à la volée » avec lambda ;
la récursivité remplace souvent les boucles.

Python n'est pas un langage fonctionnel pur, mais il permet un style fonctionnel avec lambda, map, filter, et les compréhensions de listes :

def somme_carres_pairs_fonctionnel(nombres):
    """Version fonctionnelle : composition de fonctions, pas de boucle explicite."""
    return sum(x ** 2 for x in nombres if x % 2 == 0)
 
 
print(somme_carres_pairs_fonctionnel([1, 2, 3, 4, 5, 6]))   # 56

On peut aussi filtrer une liste avec une fonction créée à la volée grâce à lambda :

pair_et_positif = lambda n: n % 2 == 0 and n >= 0
nombres = [-4, -3, -2, -1, 0, 1, 2, 3, 4]
print(list(filter(pair_et_positif, nombres)))   # [0, 2, 4]

L'absence d'effets de bord facilite la programmation concurrente : si res = f1(a, b) + f2(a, c), les appels à f1 et f2 peuvent être exécutés dans n'importe quel ordre (voire en parallèle), car a n'est jamais modifié entre-temps.

Le paradigme objet

La programmation orientée objet (POO), née avec le langage Simula (années 1960) puis popularisée par Smalltalk, réunit données et traitements au sein d'une même entité : l'objet. Un objet est une instance d'une classe, qui définit ses attributs (données) et ses méthodes (fonctions qui agissent sur ces données).

class CollectionNombres:
    """Regroupe une liste de nombres et les traitements associes."""
 
    def __init__(self, nombres):
        self.nombres = nombres
 
    def somme_carres_pairs(self):
        """Version objet : la donnee et le traitement sont lies."""
        return sum(x ** 2 for x in self.nombres if x % 2 == 0)
 
 
collection = CollectionNombres([1, 2, 3, 4, 5, 6])
print(collection.somme_carres_pairs())   # 56

Ici, nombres (la donnée) et somme_carres_pairs (le traitement) sont regroupés au sein d'un même objet collection, qui devient « autonome » et peut être manipulé comme un tout.

Comparer et choisir un paradigme

Paradigme	Question centrale	Exemple de langage	Bien adapté à
Impératif	Comment faire, étape par étape ?	C, Python	Algorithmes simples, contrôle fin des ressources
Fonctionnel	Quel est le résultat attendu ?	Haskell, OCaml	Calcul parallèle/concurrent, transformations de données
Objet	Quelles entités et quelles interactions ?	Java, Python, C++	Modélisation de systèmes complexes, interfaces graphiques

En pratique, le choix d'un paradigme dépend du problème à résoudre : un pilote de périphérique bas niveau reste impératif, un traitement de flux de données massif tire parti du fonctionnel (facile à paralléliser), une simulation avec de nombreuses entités en interaction (jeu vidéo, interface graphique) se prête bien à l'objet. Les langages modernes, comme Python, permettent de combiner ces styles selon les besoins d'un même programme.

Exercice — Trois façons de résoudre le même problème

On souhaite écrire une fonction qui renvoie la liste des mots d'une phrase (donnée sous forme de chaîne de caractères) dont la longueur est strictement supérieure à 4 caractères, en majuscules.

Écrire une solution mots_longs_imperatif(phrase) en paradigme impératif (boucle for et accumulateur).
Écrire une solution mots_longs_fonctionnel(phrase) en paradigme fonctionnel (compréhension de liste, sans boucle for explicite modifiant un accumulateur).
Écrire une classe Phrase en paradigme objet, avec une méthode mots_longs() qui fait le même traitement sur self.texte.

Exercice — Bac NSI — Amérique du Nord 2025 (exercice 2, partie POO)

Exercice 2 (6 points, partie programmation orientée objet) du sujet de bac NSI Amérique du Nord 2025, jour 1.

Une entreprise gère des colis via une classe Colis : id (identifiant unique, str), poids (float, kg), adresse (str), etat (str parmi 'préparé', 'transit', 'livré', initialisé à 'préparé' à la création) :

class Colis:
    def __init__(self, id, poids, adresse):
        self.id = id
        self.poids = poids
        self.adresse = adresse
        self.etat = 'préparé'

Écrire la méthode passer_transit de la classe Colis, qui met l'état à 'transit'.

On dispose de ajouter_colis(liste, colis), qui ajoute simplement colis en fin de liste par liste.append(colis).

Dans cette question uniquement, un transporteur refuse les colis de plus de 25 kg. Recopier et modifier ajouter_colis pour qu'elle ajoute le colis seulement si son poids est ≤ 25 kg, et affiche "Dépassement du poids maximal autorisé" sinon.
Écrire une fonction nb_colis(liste) qui renvoie le nombre de colis d'une liste d'objets Colis.
Recopier et compléter les lignes 2 et 4 de :

def poids_total(liste):
    total = ...
    for c in liste:
        total = ...
    return total

Écrire une fonction liste_colis_etat(liste, statut) qui renvoie une nouvelle liste contenant les colis de liste dont l'état vaut statut.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Bac NSI — Centres étrangers 2024 J1 (exercice 3, partie POO)

Exercice 3 (8 points, partie Python/POO et débogage) du sujet de bac NSI Centres étrangers (groupe 1) 2024, jour 1.

On veut éditer une facture correspondant au séjour d'un client, à partir d'un tuple de trois objets des classes Client, Reservation et Emplacement :

from datetime import datetime
 
class Client:
    def __init__(self, nom, prenom, adresse, ville, pays, telephone):
        self.nom = nom
        self.prenom = prenom
        self.adresse = adresse
        self.ville = ville
        self.pays = pays
        self.telephone = telephone
 
class Reservation:
    def __init__(self, id_reservation, nombre_personne, date_arrivee, date_depart):
        self.id_reservation = id_reservation
        self.nombre_personne = nombre_personne
        self.date_arrivee = date_arrivee
        self.date_depart = date_depart
 
    def nb_jours(self):
        """renvoie, à l'aide de l'attribut days de la classe timedelta,
        un entier correspondant au nombre de jours passés au camping."""
        return (self.date_depart - self.date_arrivee).days
 
class Emplacement:
    def __init__(self, nom, tarif_journalier):
        self.nom = nom
        self.tarif_journalier = tarif_journalier

Expliquer pourquoi le terme self est utilisé comme paramètre des méthodes de ces classes.
Instancier une variable client01 de la classe Client représentant un client se nommant CODD Edgar habitant au 28 rue des Capucines à Lyon, France, ayant pour téléphone '0555555555'.

On veut une fonction renvoyant le montant dû par un client pour un emplacement et une durée de séjour donnés, sachant qu'au tarif journalier de location il faut ajouter une taxe de séjour de 2,20 € par jour et par personne. Exemple : pour 4 personnes, 12 jours, un emplacement à 30 € la journée, 30 * 12 + 4 * 2.20 * 12 vaut 465.6.

Compléter la ligne 5 de montant_a_regler :

def montant_a_regler(triplet):
    client, reservation, emplacement = triplet
    return ...

Chaque facture possède un numéro unique au format 'AAAA-MMM-xxx' : 'AAAA' une année entre 2018 et 2024, 'MMM' les trois premières lettres du mois en anglais, 'xxx' trois chiffres. Comportement attendu de facture_est_valide : facture_est_valide('2024-MAY-230') → True ; facture_est_valide('2012-MAY-230') → False ; facture_est_valide('2024-MAI-230') → False ; facture_est_valide('2024-JUN-23') → False.

calendrier = ['JAN', 'FEB', 'MAR', 'APR', 'MAY', 'JUN',
              'JUL', 'AUG', 'SEP', 'OCT', 'NOV', 'DEC']
 
def separe(chaine):
    return chaine.split('-')
 
def que_des_chiffres(chaine):
    for car in chaine:
        if not (car in "0123456789"):
            return False
    return True
 
def facture_est_valide(chaine):
    partie = separe(chaine)
    if not (len(partie) == 3):
        return False
    annee, mois, numero = partie[0], partie[1], partie[2]
    if not (que_des_chiffres(annee)):
        return False
    if not (len(annee) == 4) or not (2018 <= annee <= 2024):
        return False
    # Reste à faire vérifier les mois MMM
    ...
    # Reste à faire vérifier le numéro xxx
    ...
    return True

Expliquer pourquoi une erreur se produit à l'exécution de facture_est_valide.
Proposer une correction du code pour que cette erreur ne se produise plus.
Compléter le code afin de vérifier les mois et le numéro dans facture_est_valide.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Paradigmes de programmation

1. Quel paradigme privilégie la description de « ce que l'on veut obtenir » plutôt que de « comment l'obtenir », en évitant les effets de bord ?

2. Dans le paradigme orienté objet, qu'est-ce qui caractérise un objet ?

3. En reprenant pair_et_positif = lambda n: n % 2 == 0 and n >= 0 du cours, quel resultat renvoie list(filter(pair_et_positif, [-6, -3, 0, 5, 8, 9, 10])) ?

Mise au point et gestion des bugs

Le traceback Python

Lorsque l'interpréteur Python rencontre un problème pendant l'exécution, il lève une exception. Si elle n'est pas interceptée, le programme s'arrête et affiche un traceback : un message qui indique le type d'erreur, la ligne où elle a été détectée, et l'historique des appels de fonctions ayant mené à cette erreur (la pile d'appels). Le traceback se lit de bas en haut : la dernière ligne indique le type d'erreur, les lignes précédentes retracent le chemin qui y a mené.

Traceback (most recent call last):
  File "prog.py", line 10, in <module>
    f2()
  File "prog.py", line 7, in f2
    f1()
  File "prog.py", line 3, in f1
    a = a / (b + c)
ZeroDivisionError: division by zero

Ici, l'erreur ZeroDivisionError a été levée ligne 3, dans la fonction f1, elle-même appelée ligne 7 par f2, elle-même appelée ligne 10 par le programme principal.

Erreurs de syntaxe (SyntaxError, IndentationError) sont détectées avant l'exécution : l'interpréteur ne comprend pas le code. Elles sont en général faciles à localiser, mais attention : le traceback indique la ligne où l'erreur a été détectée, pas forcément la ligne où elle a été commise (une parenthèse non fermée n'est signalée qu'à la ligne suivante, par exemple).

Erreurs à l'exécution sont plus variées et nécessitent de comprendre le déroulement du programme : NameError (variable non définie ou mal orthographiée), IndexError (indice hors des bornes d'une liste), TypeError (opération entre types incompatibles), ZeroDivisionError (division par zéro), etc.

Les causes typiques de bugs

Problèmes liés au typage

Python est dynamiquement typé : le type d'une variable n'est vérifié qu'à l'exécution, pas avant. Une opération entre types incompatibles ne se révèle donc qu'au moment où elle est exécutée.

# BOGUE : on additionne un nombre et une chaine de caracteres
def prix_ttc(prix_ht):
    taux = "20"          # erreur : chaine au lieu d'un nombre
    return prix_ht * (1 + taux / 100)
 
print(prix_ttc(50))   # TypeError : unsupported operand type(s)

# CORRECTION : taux doit etre un nombre
def prix_ttc(prix_ht):
    taux = 20             # nombre, pas une chaine
    return prix_ht * (1 + taux / 100)
 
print(prix_ttc(50))   # 60.0

Effets de bord non désirés

Un effet de bord survient quand une fonction modifie une donnée qu'elle a reçue en argument, ce qui peut surprendre l'appelant. C'est fréquent avec les listes, qui sont mutables.

# BOGUE : la fonction modifie la liste passee en argument sans que ce soit voulu
def trier_et_afficher(notes):
    notes.sort()          # modifie la liste d'origine !
    print(notes)
 
mes_notes = [15, 8, 12]
trier_et_afficher(mes_notes)
print(mes_notes)   # [8, 12, 15] : la liste d'origine a change, effet de bord non voulu

# CORRECTION : travailler sur une copie si on ne veut pas modifier l'original
def trier_et_afficher(notes):
    notes_triees = sorted(notes)     # sorted() renvoie une NOUVELLE liste triee
    print(notes_triees)
 
mes_notes = [15, 8, 12]
trier_et_afficher(mes_notes)
print(mes_notes)   # [15, 8, 12] : inchangee

Débordement d'indices dans un tableau

Accéder à un indice qui n'existe pas dans une liste provoque une IndexError. Cette erreur est fréquente en cas d'erreur de borne (« off-by-one »), en particulier avec range ou dans une boucle qui va un cran trop loin.

# BOGUE : la boucle va jusqu'a len(notes) inclus, un indice de trop
def dernieres_notes(notes):
    resultat = []
    for i in range(1, len(notes) + 1):   # erreur : devrait s'arreter avant len(notes)
        resultat.append(notes[i])         # IndexError quand i == len(notes)
    return resultat

# CORRECTION : range(len(notes)) parcourt exactement les indices valides 0..len(notes)-1
def dernieres_notes(notes):
    resultat = []
    for i in range(len(notes)):
        resultat.append(notes[i])
    return resultat

Instruction conditionnelle non exhaustive

Oublier un cas dans une suite de if/elif (sans else final) peut laisser une variable non définie, ou faire passer silencieusement un cas non prévu.

# BOGUE : le cas "note negative ou faible" n'est traite dans aucune branche
def mention(note):
    if note >= 16:
        return "Tres bien"
    elif note >= 14:
        return "Bien"
    elif note >= 10:
        return "Passable"
    # aucun else : que renvoie mention(5) ? -> None, silencieusement !
 
print(mention(5))   # None : bug silencieux, aucune erreur levee

# CORRECTION : ajouter un cas par defaut (else) qui couvre tous les cas restants
def mention(note):
    if note >= 16:
        return "Tres bien"
    elif note >= 14:
        return "Bien"
    elif note >= 10:
        return "Passable"
    else:
        return "Insuffisant"
 
print(mention(5))   # "Insuffisant"

Choix des inégalités

Confondre < et <= (ou > et >=) est une source fréquente d'erreurs aux bornes d'un intervalle.

# BOGUE : les eleves ayant exactement 10 ne sont pas comptes comme admis
def est_admis(note):
    return note > 10     # 10 pile n'est pas admis, est-ce voulu ?
 
print(est_admis(10))   # False, potentiellement inattendu

# CORRECTION : utiliser >= si la note 10 doit compter comme admise
def est_admis(note):
    return note >= 10
 
print(est_admis(10))   # True

Comparaisons et calculs entre flottants

Les nombres à virgule flottante sont représentés en mémoire de façon approchée (norme IEEE 754). Comparer deux flottants avec == peut donc échouer même quand le résultat mathématique est exact.

>>> 0.1 + 0.2 == 0.3
False
>>> 0.1 + 0.2
0.30000000000000004

# BOGUE : comparaison exacte entre flottants, qui peut echouer a cause des arrondis
def a_converge(valeur):
    return valeur == 1.0

# CORRECTION : comparer a une tolerance pres avec math.isclose
import math
 
def a_converge(valeur):
    return math.isclose(valeur, 1.0, abs_tol=1e-9)

Mauvais nommage des variables

Un nom de variable ambigu, trop court, ou proche visuellement d'un autre symbole (l proche de 1, O proche de 0) rend le code difficile à relire et favorise les erreurs de frappe non détectées.

# BOGUE : noms non evocateurs, source de confusion et d'erreurs de frappe
def f(l, O):
    t = l * O
    return t

# CORRECTION : des noms clairs et evocateurs (voir le guide de style PEP 8)
def aire_rectangle(longueur, largeur):
    aire = longueur * largeur
    return aire

Les outils de mise au point

Lire le traceback en entier, en partant du bas (le type d'erreur) et en remontant la pile d'appels pour comprendre le contexte.
Le débogueur (debugger) permet de dérouler un programme pas à pas et d'inspecter le contenu de chaque variable à chaque étape ; le débogueur post-mortem permet d'inspecter l'état du programme à l'endroit où l'exception a été levée.
Des instructions assert et des jeux de tests permettent de vérifier automatiquement qu'une fonction se comporte comme attendu, y compris sur des cas limites (valeurs nulles, négatives, listes vides…).
Suivre un guide de style (comme la PEP 8 pour Python : noms explicites, indentation cohérente, une instruction par ligne) réduit fortement le risque d'introduire des bugs, en rendant le code plus facile à relire.

Le mot bug (« insecte » en anglais) doit son usage informatique à une anecdote de 1947 : Grace Hopper avait retrouvé un véritable insecte coincé dans un relais de l'ordinateur Mark II, provoquant des erreurs de calcul.

Exercice — Corriger un code buggé

Le code suivant contient trois bugs. Il doit renvoyer la moyenne des notes strictement positives d'une liste, ou None si la liste ne contient aucune note positive.

def moyenne_positives(notes):
    total = 0
    compteur = 0
    for i in range(1, len(notes)):
        if notes[i] > 0:
            total = total + notes[i]
            compteur = compteur + 1
    if compteur = 0:
        return None
    return total / compteur

Identifier les trois erreurs (une erreur de syntaxe, une erreur de borne dans la boucle, et leur conséquence sur le résultat).
Proposer une version corrigée.
Vérifier avec moyenne_positives([12, -3, 8, 0, 15]), qui doit renvoyer environ 11.67.

Exercice — Bug d'égalité entre flottants

On simule un compte bancaire qui perçoit des intérêts de 3 % chaque année, et on veut savoir en combien d'années le capital dépasse exactement 1000 €, en partant de 800 €.

def annees_pour_atteindre(objectif, capital):
    annees = 0
    while capital != objectif:
        capital = capital * 1.03
        annees = annees + 1
        if annees > 1000:      # garde-fou pour eviter une boucle infinie
            return None
    return annees
 
print(annees_pour_atteindre(1000, 800))

Pourquoi ce code ne s'arrête-t-il jamais avec capital == objectif (il renvoie None) ?
Corriger le programme pour qu'il s'arrête dès que capital dépasse ou atteint l'objectif.

Exercice — Bac NSI — Asie/Pacifique 2022 J2 (exercice 5)

Exercice tiré du bac NSI 2022 (Asie/Pacifique, Jour 2), sur la recherche et la correction de bugs (questions indépendantes).

1. somme(n) doit calculer $1+\frac12+\dots+\frac1n$ :

def somme(n):
    total = 0
    for i in range(n):
        total = total + 1/i
    return total

somme(10) déclenche ZeroDivisionError. Identifier et corriger.

def maxi(L):
    indice = 0
    maximum = 0
    while indice <= len(L):
        if L[indice] > maximum:
            maximum = L[indice]
        indice = indice + 1
    return maximum

a. maxi([2, 4, 9, 1]) déclenche une erreur : laquelle, et pourquoi ? b. Une fois corrigée, que renvoie maxi([-2, -7, -3]) ? Corriger pour obtenir le bon résultat.

def genere(n):
    L = []
    for i in range(1, n + 1):
        L.append('Joueur ' + i)
    return L

genere(3) déclenche TypeError: can only concatenate str (not "int") to str. Expliquer et corriger.

def suite(n):
    if n == 0:
        return 0
    else:
        return 3 + 2 * suite(n - 2)

a. Que renvoie suite(6) ? b. Que se passe-t-il pour suite(7) ?

x = 4
L = []
def modif(x, L):
    x = x + 1
    L.append(2 * x)
    return x, L
 
print(modif(x, L))
print(x, L)

Qu'affichent les deux print ?

Exercice — Épreuve pratique NSI — Sujet zéro 2026 n°1 : dates et calendrier iCalendar

Épreuve pratique d'une heure sur ordinateur. Le candidat dispose de l'énoncé et de fichiers de code et de données. Il agit en autonomie ; aux « appels professeur » indiqués dans le sujet, il présente son travail à l'examinateur ou le sollicite en cas de difficulté.

Ce sujet zéro est devenu le sujet n°03 de la banque nationale 2026 de l'épreuve pratique. Le texte est le même, à la présentation près ; la banque corrige seulement la coquille « phase lutérale » du sujet zéro, déjà rectifiée ici.

Cycle menstruel

Le cycle menstruel désigne l'ensemble des transformations physiologiques cycliques qui se répètent en moyenne tous les 28 jours chez une femme, de la puberté à la ménopause. Il est constitué de deux phases séparées par l'ovulation : avant l'ovulation, la phase folliculaire ; après, la phase lutéale. Par convention, le cycle commence le premier jour des règles, et l'ovulation se produit toujours 14 jours avant le début des menstruations.

On veut concevoir une application qui calcule et prédit les étapes du cycle à partir de dates fournies. On suppose un cycle régulier de 28 jours, découpé de façon simplifiée en quatre phases :

Phase	Numéro	Jours du cycle	Description
Règles	1	1 à 5	Écoulement menstruel
Phase folliculaire	2	6 à 13	Développement d'un follicule dans l'ovaire
Ovulation	3	14	Libération de l'ovocyte
Phase lutéale	4	15 à 28	Développement de la muqueuse utérine

Une date est représentée par le tuple d'entiers (jour, mois, annee), supposé toujours correctement formé et valide dans le calendrier grégorien : le 7 septembre 2025 s'écrit (7, 9, 2025).

Une année est bissextile (366 jours au lieu de 365) si elle est divisible par 4, à l'exception des années divisibles par 100, sauf si ce sont des multiples de 400. Ainsi 2024 est bissextile (divisible par 4 et pas par 100) ; 2100 ne l'est pas (divisible par 4 et par 100, mais pas par 400) ; 2000 l'est (divisible par 4, par 100 et par 400).

1. Écrire une fonction est_bissextile qui prend en paramètre un entier correspondant à une année et renvoie un booléen indiquant si elle est bissextile, en appliquant la règle ci-dessus.

Appel 1 — Appeler le professeur en cas de difficulté de compréhension du codage.

2. Écrire une fonction determiner_phase qui prend en paramètre un entier compris entre 1 et 28 inclus, le jour d'un cycle, et renvoie le numéro de la phase associée. À l'aide d'une assertion, on garantira que l'entier donné en argument est compris entre 1 et 28 inclus.

Appel 2 — Appeler le professeur pour lui présenter votre fonction et son fonctionnement, ou en cas de difficultés.

3. La fonction ajouter_jours, déjà fournie, prend en paramètres une date et un nombre de jours, et renvoie la date obtenue après ajout de ces jours. Compléter la fonction test_ajouter_jours en ajoutant au moins trois autres tests pertinents. Pour chaque test ajouté, justifier brièvement pourquoi ce cas est important à vérifier.

Pour inscrire les dates de début des règles d'une année dans un agenda en ligne, on veut créer un fichier au format iCalendar. Un calendrier a la structure suivante :

BEGIN:VCALENDAR
VERSION:2.0
PRODID: le nom du calendrier
une suite d'événements
END:VCALENDAR

Chaque événement d'une journée est décrit par une entrée de la forme :

BEGIN:VEVENT
DTSTART: la date JJ/MM/AAAA écrite sous la forme AAAAMMJJ
SUMMARY: la description de l'événement
END:VEVENT

Les nombres strictement inférieurs à 10 sont complétés par un 0, pour que la valeur de DTSTART ait toujours 8 chiffres : le 3 juillet 2026 s'écrit DTSTART:20260703.

4. La fonction calendrier_cycles, fournie, prend en paramètre la date du premier jour des dernières règles et renvoie, au format iCalendar sous forme de chaîne de caractères, la liste chronologique des dates de début de règles qui se présentent dans les 100 jours suivant cette date, date incluse. Observer avec la fonction test_calendrier_cycles que le calendrier renvoyé n'est pas dans un format valide. Identifier le problème dans calendrier_cycles, proposer une démarche de résolution et la mettre en œuvre.

Appel 3 — Appeler le professeur pour lui présenter votre démarche, ou en cas de difficultés.

Fichier fourni : `cycle_menstruel.py`

Le code nécessite la bibliothèque ics (pour la dernière question).

import calendar
 
#############################################################################
# Écrire le code de la fonction est_bissextile de la question 1             #
#############################################################################
 
 
#############################################################################
# Écrire le code de la fonction determiner_phase de la question 2           #
#############################################################################
 
 
#############################################################################
# Fonctions fournies pour la question 3                                     #
#############################################################################
def jours_dans_mois(annee, mois):
    """Renvoie le nombre de jours dans un mois donné d'une année donnée.
       Utilise le module calendar pour gérer les années bissextiles."""
    if mois == 2:  # février
        return 29 if calendar.isleap(annee) else 28
    elif mois in [1, 3, 5, 7, 8, 10, 12]:
        return 31
    else:
        return 30
 
def ajouter_jours(date, nb_jours):
    """Ajoute nb_jours à une date donnée et renvoie la nouvelle date.
       La date est représentée par un tuple (jour, mois, année)."""
    jour, mois, annee = date
    jour = jour + nb_jours
 
    # Ajustement du jour et du mois si dépassement
    while jour > jours_dans_mois(annee, mois):
        jour = jour - jours_dans_mois(annee, mois)
        mois = mois + 1
        if mois > 12:  # passage à l'année suivante
            mois = 1
            annee = annee + 1
 
    return (jour, mois, annee)
 
def test_ajouter_jours():
    assert ajouter_jours((7, 9, 2025), 3) == (10, 9, 2025)
 
#############################################################################
# Fonction fournie pour la question 4                                       #
#############################################################################
def calendrier_cycles(date_regles):
    """Renvoie une chaîne de caractère contenant au format iCalendar, l'ensemble
    des dates de début de règles qui se présentent dans les 100 jours suivants
    `date_regles`, date incluse.
 
    Hypothèse : cycle régulier de 28 jours. """
 
    cal_lignes = ['BEGIN:VCALENDAR', 'VERSION:2.0', 'PRODID:']
 
    date_courante = date_regles
    jours_ecoules = 0
 
    # On ajoute les dates tant que l'on ne dépasse pas 100 jours écoulés
    while jours_ecoules + 28 <= 100:
        jour, mois, annee = date_courante
        cal_lignes.append('BEGIN:VEVENT')
        cal_lignes.append('SUMMARY: Règles')
        date = str(annee)+str(mois)+str(jour)
        cal_lignes.append('DTSTART:'+date)
        cal_lignes.append('END:VEVENT')
        date_courante = ajouter_jours(date_courante, 28)
        jours_ecoules += 28
 
    cal_lignes.append('END:VCALENDAR')
 
    # La méthode join va renvoyer ici une unique chaîne contenant toutes les
    # chaînes de la liste séparées par des sauts de lignes.
    return '\n'.join(cal_lignes)
 
def test_calendrier_cycles():
    '''Crée un calendrier et le charge avec le module ics pour vérifier sa
    validité.
 
    Nécessite que le module ics soit présent sur la machine (pip install ics).
    '''
    from ics import Calendar
    c = calendrier_cycles( (12,3,2026) )
    print(c)
    cal = Calendar(c)
    print(cal.events)

Exercice — Épreuve pratique NSI — Sujet zéro 2026 n°2 : écarts de salaires et k plus proches voisins

Ce sujet zéro est devenu le sujet n°02 de la banque nationale 2026 de l'épreuve pratique. Le texte est le même, à la présentation près ; la banque harmonise en outre le nom de la fonction (calcul_ecart_sexe partout) et la clé des hommes ('M' partout), les deux incohérences signalées dans le corrigé.

Analyse d'écarts de salaires

Des écarts de salaires subsistent entre les femmes et les hommes, même à poste équivalent : en France, l'écart de salaire moyen est encore d'environ 15 % en 2023 selon l'INSEE.

Pour observer cet écart et ses conséquences, on dispose de jeux de données représentant les employés d'une entreprise. Chaque jeu de données est une liste de dictionnaires ; chaque dictionnaire représente un employé, avec les champs suivants :

'experience' (int, en années, l'expérience professionnelle) ;
'etudes' (int, en années, le nombre d'années d'études après le baccalauréat) ;
'sexe' (str, 'F' ou 'M') ;
'salaire' (int, en euros).

Deux jeux de données sont fournis : un jeu de test dans le fichier donnees.py, reproduit ci-dessous, et un jeu plus complet de 2000 employés dans le fichier donnees_completes.py.

employes = [
    {'experience': 5, 'etudes': 3, 'sexe': 'F', 'salaire': 2400},
    {'experience': 3, 'etudes': 3, 'sexe': 'M', 'salaire': 2550},
    {'experience': 5, 'etudes': 5, 'sexe': 'F', 'salaire': 2500},
    {'experience': 3, 'etudes': 5, 'sexe': 'M', 'salaire': 2800},
    {'experience': 2, 'etudes': 5, 'sexe': 'F', 'salaire': 2300},
    {'experience': 2, 'etudes': 3, 'sexe': 'M', 'salaire': 2700}
]

Le fichier analyse.py (reproduit plus bas) contient des éléments d'analyse de ces données, à compléter et à améliorer dans les questions suivantes.

1. Écrire le code de la fonction salaire_moyen_condition, qui prend en paramètres un tableau d'employés au format ci-dessus, le nom d'un des trois champs 'experience', 'etudes' ou 'sexe', et une valeur, et qui renvoie un flottant : le salaire moyen des employés dont le champ a la valeur fournie. La fonction renvoie None si aucun employé n'a cette valeur pour ce champ. Ainsi, salaire_moyen_condition(employes, 'sexe', 'F') renvoie le salaire moyen des femmes. Une fonction de test sur le jeu de test est fournie. Déterminer le salaire moyen des femmes et celui des hommes pour le jeu de données complet.

Appel 1 — Appeler le professeur pour lui présenter vos réponses et votre fonction, ou en cas de difficulté de compréhension de la représentation.

2. Écrire une fonction effectif_par_sexe qui prend en paramètre un tableau non vide d'employés et renvoie un dictionnaire associant à chaque sexe l'effectif correspondant. Avec le tableau employes précédent :

>>> effectif_par_sexe(employes)
{'F': 3, 'M': 3}

Appel 2 — Appeler le professeur pour lui présenter votre fonction et son fonctionnement, ou en cas de difficultés.

On définit l'écart de salaire moyen en pourcentage par :

\text{écart} = \frac{\text{salaire moyen des hommes} - \text{salaire moyen des femmes}}{\text{salaire moyen des hommes}} \times 100

Une fonction de calcul de cet écart est écrite dans le fichier analyse.py.

3. Expliquer pourquoi le code de cette fonction est incorrect, et proposer quelques tests simples, sous forme d'assertions, qui mettent ces problèmes en évidence :

vérifier que le résultat est None quand un seul sexe est présent ;
vérifier qu'un écart de salaires exprimé en pourcentage est toujours compris entre 0 et 100.

Proposer une version corrigée de la fonction, qui valide ces tests et renvoie le bon écart. En déduire l'écart de salaire moyen dans les données complètes.

Appel 3 — Appeler le professeur pour lui présenter vos tests et la correction proposée.

4. Pour proposer un salaire d'embauche à un nouvel employé, le service informatique utilise l'algorithme des k plus proches voisins : la fonction salaire_par_proximite renvoie la moyenne des salaires des trois employés aux caractéristiques les plus proches. Tester et comparer les salaires proposés aux deux futurs employés suivants :

{'experience': 3, 'etudes': 3, 'sexe': 'F'}
{'experience': 3, 'etudes': 3, 'sexe': 'M'}

Identifier dans le programme la source de l'écart entre les deux propositions, et la corriger.

Appel 4 — Appeler le professeur pour lui présenter vos tests, votre analyse des écarts et la correction proposée.

Fichier fourni : `analyse.py`

import donnees
import donnees_completes
from math import sqrt
 
def salaire_moyen_condition(employes, champ, valeur):
    '''Renvoie le salaire moyen des employes ayant val comme valeur associée
    au champ donné en argument.
    Si le nombre d'employés considéré est nul, cette fonction renvoie None'''
    pass # à implémenter
 
def test_salaire_moyen_condition():
    e = donnees.employes
    assert salaire_moyen_condition([], 'sexe', 'F') == None
    assert salaire_moyen_condition(e, 'sexe', 'F') == 2400.0
    assert salaire_moyen_condition(e, 'etudes', 3) == 2550.0
    assert salaire_moyen_condition(e, 'etudes', 12) == None
 
def effectif_par_sexe(employes):
    '''Renvoie un dictionnaire ayant deux clés 'F' et 'M'
    associée respectivement au nombre d'employées femmes et au
    nombre d'employés hommes dans les données en arguments.'''
    pass # à implémenter
 
def test_effectif_par_sexe():
    e = donnees.employes
    assert effectif_par_sexe(e) == { 'F' : 3, 'M' : 3 }
 
def calcul_ecart_sexe(employes):
    '''Renvoie l'écart de salaire en pourcentage pour les femmes
    par rapport aux hommes'''
    moy_h = salaire_moyen_condition(employes, 'sexe', 'M')
    moy_f = salaire_moyen_condition('employes', 'sexe', 'F')
    return moy_h - moy_f
 
# Attribution d'un premier salaire après embauche par les k plus proches voisins
 
def sexe_vers_entier(e):
    if e['sexe'] == 'F':
        return 1
    else:
        return -1
 
def distance(e1, e2):
    '''Renvoie la mesure de distance entre deux personnes.'''
    s = 0
    s = s + (sexe_vers_entier(e1) - sexe_vers_entier(e2))**2
    s = s + (e1['experience'] - e2['experience'])**2
    s = s + (e1['etudes'] - e2['etudes'])**2
    return sqrt(s)
 
def k_plus_proches(k, employes, e):
    '''Renvoie les k employes les plus proches de e par la
    distance définie au dessus.'''
    e_d = [(distance(e, employes[i]), i) for i in range(len(employes))]
    e_d.sort() # va trier en premier sur la distance
    voisins = []
    for i in range(k):
        voisins.append(employes[e_d[i][1]])
    return voisins
 
def salaire_moyen(employes):
    '''Renvoie le salaire moyen pour une liste d'employes'''
    if len(employes) == 0:
        return None
    s = sum(e['salaire'] for e in employes)
    return s/len(employes)
 
def salaire_par_proximite(employes, e):
    '''Prend en entrée une liste d'employés et un dictionnaire comportant
    les champs experience, etudes et sexe et renvoie le salaire le plus
    proche en moyennant les 3 plus proches voisins'''
    voisins = k_plus_proches(3, employes, e)
    return salaire_moyen(voisins)

Le fichier donnees_completes.py définit de la même façon une liste employes de 2000 dictionnaires (984 femmes et 1016 hommes).

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI — Sujet zéro 2026 n°3 : codage RLE d'images

Ce sujet zéro est devenu le sujet n°01 de la banque nationale 2026 de l'épreuve pratique. Le texte est le même, à la présentation près.

Codage RLE d'images

On considère des images en niveaux de gris : chaque pixel est décrit par une valeur entre 0 (noir) et 255 (blanc), qui représente l'intensité du gris. Une image est vue comme la liste des valeurs de ses pixels, ligne par ligne. Par exemple, une petite image en niveaux de gris peut, une fois « aplatie », devenir la liste [0, 128, 128, 255, 64, 255, 128, 128, 255, 255, 128, 128, 0, 0, 64, 255, 0, 0, 0, 0], à partir de laquelle on retrouve l'image si l'on connaît sa largeur.

Les images manipulées sont des dessins ou des schémas présentant de grandes zones d'un même gris. On veut les représenter efficacement en tirant parti de cette particularité : les aplats font apparaître des valeurs qui se répètent. On remplace donc chaque suite de valeurs identiques par un couple (compte, valeur), qui indique le nombre de répétitions et la valeur répétée. La liste de couples est elle-même aplatie en une liste de longueur paire [compte1, valeur1, compte2, valeur2, ...]. Cette nouvelle liste est le codage RLE de l'image (de l'anglais run-length encoding : une suite de valeurs identiques s'appelle un run).

Exemple. La liste [4, 4, 4, 0, 5, 5] présente trois fois de suite la valeur 4, soit le couple (3, 4), une fois la valeur 0, soit (1, 0), et deux fois la valeur 5, soit (2, 5). Son codage RLE est [3, 4, 1, 0, 2, 5]. Ici, les deux listes ont la même longueur ; mais la liste [0, 0, 0, 0, 0] aurait pour codage [5, 0], plus court.

1. La liste obtenue par codage RLE est-elle forcément de longueur inférieure ou égale à celle de la liste de départ ?

Appel 1 — Appeler le professeur en cas de difficulté de compréhension du codage.

2. En étudiant la fonction codage_rle, qui réalise le codage, écrire le corps de la fonction decodage_rle, qui réalise le décodage d'une liste. Des tests sont fournis dans la fonction test_codage ; on pourra les compléter.

Appel 2 — Appeler le professeur pour lui présenter votre fonction et son fonctionnement, ou en cas de difficultés.

3. Pour tester le codage sur une image, on peut utiliser la fonction fournie encoder_decoder_image, qui code puis décode une image et enregistre le résultat dans un nouveau fichier. Utiliser cette fonction sur les images bac_nsi_32.png et bac_nsi_256.png, et observer la différence de comportement.

4. Le problème précédent vient de ce que, sur de grandes images, plus de 255 pixels consécutifs peuvent avoir la même couleur. Proposer une démarche de résolution de ce problème, qui modifie les fonctions de codage et de décodage, puis l'implémenter.

Appel 3 — Appeler le professeur pour lui présenter votre démarche, ou en cas de difficultés.

Fichier fourni : `rle.py`

Le dossier contient aussi les images bac_nsi_32.png (32 × 32 pixels) et bac_nsi_256.png (256 × 256 pixels). Le code nécessite la bibliothèque pillow.

from PIL import Image
 
def codage_rle(liste_octets):
    '''Renvoie une liste d'octets obtenue par compression RLE'''
    liste_rle = []
    i = 0
    while i < len(liste_octets):
        c = liste_octets[i]
        k = 1
        while i+k < len(liste_octets) and liste_octets[i+k] == c:
            k += 1
        liste_rle.append(k)
        liste_rle.append(c)
        i += k
    return liste_rle
 
def decodage_rle(liste_rle):
    '''Renvoie la liste d'octets obtenue à partir de la liste liste_rle obtenue
    par compression RLE'''
    # A VOUS D'ÉCRIRE LE CODE LA FONCTION
 
def test_codage():
    assert codage_rle([255, 255, 0, 255, 255, 255]) == [2, 255, 1, 0, 3, 255]
    assert decodage_rle([2, 255, 1, 0, 3, 255]) == [255, 255, 0, 255, 255, 255]
 
#############################################################################
# Il n'est pas nécessaire de comprendre le code de ces 4 fonctions, mais il #
# sera nécessaire de les utiliser dans la suite à partir de l'exemple.      #
#############################################################################
 
def enregistrer_octets(nom_fichier, liste_octets):
    '''Enregistre une liste de valeurs numériques entre 0 et 255 dans un
    le fichier nom_fichier. Si une valeur est plus grande que 255 on considère
    que c'est 255. De même pour les valeur plus petite que 0.'''
    with open(nom_fichier, 'wb') as fichier:
        fichier.write(bytes([ max(0, min(255, b)) for b in liste_octets]))
 
def charger_octets(nom_fichier):
    '''Renvoie la liste des octets présents dans le fichier nom_fichier'''
    with open(nom_fichier, 'rb') as fichier:
        liste_octets = list(fichier.read())
        return liste_octets
 
def enregistrer_image(nom_image, largeur, liste_niveaux):
    '''Enregistre un fichier image nom_image de la largeur donnée et dont les
    valeurs de niveaux de gris des pixels sont celles de la liste
    liste_niveaux'''
    hauteur = len(liste_niveaux) // largeur
    im = Image.frombytes('L', (largeur, hauteur), bytes(liste_niveaux))
    im.save(nom_image)
 
def charger_image(nom_image):
    '''Étant donné une image nom_image, renvoie un couple (largeur, liste_niveaux) où
    largeur est la largeur de l'image et liste_niveaux est la liste des valeurs de niveaux
    de gris de l'image ligne par ligne'''
 
    image = Image.open(nom_image).convert('L')
    return (image.width, list(image.tobytes()))
 
#############################################################################
# Fonction nécessaire pour les tests de la question 3                       #
#############################################################################
 
def encoder_decoder_image(nom_image):
    '''Fonction de test permettant d'encoder puis décoder une image avec un
    codage RLE. Le fichier rle est nommé nom_image.rle et le fichier decodé
    est nom_image.dec.png'''
    w, l = charger_image(nom_image)
    enregistrer_octets(nom_image+'.rle', codage_rle(l))
    l = charger_octets(nom_image+'.rle')
    enregistrer_image(nom_image+'.dec.png', w, decodage_rle(l))

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Exercice — Épreuve pratique NSI 2026 — Sujet 14 : simulation de l'évacuation d'une pièce

Banque nationale de sujets 2026 de l'épreuve pratique, sujet n°14 (situation d'évaluation d'une heure).

Simulation de l'évacuation d'une pièce

Lors de la construction d'un bâtiment, d'un lieu culturel ou sportif, le respect des normes de sécurité amène à se poser la question du nombre judicieux de sorties, de leurs emplacements et du temps nécessaire pour l'évacuation totale des occupants.

Ce sujet propose de finaliser une application permettant de simuler l'évacuation d'une pièce rectangulaire. Cette pièce sera une instance de la classe Piece dont le code est dans le fichier simulation_evacuation.py du dossier fourni. Le constructeur de cette classe permet de définir la profondeur et la largeur de la pièce.

La méthode ajouter_occupants(self, i, j, nb) permet d'ajouter jusqu'à nb occupants dans la case située ligne i et colonne j, sachant que le nombre d'occupants d'une case est obligatoirement compris entre 0 et 5.

La méthode ajouter_sortie(self, direction, position) permet d'ajouter une sortie à la pièce bien que, pour l'instant, seules les directions "N" (pour le nord) et "O" (pour l'ouest) soient prises en compte. Lors de l'affichage d'une pièce, les sorties sont représentées par la lettre P.

Voici un exemple d'utilisation de cette classe. Le programme

p1 = Piece(5, 7)
p1.ajouter_occupants(2, 0, 4)
p1.ajouter_occupants(3, 4, 1)
p1.ajouter_occupants(0, 5, 2)
p1.ajouter_sortie("N", 5)
print(p1)

produit l'affichage console :

                 P
 [0, 0, 0, 0, 0, 2, 0]
 [0, 0, 0, 0, 0, 0, 0]
 [4, 0, 0, 0, 0, 0, 0]
 [0, 0, 0, 0, 1, 0, 0]
 [0, 0, 0, 0, 0, 0, 0]

La méthode alerter permet de simuler une alerte : chaque occupant essaie de se rapprocher d'une sortie en se déplaçant d'une case (vers le nord, le sud, l'est ou l'ouest) ; chaque sortie ne laisse passer qu'une seule personne par alerte. Il n'est pas nécessaire de comprendre, ni de modifier, le code de cette méthode. Voici, par exemple, trois alertes successives sur la pièce précédente :

                 P                       P                       P
 [0, 0, 0, 0, 0, 1, 0]   [0, 0, 0, 0, 0, 0, 0]   [0, 0, 0, 0, 0, 0, 0]
 [0, 0, 0, 0, 0, 0, 0]   [0, 4, 0, 0, 0, 0, 0]   [0, 4, 0, 0, 0, 1, 0]
 [0, 4, 0, 0, 0, 0, 0]   [0, 0, 0, 0, 0, 1, 0]   [0, 0, 0, 0, 0, 0, 0]
 [0, 0, 0, 0, 0, 1, 0]   [0, 0, 0, 0, 0, 0, 0]   [0, 0, 0, 0, 0, 0, 0]
 [0, 0, 0, 0, 0, 0, 0]   [0, 0, 0, 0, 0, 0, 0]   [0, 0, 0, 0, 0, 0, 0]

Question 1. Écrire le corps de la méthode nb_occupants_restants de la classe Piece. Comme son nom l'indique, cette méthode doit renvoyer le nombre d'occupants restants dans la pièce. La fonction test_nb_occupants_restants présente dans le fichier simulation_evacuation.py vous permettra d'effectuer une première série de tests.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 2. Écrire le corps de la fonction evacuation afin qu'elle simule l'évacuation complète de la pièce et renvoie le nombre de tours nécessaire. On pourra, dans cette fonction, faire appel à la méthode alerter qui simule un tour et renvoie True si des déplacements ont pu avoir lieu, False sinon. En complément de la pièce à évacuer, la fonction evacuation a un paramètre silencieux dont la valeur par défaut est True. Si ce paramètre vaut False, l'état de la pièce doit être affiché à chaque tour dans la console. La fonction test_evacuation présente dans le fichier simulation_evacuation.py vous permettra d'effectuer une série de tests.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Question 3. Modifier la méthode ajouter_sortie(self, direction, position) afin qu'il soit aussi possible d'ajouter une sortie dans les directions qui ne sont pour l'instant pas prises en compte : "S" (pour le sud) et "E" (pour l'est). Le paramètre position désigne l'indice de la case sur le côté correspondant.

La fonction test_ajouter_sortie vous permettra d'effectuer une première série de tests. Vous vérifierez également qu'il est maintenant possible d'ajouter des sorties dans les quatre directions via l'interface homme-machine (IHM), sans modifier le code de celle-ci. Lorsqu'une pièce a été créée dans l'IHM, un clic en périphérie de cette pièce déclenche automatiquement un appel à la méthode ajouter_sortie et fait apparaître la porte ajoutée. Cependant, une seule porte sera utilisée lors des alertes tant que la question suivante n'aura pas été traitée.

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

On s'aperçoit que, lorsqu'une pièce possède plusieurs sorties, seule la première est utilisée par les occupants. Le problème vient de la méthode choix_sortie(self, i, j) qui renvoie la sortie à utiliser pour une personne positionnée sur la ligne i et la colonne j.

Question 4. Identifier l'erreur logique et la variable non définie dans le code de cette méthode, puis effectuer les corrections nécessaires afin qu'elle renvoie la sortie la plus proche. La fonction test_choix_sortie vous permettra d'effectuer une première série de tests. Vous poursuivrez vos tests avec l'IHM (sans la modifier).

Appel professeur — Appeler le professeur pour lui présenter votre réponse ou en cas de difficulté.

Fichiers fournis

Le dossier comporte une version PDF de l'énoncé, le code source à compléter et corriger simulation_evacuation.py et un programme IHM_evacuation.py permettant d'ouvrir une IHM qui facilitera les tests, à utiliser sans modification. Les bibliothèques random, copy et tkinter doivent être disponibles.

simulation_evacuation.py

from random import randint, shuffle
from copy import deepcopy
 
 
class Piece:
 
    def __init__(self, profondeur, largeur):
        self.grille = [[0 for _ in range(largeur)] for _ in range(profondeur)]
        self.i_max = profondeur-1
        self.j_max = largeur-1
        self.capacite = profondeur * largeur * 5
        self.sorties = []
 
    def ajouter_occupants(self, i, j, nb):
        ''' permet d'ajouter jusqu'à nb occupants dans la case située ligne i et colonne j.
            Le nombre d'occupants ajoutés est limité par la capacité d'accueil de la case (5).
            Cette méthode renvoie le nombre d'occupants effectivement ajoutés.
        '''
        nb_add = min(nb, 5 - self.grille[i][j])
        if nb_add > 0:
            self.grille[i][j] = self.grille[i][j] + nb_add
        return nb_add
 
    def nb_occupants_restants(self):
        ''' renvoie le nombre d'occupants restants dans la pièce.
            A FAIRE (QUESTION 1)
        '''
        pass
 
    def ajouter_sortie(self, direction, position):
        ''' permet d'ajouter des sorties à la pièce.
            A COMPLETER (QUESTION 3) (Pour l'instant, on n'utilise que deux directions !)
        '''
        if direction == "N":
            self.sorties.append((0, position))
        elif direction == "O":
            self.sorties.append((position, 0))
 
    def choix_sortie(self, i, j):
        ''' renvoie la sortie à utiliser pour une personne positionnée sur la ligne i et la colonne j.
            A CORRIGER (QUESTION 4) (Pour l'instant, seule la 1ère sortie est utilisée !)
        '''
        assert len(self.sorties) > 0, "Aucune sortie"
        choix = self.sorties[0]
        distance = abs(i - choix[0]) + abs(j - choix[1])
        for k in range(1, len(self.sorties)):
            autre_sortie = self.sorties[k]
            if k < 0:
                choix = autre_sortie
                distance = d2
        return choix
 
    def deplacer(self, i, j, nb, direction, silencieux=True):
        ''' effectue le déplacement dans la direction demandée d'au maximum
            nb occupants actuellement en ligne i et colonne j.
            Le déplacement est limité par la capacité d'accueil (5) de la case visée.
            Cette fonction renvoie le nombre d'occupants déplacés.
            IL N'EST PAS NECESSAIRE DE COMPRENDRE LE CODE DE CETTE METHODE.
        '''
        d = {"N": (-1, 0), "S": (1, 0), "E": (0, 1), "O": (0, -1)}
        nv_i, nv_j = i + d[direction][0], j + d[direction][1]
        nb_dep = min(nb, 5 - self.grille[nv_i][nv_j], self.grille[i][j])
        if nb_dep > 0:
            if not silencieux:
                print("déplacement de ", nb_dep,
                      " occupant(s) (", i, ",", j, ") vers ", direction)
            self.grille[i][j] = self.grille[i][j] - nb_dep
            self.grille[nv_i][nv_j] = self.grille[nv_i][nv_j] + nb_dep
        return nb_dep
 
    def alerter(self, silencieux=True):
        ''' permet de simuler une alerte : chaque occupant se déplace d'une case
            vers la sortie qui lui est conseillée par la méthode choix_sortie.
            Cette méthode renvoie True si des déplacements ont pu avoir lieu, False sinon.
            IL N'EST PAS NECESSAIRE DE COMPRENDRE LE CODE DE CETTE METHODE.
        '''
        old_grille = deepcopy(self.grille)
        modif = False
        for i in range(len(self.grille)):
            for j in range(len(self.grille[i])):
                if old_grille[i][j] > 0:
                    sortie_i, sortie_j = self.choix_sortie(i, j)
                    dx, dy = sortie_j-j, sortie_i-i
                    if dx == 0 and dy == 0:
                        if not silencieux:
                            print("évacuation d'un occupant (", i, ",", j, ")")
                        self.grille[i][j] = self.grille[i][j] - 1
                        nb_dep = 1
                    else:
                        mvt_possibles = []
                        if dx > 0:
                            mvt_possibles.append("E")
                        elif dx < 0 and j > 0:
                            mvt_possibles.append("O")
                        if dy > 0:
                            mvt_possibles.append("S")
                        elif dy < 0 and i > 0:
                            mvt_possibles.append("N")
                        shuffle(mvt_possibles)
                        nb_dep = self.deplacer(
                            i, j, old_grille[i][j], mvt_possibles[0], silencieux)
                        if nb_dep == 0 and len(mvt_possibles) > 1:
                            nb_dep = self.deplacer(
                                i, j, old_grille[i][j], mvt_possibles[1], silencieux)
                    if nb_dep > 0:
                        modif = True
        return modif
 
    def __str__(self):
        ''' Cette méthode permet de convertir une pièce en chaîne de caractères.
            Ainsi, si p1 est une pièce, l'instruction print(p1) permettra d'afficher l'état actuel de la pièce dans la console.
            IL N'EST PAS NECESSAIRE DE COMPRENDRE LE CODE DE CETTE METHODE.
        '''
        s = "  "
        for j in range(self.j_max+1):
            if (0, j) in self.sorties:
                s = s + "P  "
            else:
                s = s + "   "
        s = s + "\n"
        for i in range(len(self.grille)):
            if (i, 0) in self.sorties:
                s = s + "P"
            else:
                s = s + " "
            s = s + str(self.grille[i])
            if i != 0 and i != self.i_max and (i, self.j_max) in self.sorties:
                s = s + "P\n"
            else:
                s = s + "\n"
        s = s + "  "
        for j in range(self.j_max+1):
            if (self.i_max, j) in self.sorties:
                s = s + "P  "
            else:
                s = s + "   "
        return s + "\n"
 
 
def evacuation(p, silencieux=True):
    ''' simule l'évacuation de la pièce et renvoie le nombre de tours nécessaire.
        A chaque tour, chacun des occupants se déplace, si possible, d'une case
        vers la sortie la plus proche. Si le paramètre silencieux vaut false,
        l'état de la pièce à chaque tour est affiché dans la console.
        A FAIRE EN QUESTION 2
    '''
    pass
 
 
def test_nb_occupants_restants():
    ''' Jeux de tests proposés pour la méthode nb_occupants_restants de la classe Piece.
    '''
    p1 = Piece(5, 7)
    p1.ajouter_sortie("N", 5)
    reussite = True
    if p1.nb_occupants_restants() != 0:
        print("La méthode nb_restants devrait renvoyer 0 quand la pièce est vide.")
        reussite = False
    n1 = randint(1, 5)
    cases_occupees = {(0, 3): 4, (0, 1): 2, (3, 4): 3, (4, 0): n1, (4, 3): 2}
    for c in cases_occupees:
        p1.ajouter_occupants(c[0], c[1], cases_occupees[c])
    if p1.nb_occupants_restants() != 11 + n1:
        print("La méthode nb_restants renvoie",
              p1.nb_occupants_restants(), " au lieu", 11 + n1)
        reussite = False
    if reussite == True:
        print("Pas de problème détecté pour l'instant avec nb_occupants_restants. Il faudra vérifier que l'IHM affiche maintenant le bon nombre d'occupants restants.")
 
 
def test_evacuation(silencieux: bool = True):
    ''' Jeux de tests proposés pour la fonction evacuation.
    '''
    p1 = Piece(5, 7)
    p1.ajouter_sortie("N", 5)
    situations = [{"nom": "essai1", "cases_occupees": {(0, 3): 3, (1, 1): 1, (3, 2): 5}, "temps_attendu": 11},
                  {"nom": "essai2", "cases_occupees": {
                      (0, 3): 4, (0, 1): 2, (3, 4): 3, (4, 0): 1, (4, 3): 2}, "temps_attendu": 14},
                  {"nom": "essai3", "cases_occupees": {(0, 3): 1, (0, 1): 2, (3, 4): 1, (4, 0): 3, (4, 3): 5}, "temps_attendu": 15}]
    verif = True
    for s in situations:
        for c, nb in s["cases_occupees"].items():
            p1.ajouter_occupants(c[0], c[1], nb)
        nbT = evacuation(p1, silencieux)
        if nbT != s["temps_attendu"]:
            print("La fonction evacuation renvoie ", nbT,
                  " au lieu de ", s["temps_attendu"], " pour ", s["nom"])
            verif = False
    if verif:
        print("Pas de problème détecté pour l'instant avec l'évacuation. Il faudra vérifier avec l'IHM que les évacuations n'échouent plus.")
 
 
def test_ajouter_sortie():
    ''' Jeux de tests proposés pour tester les modifications apportées à la méthode ajouter_sortie de la classe Piece.
    '''
    p1 = Piece(5, 7)
    p1.ajouter_sortie("N", 5)
    n1 = randint(1, 5)
    p1.ajouter_sortie("S", n1)
    n2 = randint(1, 5)
    p1.ajouter_sortie("E", n2)
    p1.ajouter_sortie("O", 1)
    if p1.sorties == [(0, 5), (4, n1), (n2, 6), (1, 0)]:
        print("Pas de problème détecté avec le jeu de tests pour la méthode ajouter_sortie. Il faudra vérifier que l'ajout de sortie à l'est ou au sud de la pièce est maintenant possible via l'IHM.")
    else:
        print("L'ajout des sorties ne fonctionne pas correctement.")
 
 
def test_choix_sortie():
    ''' Jeux de tests proposés pour tester les modifications apportées à la méthode choix_sortie de la classe Piece.
    '''
    p1 = Piece(5, 7)
    # Afin de pouvoir tester choix_sortie indépendamment de ajouter_sortie,
    # on effectue ici une modification directe de l'attribut sorties de p1
    p1.sorties = [(0, 5), (4, 1), (3, 6), (1, 0)]
    try:
        assert p1.choix_sortie(0, 3) == (0, 5)
        assert p1.choix_sortie(0, 1) == (1, 0)
        assert p1.choix_sortie(1, 2) == (1, 0)
        assert p1.choix_sortie(3, 4) == (3, 6)
        assert p1.choix_sortie(4, 0) == (4, 1)
        assert p1.choix_sortie(4, 3) == (4, 1)
        print("Pas de problème détecté avec le jeu de tests pour la méthode choix_sortie. Il faudra vérifier avec l'IHM que les occupants n'utilisent plus uniquement la première sortie lors des alertes.")
    except:
        print("La méthode choix_sortie ne renvoie pas la réponse attendue sur au moins l'un des tests.")
 
 
if __name__ == "__main__":
    test_nb_occupants_restants()
    test_evacuation(False)
    test_ajouter_sortie()
    test_choix_sortie()

IHM_evacuation.py

from simulation_evacuation import Piece, evacuation
from tkinter import *
from random import randint
 
################################################################################
# Il n'est pas nécessaire de comprendre (ni modifier) le code de ce programme. #
# Son execution ouvre une interface graphique qui facilitera vos tests.        #
################################################################################
 
 
def creation_piece():
    global choix_largeur, choix_profondeur, choix_nboccupants, piece_test
    global dessin, dernier_affichage, nb_tour_evac
    piece_test = Piece(choix_profondeur.get(), choix_largeur.get())
    n = min(choix_nboccupants.get(), piece_test.capacite)
    while n > 0:
        i = randint(0, piece_test.i_max)
        j = randint(0, piece_test.j_max)
        nb = piece_test.ajouter_occupants(i, j, randint(1, min(5, n)))
        n = n - nb
    dernier_affichage = [[[None, None] for _ in range(
        piece_test.j_max + 1)] for _ in range(piece_test.i_max + 1)]
    dessin.delete(ALL)
    nb_tour_evac.configure(text="")
 
 
def affichage_grille():
    global piece_test, dessin, mode_daltonien, dernier_affichage, nb_occ_restants
    if piece_test is not None:
        couleurs = ["white", "blue", "green", "yellow", "orange", "red"]
        for (lg, cl) in piece_test.sorties:
            if lg == 0:
                dessin.create_text(15*cl+22, 7, text="P")
            elif cl == 0:
                dessin.create_text(7, 15*lg+22, text="P")
            elif lg == piece_test.i_max:
                dessin.create_text(15*cl+22, 15*lg+37, text="P")
            else:
                dessin.create_text(15*cl+37, 15*lg+22, text="P")
        for lg in range(piece_test.i_max + 1):
            for cl in range(piece_test.j_max + 1):
                nb = piece_test.grille[lg][cl]
                case = dernier_affichage[lg][cl]
                if case[0] is None:
                    case[0] = dessin.create_rectangle(
                        15*cl+15, 15*lg+15, 15*cl+30, 15*lg+30, fill="white")
                if case[1] is None:
                    case[1] = dessin.create_text(15*cl+22, 15*lg+22, text="")
                if dessin.itemcget(case[0], "fill") != couleurs[nb]:
                    dessin.itemconfig(case[0], fill=couleurs[nb])
                if mode_daltonien.get() == "oui" and dessin.itemcget(case[1], "text") != str(nb):
                    dessin.itemconfig(case[1], text=str(nb))
                if mode_daltonien.get() == "non" and dessin.itemcget(case[1], "text") != "":
                    dessin.itemconfig(case[1], text="")
        nb_occ_restants.configure(text=str(piece_test.nb_occupants_restants()))
    dessin.after(100, affichage_grille)
 
 
def clic_gauche(event):
    global piece_test
    if piece_test is not None:
        cl, lg = event.x // 15, event.y // 15
        if lg == 0:
            # ajout d'une sortie au nord
            piece_test.ajouter_sortie("N", min(cl-1, piece_test.j_max))
        elif cl == 0:
            # ajout d'une sortie à l'ouest
            piece_test.ajouter_sortie("O", min(lg-1, piece_test.i_max))
        elif lg > piece_test.i_max:
            # ajout d'une sortie au sud
            piece_test.ajouter_sortie("S", min(cl-1, piece_test.j_max))
        elif cl > piece_test.j_max:
            # ajout d'une sortie à l'est
            piece_test.ajouter_sortie("E", min(lg-1, piece_test.i_max))
        else:
            # ajout d'occupants
            piece_test.ajouter_occupants(lg-1, cl-1, 5)
 
 
def alerter_occupants():
    global piece_test
    if piece_test is not None and piece_test.sorties != []:
        nb_tour_evac.configure(text="")
        piece_test.alerter()
 
 
def evacuer_occupants():
    global piece_test, nb_tour_evac
    if piece_test is not None and piece_test.sorties != []:
        nbT = evacuation(piece_test)
        if piece_test.nb_occupants_restants() == 0:
            nb_tour_evac.configure(
                text="Evacuation effectuée en " + str(nbT) + " tours.")
        else:
            nb_tour_evac.configure(text="Echec de l'évacuation.")
 
 
if __name__ == "__main__":
    global fen, choix_largeur, choix_profondeur, choix_nboccupants
    global piece_test, dessin, mode_daltonien, nb_occ_restants, nb_tour_evac
    piece_test = None
    # création de la fenêtre
    fen = Tk()
    fen.title("IHM de simulation d'évacuation")
    fen.geometry("430x650")
    # ajout des zones de saisie permettant de paramétrer la simulation
    Label(fen, text="Largeur de la pièce").grid(row=1, column=1, columnspan=2)
    choix_largeur = Scale(fen, from_=10, to=20, orient=HORIZONTAL)
    choix_largeur.set(10)
    choix_largeur.grid(row=1, column=3)
    Label(fen, text="Profondeur de la pièce").grid(
        row=2, column=1, columnspan=2)
    choix_profondeur = Scale(fen, from_=10, to=20, orient=HORIZONTAL)
    choix_profondeur.set(10)
    choix_profondeur.grid(row=2, column=3)
    Label(fen, text="Nombre d'occupants placés aléatoirement \n(dans la limite de capacité de la pièce)").grid(
        row=3, column=1, columnspan=2)
    choix_nboccupants = Scale(fen, from_=10, to=2000, orient=HORIZONTAL)
    choix_nboccupants.set(200)
    choix_nboccupants.grid(row=3, column=3)
    Label(fen, text="Affichage des nombres en plus des couleurs \n (mode daltonien)").grid(
        row=4, column=1, columnspan=2)
    mode_daltonien = StringVar()
    Checkbutton(fen, text="", var=mode_daltonien, onvalue="oui",
                offvalue="non").grid(row=4, column=3)
    mode_daltonien.set("non")
    btn_grille = Button(fen, text="Créer la pièce", command=creation_piece)
    btn_grille.grid(row=5, column=2)
    # ajout du canvas où sera dessinée la pièce
    Label(fen, text="Un clic sur un côté de la pièce permet d'ajouter une sortie. \nPour ajouter des occupants, cliquer dans la pièce.").grid(
        row=6, column=1, columnspan=3)
    dessin = Canvas(fen, bg="grey", height=330, width=330)
    dessin.grid(row=7, column=1, columnspan=3)
    dessin.bind("<Button-1>", clic_gauche)
    dessin.after(100, affichage_grille)
    Label(fen, text="Nombre d'occupants actuellement dans la pièce :").grid(
        row=8, column=1, columnspan=2)
    nb_occ_restants = Label(fen, text="")
    nb_occ_restants.grid(row=8, column=3)
    # ajout des boutons d'alerte et d'évacuation
    btn_alerte = Button(
        fen, text="Alerter (un pas vers la sortie la plus proche)", command=alerter_occupants)
    btn_alerte.grid(row=9, column=1, columnspan=2)
    btn_evacuer = Button(fen, text="Evacuer", command=evacuer_occupants)
    btn_evacuer.grid(row=9, column=3)
    nb_tour_evac = Label(fen, text="")
    nb_tour_evac.grid(row=10, column=1, columnspan=3)
    # affichage de la fenêtre
    fen.mainloop()

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

QCM — Mise au point et gestion des bugs

1. Une liste notes contient 5 éléments (indices 0 à 4). Que se passe-t-il si on exécute notes[5] ?

2. Pourquoi faut-il éviter de comparer deux flottants avec l'opérateur == en Python ?

3. En executant la version boguee de dernieres_notes du cours (avec la boucle for i in range(1, len(notes) + 1): resultat.append(notes[i])) avec notes = [15, 8, 12], a quelle valeur de i l'erreur IndexError se produit-elle exactement ?

Exercices bilan

Dérouler la pile d'appels d'une somme récursive

ApplicationCorrigé gratuit

On considère la fonction suivante :

def somme(n):
    if n == 0:
        return 0
    else:
        return n + somme(n - 1)

Identifier le cas de base et l'appel récursif de cette fonction.
Dérouler la pile d'exécution pour l'appel somme(4), sur le modèle vu en cours pour factorielle(4) : indiquer, pour chaque appel empilé, ce qu'il attend, jusqu'au cas de base ; puis, en dépilant, la valeur calculée à chaque étape.
En déduire la valeur renvoyée par somme(4), et vérifier qu'elle correspond bien à $0+1+2+3+4$ .
Combien d'appels de la fonction somme (cas de base compris) sont déclenchés au total par l'évaluation de somme(n), pour un entier naturel n quelconque ?
Un élève appelle somme(-3) par erreur. Expliquer pourquoi cet appel ne rencontre jamais le cas de base, et quelle erreur Python finit par lever.

Utiliser l'API d'un module et éviter les imports dangereux

Application

Le module standard math fournit une fonction dont la documentation annonce : « sqrt(x) — Renvoie la racine carrée de x. » Sans avoir besoin de savoir comment cette fonction est implémentée en interne, écrire l'instruction qui importe uniquement cette fonction (et rien d'autre du module), puis l'instruction qui affiche la racine carrée de $225$ .
Écrire un module nommé finance.py, contenant une unique fonction documentée interet_simple(capital, taux, duree), qui renvoie l'intérêt simple généré par un capital placé à un taux annuel (exprimé en décimal, par exemple 0.02 pour $2\,\%$ ) pendant une durée exprimée en années, selon la formule capital × taux × durée. La fonction sera accompagnée d'une docstring donnant un exemple d'utilisation, sur le modèle vu en cours.
Depuis un autre fichier simulation.py, situé dans le même dossier que finance.py, écrire les instructions qui importent ce module puis calculent l'intérêt simple généré par un capital de $5000$ euros placé à $2\,\%$ pendant $3$ ans.
Un camarade a écrit, dans deux fichiers séparés, un module finance.py définissant une fonction calcul(montant) (qui calcule un intérêt), et un module geometrie.py définissant une autre fonction calcul(rayon) (qui calcule une aire de disque). Il les importe ainsi :

from finance import *
from geometrie import *
 
resultat = calcul(5)

Quelle fonction calcul est réellement appelée à la dernière ligne ? Expliquer pourquoi ce genre d'erreur est particulièrement difficile à repérer, et comment écrire les imports pour l'éviter.

En s'appuyant sur l'exemple de sqrt de la question 1, expliquer ce que signifie le terme API.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Déboguer une fonction de moyenne sans la note la plus basse

EntraînementCorrigé gratuit

La fonction suivante est censée calculer la moyenne d'une liste de notes après avoir retiré la plus mauvaise note (une seule occurrence).

def moyenne_sans_min(notes):
    minimum = min(notes)
    notes_restantes = [n for n in notes if n != minimum]
    total = sum(notes_restantes)
    return total / len(notes_restantes)

Exécuter mentalement moyenne_sans_min([8, 8, 15, 17]). Quelle valeur la fonction renvoie-t-elle réellement ?
Une camarade attendait plutôt que la fonction ne retire qu'une seule occurrence de la note la plus basse (ici un seul des deux 8), pour obtenir la moyenne des notes 8, 15 et 17. Calculer cette valeur attendue, et comparer avec la question précédente : le résultat de la fonction est-il correct ?
Un autre élève exécute moyenne_sans_min([8, 8]). Que se passe-t-il ? Nommer l'exception levée par Python, et expliquer précisément, à partir du code, pourquoi elle survient ici.
Corriger la fonction pour qu'elle ne retire réellement qu'une seule occurrence de la note la plus basse, quelle que soit la liste. Vérifier que votre correction renvoie bien la valeur attendue à la question 2 pour [8, 8, 15, 17].
Pourquoi est-il préférable, dans la fonction corrigée, de travailler sur une copie de la liste notes plutôt que d'appeler directement .remove() sur notes ?
Même après la correction, l'appel moyenne_sans_min([12]) provoque encore une erreur. S'agit-il encore d'un bug de la fonction, ou d'une limite légitime de son principe ? Proposer une façon propre de signaler ce cas à l'appelant plutôt que de laisser Python lever une erreur peu explicite.

Mémoïser le calcul récursif d'un coefficient binomial

Entraînement

Le coefficient binomial $\binom{n}{k}$ (« $n$ choisir $k$ ») compte le nombre de façons de choisir $k$ éléments parmi $n$ . La formule de Pascal, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ , se programme directement de façon récursive :

def binom(n, k):
    if k == 0 or k == n:
        return 1
    return binom(n - 1, k - 1) + binom(n - 1, k)

Identifier le ou les cas de base, et l'appel récursif.
Dérouler entièrement l'arbre des appels déclenchés par binom(4, 2), jusqu'aux cas de base, puis calculer la valeur renvoyée en remontant l'arbre. Vérifier que ce résultat correspond bien au nombre de façons de choisir $2$ éléments parmi $4$ .
Combien d'appels à binom (cas de base compris) ont été déclenchés au total pour évaluer binom(4, 2) ? Identifier le couple (n, k) dont le calcul a été déclenché deux fois.
En s'inspirant de la mémoïsation vue en cours, écrire une version binom_memo(n, k) qui ne recalcule jamais deux fois le même couple (n, k).
Le tableau du cours donne la relation $T_n = 2\,T_{n-1} + \Theta(1) \Rightarrow \Theta(2^n)$ pour une fonction qui s'appelle deux fois elle-même sur une entrée de taille réduite de $1$ — le cas de binom non mémoïsée. Expliquer pourquoi la mémoïsation change radicalement l'ordre de grandeur du nombre d'appels, en s'appuyant sur le nombre de couples (n, k) distincts possibles pour n fixé.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Comparer trois styles de programmation sur un même traitement

Entraînement

Voici trois versions d'un même traitement : extraire les mots de plus de $5$ lettres d'une liste, et les mettre en majuscules.

# Version 1
def version1(mots):
    resultat = []
    for m in mots:
        if len(m) > 5:
            resultat.append(m.upper())
    return resultat

# Version 2
def version2(mots):
    return [m.upper() for m in mots if len(m) > 5]

# Version 3
class ListeMots:
    def __init__(self, mots):
        self.mots = mots
 
    def mots_longs_majuscules(self):
        return [m.upper() for m in self.mots if len(m) > 5]

Associer chacune des trois versions à l'un des trois paradigmes vus en cours (impératif, fonctionnel, objet), en justifiant chaque association par une caractéristique du code.
Vérifier, en exécutant mentalement chacune des trois versions sur mots = ["chat", "ordinateur", "sql", "algorithme", "bug"], qu'elles renvoient bien le même résultat. Donner ce résultat.
Réécrire le corps de version1 sous une forme encore plus proche du style fonctionnel pur, en utilisant filter, map et une fonction lambda, sans aucune boucle for explicite ni compréhension de liste.
Un professeur souhaite pouvoir, plus tard, ajouter une deuxième méthode mots_courts(self), qui renverrait les mots de $5$ lettres ou moins. Expliquer pourquoi la version 3 (objet) se prête particulièrement bien à cet ajout, par rapport aux versions 1 et 2.
Expliquer pourquoi appeler version2(mots) plusieurs fois de suite renvoie toujours exactement le même résultat, sans jamais modifier la liste mots d'origine. Proposer, à l'inverse, une modification de version1 qui introduirait un effet de bord indésirable sur la liste mots reçue en argument, en expliquant pourquoi ce serait risqué.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Décidabilité : classer des problèmes et déjouer le raisonnement diagonal

Entraînement

Rappeler, en une phrase chacun, ce que signifient les mots calculable et décidable.
Classer chacun des trois problèmes suivants comme décidable ou indécidable, en justifiant brièvement : a. Étant donné deux entiers naturels, déterminer s'ils sont premiers entre eux (c'est-à-dire si leur seul diviseur commun est $1$ ). b. Étant donné le code source d'un programme Python et une entrée, déterminer s'il finira par s'arrêter. c. Étant donné le code source d'un programme Python, déterminer s'il affiche un jour le mot "ERREUR" au cours de son exécution, quelle que soit l'entrée fournie.
On suppose, par l'absurde, qu'une fonction arret(prog, x) existe, qui termine toujours et renvoie True si prog(x) s'arrête, False sinon — exactement l'hypothèse du cours, avec la fonction diag qu'elle permet de construire. Que se passe-t-il si l'on suppose que arret(diag, diag) renvoie True ? Et si l'on suppose qu'il renvoie False ? En déduire pourquoi ces deux cas sont chacun contradictoires.
Un élève propose la variante suivante :

def diag2(entree):
    if arret(entree, entree):
        return "fini"
    else:
        while True:
            pass

En reprenant le même raisonnement qu'à la question 3 sur diag2(diag2), montrer que cette fois, aucune contradiction n'apparaît. Qu'est-ce que cela révèle sur la construction précise de la fonction diag du cours, indispensable à la preuve ?

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Corriger une recherche dichotomique récursive qui boucle

Type bac

On considère la fonction suivante, censée rechercher cible dans une liste triée par ordre croissant, entre les indices gauche et droite inclus :

def recherche_dichotomique(liste, cible, gauche, droite):
    if gauche > droite:
        return False
    milieu = (gauche + droite) // 2
    if liste[milieu] == cible:
        return True
    elif liste[milieu] < cible:
        return recherche_dichotomique(liste, cible, milieu, droite)
    else:
        return recherche_dichotomique(liste, cible, gauche, milieu - 1)

Elle est appelée initialement par recherche_dichotomique(liste, cible, 0, len(liste) - 1).

Expliquer en une ou deux phrases le principe de la recherche dichotomique, et pourquoi elle exige que liste soit triée.
On exécute recherche_dichotomique([1, 4, 7, 10], 10, 0, 3). Dérouler les appels successifs en donnant, à chaque fois, les valeurs de gauche, droite, milieu, et la branche empruntée — jusqu'à observer un problème. Que constatez-vous à partir du troisième appel ?
Expliquer précisément l'origine du bug : pourquoi l'appel de la branche liste[milieu] < cible peut-il se retrouver avec exactement les mêmes valeurs de gauche et droite qu'à l'appel précédent ? Quelle est la conséquence pour l'exécution du programme ?
Proposer la correction minimale de la fonction (une seule valeur à changer dans l'appel de cette branche). Vérifier, en déroulant à nouveau recherche_dichotomique([1, 4, 7, 10], 10, 0, 3) avec cette correction, qu'elle se termine bien et renvoie le bon résultat.
Quelle est la complexité de la recherche dichotomique corrigée, en fonction du nombre d'éléments n de la liste ? Justifier à l'aide d'une relation de récurrence sur la taille de l'intervalle traité à chaque appel.
Quel principe de mise au point, vu en cours, aurait permis de repérer ce bug avant qu'il ne cause un plantage ? Préciser en particulier quel cas limite, sur cet exemple, aurait suffi à le révéler.

Correction réservée aux abonnés Premium.

Créez un compte gratuit : votre première correction est offerte.

Créer un compte Se connecter

Chapitre suivant

Langages et programmation

Programme et donnée, calculabilité et décidabilité

Le programme est aussi une donnée

La calculabilité ne dépend pas du langage

Le problème de l'arrêt est indécidable

Le théorème de Rice (culture)

QCM — Programme, donnée et décidabilité

Récursivité

Qu'est-ce qu'une fonction récursive ?

La pile d'exécution

Méthode pour écrire une fonction récursive

La suite de Fibonacci : une récursivité qui explose

Complexité d'une fonction récursive

Empreinte carbone

Fichiers fournis

QCM — Récursivité

Modularité : API et bibliothèques

Le principe de modularité

Importer un module

Utiliser une API à travers sa documentation

Documenter avec les docstrings

Créer son propre module

QCM — Modularité, API et bibliothèques

Paradigmes de programmation

Qu'est-ce qu'un paradigme de programmation ?

Le paradigme impératif

Le paradigme fonctionnel

Le paradigme objet

Comparer et choisir un paradigme

QCM — Paradigmes de programmation

Mise au point et gestion des bugs

Le traceback Python

Les causes typiques de bugs

Problèmes liés au typage

Effets de bord non désirés

Débordement d'indices dans un tableau

Instruction conditionnelle non exhaustive

Choix des inégalités

Comparaisons et calculs entre flottants

Mauvais nommage des variables

Les outils de mise au point

Cycle menstruel

Fichier fourni : cycle_menstruel.py

Analyse d'écarts de salaires

Fichier fourni : analyse.py

Codage RLE d'images

Fichier fourni : rle.py

Simulation de l'évacuation d'une pièce

Fichiers fournis

QCM — Mise au point et gestion des bugs

Exercices bilan

Dérouler la pile d'appels d'une somme récursive

Utiliser l'API d'un module et éviter les imports dangereux

Déboguer une fonction de moyenne sans la note la plus basse

Mémoïser le calcul récursif d'un coefficient binomial

Comparer trois styles de programmation sur un même traitement

Décidabilité : classer des problèmes et déjouer le raisonnement diagonal

Corriger une recherche dichotomique récursive qui boucle

Fichier fourni : `cycle_menstruel.py`

Fichier fourni : `analyse.py`

Fichier fourni : `rle.py`