Informatique (option informatique, MP) - algorithmique et programmation
Ce que l'épreuve teste
L'épreuve écrite d'informatique (option informatique, filière MP) porte sur l'algorithmique et la programmation : structures de données (listes, piles, files, arbres, graphes, tables de hachage), récursivité, complexité, preuve de correction, et programmation en Python ou en Caml selon le programme. Le concours demande d'écrire des algorithmes corrects, d'en justifier la terminaison et la complexité, et de comparer des structures de données.
Ce qui est attendu dans une réponse
- Un algorithme ou un programme complet, avec ses cas de base et ses invariants explicites.
- Une preuve de terminaison : la variante décroît strictement et reste positive.
- Une preuve de correction : l'invariant est vrai à l'initialisation, se conserve, et donne le résultat à la sortie.
- Une complexité exprimée en fonction de la taille d'entrée, au pire cas, avec sa justification (nombre d'itérations, coût d'une opération élémentaire).
Exemple travaillé
Recherche d'un élément x dans un tableau trié t de taille n : on compare x à t[m] avec m = (i+j)//2 et on réduit l'intervalle. L'invariant est « si x est dans t, il est dans t[i..j] ». Terminaison : la longueur j−i+1 diminue strictement à chaque itération (division entière), donc le cas de base est atteint. Complexité : la taille est divisée par deux à chaque étape, soit au plus ⌈log₂ n⌉ itérations, donc O(log n), contre O(n) pour une recherche linéaire. La conclusion doit nommer le coût des opérations et la structure utilisée : c'est ce qui distingue une réponse complète d'un simple code.
Pièges
- Confondre complexité au pire cas et complexité moyenne, ou l'affirmer sans justification.
- Choisir une liste là où un ensemble ou un dictionnaire donne un accès en O(1).
- Erreurs de borne dans la dichotomie (i = m au lieu de m+1), qui provoquent une boucle infinie.
- Récursion sans cas de base, ou sans preuve de terminaison.
- Écrire du code sans commenter l'invariant : le correcteur ne peut pas suivre le raisonnement.