Terminale · Numérique et sciences informatiques

Comprendre une trace d'exécution pour analyser un code et son coût

Dérouler à la main la trace d'exécution d'un programme Python (variables, tests, itérations), en déduire sa fonction et le nombre d'opérations pour estimer sa complexité.

Aperçu gratuit
Illustration de la fiche « Comprendre une trace d'exécution pour analyser un code et son coût »

Les points essentiels

  • Une trace d'exécution est un tableau qui note, après chaque instruction ou à chaque tour de boucle, la valeur de toutes les variables concernées : elle rend visible ce que le programme fait réellement.
  • Pour tracer un programme, on part de l'état initial des variables, on exécute les instructions dans l'ordre exact du code et on recopie l'état obtenu à chaque étape, sans deviner le résultat.

Les mots à connaître

Trace d'exécution
Tableau, construit à la main ou par un outil, qui liste l'évolution des valeurs des variables au fil des instructions ou des itérations d'un programme sur une entrée donnée.
Complexité (en temps)
Ordre de grandeur du nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n de son entrée, par exemple linéaire (proportionnel à n) ou quadratique (proportionnel à n²).

Un exemple pour comprendre

On considère : def f(t): m = t[0] ; for x in t: if x > m: m = x ; return m. Écrire la trace pour t = [3, 8, 2, 8, 5], dire ce que calcule f et estimer sa complexité.

État initial : m = 3. Itérations : x=3, 3>3 faux, m=3 ; x=8, 8>3 vrai, m=8 ; x=2, 2>8 faux, m=8 ; x=8, 8>8 faux, m=8 ; x=5, 5>8 faux, m=8. La fonction renvoie 8. La trace montre que m ne fait que croître et vaut toujours le maximum des éléments déjà lus (invariant) : f renvoie le plus grand élément de la liste. Le test de égalité 8>8 est faux, donc m n'est pas modifié inutilement. Il y a 5 tours pour 5 éléments : pour une liste de taille n, n comparaisons, donc une complexité linéaire, de l'ordre de n.

Première page de l’Essentiel : Comprendre une trace d'exécution pour analyser un code et son coût
Ketty