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.

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

