CCINP 2026 MPI Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2026, filière MPI, en 4 heures. Thème : Voyageur de commerce et suite de Prouhet-Thue-Morse.

Lire le sujet 8 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,6 Mo)

Ce que traite le sujet, partie par partie

• Partie I : problème du voyageur de commerce. Appartenance à NP, réductions de COUVERTURE-SOMMET vers CYCLE-HAMILTONIEN puis vers TSP pour la NP-complétude, 2-approximation par arbre couvrant minimal et parcours en profondeur, puis implémentation en C avec gestion de la mémoire.
  À revoir : Langage C : types, tableaux, pointeurs, allocation
• Partie II : suite de Prouhet-Thue-Morse. Trois définitions équivalentes de la suite, fonctions OCaml récursives sur les listes, mots sans carré et preuve par récurrence que le mot de Thue-Morse ne contient pas de cube.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Langage OCaml : expressions, types, filtrage, récursivité

Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.