CCINP 2025 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2025, filière MP, en 4 heures. Thème : Partage d'un réseau : arbre couvrant de poids maximal, algorithme de Borůvka et jeu sur un graphe.

Ce que traite le sujet, partie par partie

• Partie I : base de données du réseau. Clés primaires et étrangères, requêtes SQL avec jointure et agrégation, lecture d'une requête sur les tables des villes et des liaisons d'un réseau imaginaire.
• Partie II : arbre couvrant de poids maximal. Acyclicité, connexité et arbres, existence d'un arbre couvrant et existence et unicité de l'arbre de poids maximal quand la pondération est injective.
• Partie III : recherche d'un arbre couvrant de poids maximal. En OCaml, listes d'adjacence pondérées, composantes connexes par parcours en profondeur et algorithme de Borůvka, avec terminaison, correction et complexité.
• Partie IV : chemin de bande passante maximale. Le chemin de l'arbre couvrant de poids maximal réalise la bande passante maximale entre deux sommets, et la bande passante limite du graphe est le plus petit poids de cet arbre.
• Partie V : jeu sur un graphe. Partage du réseau vu comme un jeu à deux joueurs : terminaison, calcul de score en Python, mémoïsation, algorithme MinMax avec heuristique et argument du vol de stratégie.

Chapitres à revoir avant de traiter ce sujet

• Langage OCaml : expressions, types, filtrage, récursivité
• Récursivité
• Complexité des algorithmes itératifs et récursifs
• Bases de Python : expressions, types, instructions, fonctions

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.