Annales sur Algorithmique et complexité

Algorithmique et complexité

Au programme

L'algorithmique et la complexité couvrent les structures de données fondamentales (listes, piles, files, arbres, graphes), les algorithmes de tri, la recherche dichotomique, le diviser pour régner, la programmation dynamique et l'analyse de complexité (temps et espace, pire cas, moyen). En MPI, le programme va plus loin avec l'informatique théorique. En MP, PC, PSI le tronc commun reste centré sur les structures et l'analyse de coût.

Pourquoi c'est testé

85 sujets de concours dans notre base portent sur l'algorithmique. L'épreuve d'informatique CCINP (commune aux trois filières) en est le support principal, complétée par Info Mines-Ponts MP et Info X-ENS PSI/MP. Les pièges récurrents pointés par les jurys :

• Recherche dichotomique mal initialisée : confusion sur l'indice « milieu » (jury Info CCINP PC 2025 : « beaucoup de candidats calculent l'indice " milieu " en faisant une différence entre ind_fin et ind_deb »)
• Détermination de maximum imparfaite sur l'initialisation (jury Info CCINP PC 2025 : « Cette première question de code, réalisée parfaitement par la moitié des candidats, demande une simple détermination de maximum : il faut faire attention à l'initialisation »)
• Codage d'un entier — nombre de bits mal estimé (jury Info CCINP PC 2024 : « Combien de bits pour coder l'entier 48 ? 248 ? Rarement 6 malheureusement »)
• Structure de données mal comprise : copies erronées entre listes d'une structure (jury Info CCINP PC 2024 : « Il y a souvent des erreurs dans la copie des deux listes de la structure jeu »)

Comment réviser

Trois axes priorisés :

1. Maîtriser les invariants de boucle : les énoncer explicitement avant d'écrire le code, ils sont attendus en rédaction. 2. Calculer la complexité au pire cas dès qu'un algorithme est écrit — pas en fin de partie quand il reste cinq minutes. 3. Travailler les sujets d'info les plus testés : Info CCINP PC 2024 et 2025 (recherche, structures), Info X-ENS PSI 2024-2025 (algorithmique pure), Info Mines-Ponts MP 2024.