Mines-Ponts 2024 MPI Informatique 1 : sujet en PDF

Sujet de l'épreuve de Informatique 1 du Concours commun Mines-Ponts, France, session 2024, filière MPI, en 3 heures. Thème : Sous-graphe le plus dense : chemins augmentants, algorithme de Goldberg et algorithme de Charikar en C.

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

Ce que traite le sujet, partie par partie

• Section 1 : entourage de plus petite bordure. Réseaux à multiplicités en C, fichier d'en-tête et compilation séparée, parcours en largeur, réseau résiduel, déconnexion par chemins augmentants avec un variant de boucle et égalité entre nombre de chemins et bordure minimale.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Spécifier, tester, prouver : terminaison et correction
• Section 2 : algorithme de Goldberg. Graphes par listes d'adjacence doublement chaînées, degrés et densité, réseau associé à un seuil, oracle de décision fondé sur la bordure minimale et recherche dichotomique de la densité maximale.
  À revoir : Langage C : types, tableaux, pointeurs, allocation, Listes et algorithmes de recherche (séquentielle, dichotomique)
• Section 3 : algorithme de Charikar. Suppression gloutonne du sommet de degré minimal, orientation et degré entrant, facteur d'approximation 2 et structure de données pour une exécution en temps linéaire.

Chapitres à revoir avant de traiter ce sujet

• Langage C : types, tableaux, pointeurs, allocation
• Spécifier, tester, prouver : terminaison et correction
• Listes et algorithmes de recherche (séquentielle, dichotomique)

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.