Informatique : algorithmique et programmation Python
Ce que teste l’épreuve
L’épreuve d’informatique du concours e3a-Polytech (option informatique) porte sur l’algorithmique et la programmation en Python : structures de données, fonctions, récursivité, complexité et preuves de correction. Elle évalue la capacité à écrire un code correct, à justifier sa terminaison et à analyser son coût. Les questions peuvent demander de compléter une fonction, de corriger un bug ou de comparer deux algorithmes.
Règles et concepts clés
- En Python, les indices d’une liste vont de 0 à n−1 ; une tranche t[a:b] exclut b.
- Les types mutables (listes, dictionnaires) sont modifiés par effet de bord ; une copie explicite est nécessaire pour préserver l’original.
- Une fonction récursive exige un cas de base et un appel sur un sous-problème strictement plus petit.
- Complexité : une boucle simple est O(n), deux boucles imbriquées O(n²), une division par deux à chaque étape O(log n).
- Pour prouver une boucle, énoncer un invariant vrai avant et après chaque itération, puis vérifier la terminaison.
Exemple travaillé
Recherche dichotomique dans une liste triée : on maintient lo et hi tels que, si x est présent, il soit dans t[lo:hi]. À chaque itération, on calcule mid=(lo+hi)//2 ; si t[mid]<x, alors lo=mid+1, sinon hi=mid. L’invariant garantit qu’aucun élément candidat n’est perdu. La taille de l’intervalle est au moins divisée par deux, donc la terminaison est assurée et la complexité est O(log n), contre O(n) pour une recherche linéaire. Une erreur classique est d’écrire hi=mid−1 alors que mid peut être la réponse.
Pièges qui coûtent des points
- Dépasser les bornes avec while lo<hi ou mal initialiser hi=len(t).
- Oublier de renvoyer une valeur sur un chemin.
- Modifier une liste pendant qu’on la parcourt.
- Confondre complexité temporelle et nombre d’appels récursifs.
- Écrire un cas de base qui ne progresse pas vers la solution.
Attendu méthodologique
Commentez brièvement l’invariant et la complexité. Testez mentalement les cas limites : liste vide, un seul élément, valeur absente. Un code qui passe un exemple mais échoue sur la liste vide n’est pas considéré comme correct.