Centrale 2023 MPI Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours Centrale-Supélec, France, session 2023, filière MPI, en 4 heures. Thème : Voyageur de commerce et algorithme de Christofides (en C), graphes d'arbres et opérations NNI et SPR (en OCaml).

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

Ce que traite le sujet, partie par partie

• Partie I : problème du voyageur de commerce (langage C). Circuits hamiltoniens et appartenance à NP, réductions entre problèmes hamiltoniens et depuis 3-SAT, impossibilité d'une approximation à facteur constant sans inégalité triangulaire si P est différent de NP. Algorithme de Christofides : arbre couvrant de Kruskal, sommets de degré impair, couplage parfait, cycle eulérien transformé en circuit hamiltonien, complexité et facteur 3/2.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Logique, ensembles et applications
• Partie II : espaces d'arbres (langage OCaml). Arbres binaires non racinés à feuilles étiquetées et opérations NNI et SPR, graphe G_NNI(n) et étude de G_NNI(5), construction de G_NNI(n) en OCaml, puis preuve par récurrence que G_SPR(n) est hamiltonien.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Récursivité

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Logique, ensembles et applications
• Langage OCaml : expressions, types, filtrage, récursivité
• 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.