Terminale · Numérique et sciences informatiques

Découvrir la démarche pour résoudre et expliquer un problème d'informatique

Dérouler, sur un problème simple, la démarche complète : spécifier le problème, écrire un algorithme en Python, suivre sa trace d'exécution, estimer sa complexité et justifier oralement ses choix.

Aperçu gratuit
Illustration de la fiche « Découvrir la démarche pour résoudre et expliquer un problème d'informatique »

Les points essentiels

  • Résoudre un problème d'informatique commence par sa spécification : entrées, sorties attendues, contraintes et cas limites (liste vide, valeur absente, doublons).
  • Un algorithme est une suite finie d'instructions non ambiguës ; le code Python en est une traduction exécutable, mais l'idée algorithmique doit rester explicable indépendamment du langage.

Les mots à connaître

Trace d'exécution
Tableau ou liste des valeurs successives des variables d'un programme au fil de son exécution, par exemple à chaque tour de boucle, utilisé pour comprendre et vérifier le comportement du code.
Complexité (temporelle)
Évaluation de l'ordre de grandeur du nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n de ses données, indépendamment de la machine.

Un exemple pour comprendre

Problème : trouver le maximum d'une liste non vide d'entiers. Écrire une fonction Python, tracer son exécution sur [4, 9, 2, 9, 7] et donner sa complexité.

Spécification : entrée = liste t non vide d'entiers ; sortie = plus grande valeur de t. Idée : garder le meilleur candidat rencontré. Code : def maximum(t): m = t[0]; for x in t[1:]: if x > m: m = x; return m. Trace : au départ m=4 ; x=9 donc 9>4 et m=9 ; x=2 donc m reste 9 ; x=9 donc 9>9 est faux et m reste 9 ; x=7 donc m reste 9. Résultat : 9. Invariant : après chaque tour, m est le maximum des éléments déjà examinés. Complexité : n-1 comparaisons pour une liste de n éléments, donc coût linéaire O(n).

Première page de l’Essentiel : Découvrir la démarche pour résoudre et expliquer un problème d'informatique
Ketty