Mines-Ponts 2025 MP Informatique commune : sujet en PDF

Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2025, filière MP, en 2 heures. Thème : Autour du sac à dos : glouton, programmation dynamique, séparation et évaluation, colonies de fourmis.

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

Ce que traite le sujet, partie par partie

• Partie 1 : base de données de fret maritime. Requêtes SQL sur des tables de navires et de conteneurs : sélection avec dates et tri par un ratio, puis nombre de conteneurs attribués à chaque navire.
• Parties 2 et 3 : structures de données des objets et des solutions. Profit et contrôle de la contrainte de ressources d'une solution codée par une liste de 0 et de 1, arbre binaire des choix et coût exponentiel d'une recherche exhaustive.
  À revoir : Bases de Python : expressions, types, instructions, fonctions, Complexité des algorithmes itératifs et récursifs
• Partie 4 : résolution approchée par un algorithme glouton. Tri par insertion décroissant des rapports profit sur ressource avec suivi des indices, meilleur et pire cas de ce tri, sélection gloutonne et contre-exemple montrant qu'elle n'est pas optimale.
  À revoir : Complexité des algorithmes itératifs et récursifs
• Partie 5 : résolution exacte par programmation dynamique. Remplissage d'un tableau à deux dimensions par la relation de récurrence du sac à dos, déroulement sur un exemple, complexité, puis reconstruction de la solution optimale.
  À revoir : Complexité des algorithmes itératifs et récursifs
• Partie 6 : résolution exacte par séparation et évaluation. Arbre des solutions construit récursivement avec des dictionnaires, test de feuille, fonction d'élagage par la contrainte et par une borne du profit, et réécriture de la recherche exhaustive récursive en version élaguée.
  À revoir : Récursivité, Dictionnaires et principes du hachage
• Parties 7 et 8 : colonies de fourmis et analyse des résultats. Mise en œuvre de l'optimisation par colonies de fourmis : évaporation et dépôt de phéromone, meilleure solution, tirage aléatoire du premier objet, probabilités de choix stockées dans un dictionnaire, puis comparaison des temps et de la qualité des solutions des différentes méthodes.
  À revoir : Dictionnaires et principes du hachage, Bases de Python : expressions, types, instructions, fonctions

Chapitres à revoir avant de traiter ce sujet

• Bases de Python : expressions, types, instructions, fonctions
• Complexité des algorithmes itératifs et récursifs
• Récursivité
• Dictionnaires et principes du hachage

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.