Prepa HelpMines-Ponts 2025 PSI Informatique commune : sujet en PDF
Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2025, filière PSI, en 2 heures. Thème : Autour du sac à dos : glouton, programmation dynamique, séparation et évaluation, colonie de fourmis.
Ce que traite le sujet, partie par partie
- 1 Base de données : exemple de fret maritime de conteneurs. Requêtes SQL sur des tables de navires et de conteneurs : filtrage avec dates, tri par ratio tarification sur longueur et comptage des conteneurs par navire.
- 2 Structure de données pour l'espace des objets. Objets codés par des tuples (ressource, profit), solution codée par une liste de 0 et de 1 : calcul du profit et test de la contrainte de ressources.
- 3 Structure de données pour l'espace des solutions. Arbre binaire des choix, nombre de feuilles et complexité exponentielle d'une résolution par force brute.
- 4 Résolution approchée par un algorithme glouton. Tri par insertion des rapports profit sur ressource avec suivi des indices, meilleur et pire cas du tri, remplissage glouton du sac et contre-exemple montrant la non-optimalité.
- 5 Résolution exacte par un algorithme de programmation dynamique. Tableau des profits maximaux construit par la relation de récurrence, complexité en fonction du nombre d'objets et de la capacité, puis reconstruction de la solution optimale.
- 6 Résolution exacte par un algorithme PSE. Arbre des solutions représenté par des dictionnaires imbriqués et construit récursivement, test de feuille, critère d'élagage sur la ressource et sur le profit, et réécriture de la recherche exhaustive récursive en séparation et évaluation.
- 7 Résolution approchée par colonie de fourmis (ACO). Métaheuristique probabiliste avec traces de phéromone et évaporation : complétion des étapes de construction des solutions par les fourmis et de mise à jour des traces.
- 8 Analyse des résultats. Comparaison des temps d'exécution et de la qualité des solutions des différentes méthodes sur un exemple de vingt objets, rôle des paramètres de l'algorithme ACO.
Chapitres à revoir avant de traiter ce sujet
- Bases de Python : expressions, types, instructions, fonctions
- 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.