Prepa HelpCentrale 2024 MPI Informatique : sujet en PDF
Sujet de l'épreuve de Informatique du Concours Centrale-Supélec, France, session 2024, filière MPI, en 4 heures. Thème : Le jeu de go : implémentation en C, k plus proches voisins, hachage de Zobrist, recherche arborescente de Monte-Carlo et complexité.
Ce que traite le sujet, partie par partie
- Partie I : introduction au jeu de go. Règles simplifiées, groupes et libertés, existence d'un gagnant.
- Partie II : implémentation du jeu de go (langage C). Représentation du goban, voisins d'une position, calcul d'un groupe, jeu de tests, retrait des groupes capturés et fonction qui joue un coup.
- Partie III : prédiction et évaluation d'un prochain coup. Algorithme des k plus proches voisins (sélection des k plus petites distances, structure de données adaptée, borne inférieure pour un algorithme par comparaisons), puis hachage de Zobrist des motifs pour évaluer un coup.
- Partie IV : recherche arborescente de Monte-Carlo (langage OCaml). Simulation de parties, valeur d'action, descente et remontée dans l'arbre, expansion, algorithme complet avec plusieurs fils d'exécution et preuve de terminaison.
- Partie V : complexité du problème de la stratégie gagnante. Classe NP et réduction depuis un problème de satisfiabilité à l'aide de gadgets placés sur le goban.
Chapitres à revoir avant de traiter ce sujet
- Langage C : types, tableaux, pointeurs, allocation
- Algorithmes, discipline de programmation, validation et tests
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Logique, ensembles et applications
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.