Prepa HelpMines-Ponts 2025 PC Informatique commune : sujet en PDF
Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2025, filière PC, en 2 heures. Thème : Autour du sac à dos.
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 pour préparer un chargement.
- 2 Structure de données pour l'espace des objets. Objets représentés par des couples (ressource, profit), solution codée par une liste de 0 et de 1, calcul du profit et vérification de la contrainte de ressources.
- 3 Structure de données pour l'espace des solutions. Arbre binaire des choix, nombre de feuilles et coût exponentiel d'une recherche par force brute.
- 4 Résolution approchée par un algorithme glouton. Tri des objets selon le rapport profit sur ressource, remplissage glouton du sac et complexité.
- 5 Résolution exacte par programmation dynamique. Tableau des profits optimaux construit ligne par ligne et exécution à la main sur un petit exemple.
- 6 Résolution exacte par un algorithme PSE. Arbre binaire des solutions construit récursivement avec des dictionnaires, recherche exhaustive puis élagage des branches par séparation et évaluation.
- 7 Résolution approchée par colonie de fourmis (ACO). Construction aléatoire de solutions par des fourmis guidées par des traces de phéromone, probabilités stockées dans un dictionnaire et mise à jour bornée des traces.
- 8 Analyse des résultats. Comparaison des temps d'exécution et de la qualité des solutions obtenues par les différentes méthodes.
Chapitres à revoir avant de traiter ce sujet
- Bases de Python : expressions, types, instructions, fonctions
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- 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.