CCINP 2023 MPI Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Commun INP (CCINP), France, session 2023, filière MPI, en 4 heures. Thème : Palindromes, traversée de rivière et coupe minimum d'un graphe.

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

Ce que traite le sujet, partie par partie

• Partie I : palindromes. Comptage des facteurs palindromes d'un mot : algorithme naïf et sa complexité, programmation dynamique, puis algorithme linéaire fondé sur les symétries autour de chaque centre après insertion d'un symbole séparateur.
  À revoir : Algorithmes, discipline de programmation, validation et tests
• Partie II : traversée de rivière. Deux groupes de randonneurs se croisent sur un chemin de cailloux : codage du chemin par un tableau, fonctions OCaml d'avance et de saut, puis nombre de mouvements nécessaires au passage.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité
• Partie III : coupe minimum d'un graphe. Contraction d'arête dans un multigraphe, algorithme probabiliste de Karger et minoration de sa probabilité de succès, amplification par répétition, puis implémentation en C avec des types structurés d'arête et de graphe et complexité.
  À revoir : Langage C : types, tableaux, pointeurs, allocation

Chapitres à revoir avant de traiter ce sujet

• Algorithmes, discipline de programmation, validation et tests
• Langage OCaml : expressions, types, filtrage, récursivité
• Langage C : types, tableaux, pointeurs, allocation

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.