Centrale-Supélec 2018 MP Option informatique : sujet en PDF
Sujet de l'épreuve de Option informatique du Concours Centrale-Supélec, France, session 2018, filière MP, en 4 heures. Thème : Jeu Ricochet Robots : déplacements dans une grille, fonctions utilitaires sur les listes, tables de hachage et plus court chemin par parcours en largeur.
Ce que traite le sujet, partie par partie
- Partie I : déplacement d'un robot dans une grille. Recherche dichotomique en temps logarithmique dans un tableau strictement croissant, déplacements possibles d'un robot dans une ligne puis dans la grille, matrice des déplacements et sa mise à jour quand un autre robot bouge, complexité d'une recherche exhaustive des suites de k déplacements.
- Partie II : quelques fonctions utilitaires. Tri par insertion d'une liste et complexité dans le pire et le meilleur cas, appartenance et association dans une liste de couples, file implantée par deux listes.
- Partie III : tables de hachage. Famille de fonctions de hachage sur des listes d'entiers, table de largeur fixée avec recherche, ajout et suppression, coût moyen d'une recherche fructueuse ou non, puis table dynamique qui se réorganise quand elle se remplit.
- Partie IV : résolution du jeu des robots. Graphe orienté des configurations et nombre de sommets, sommets accessibles en un coup, parcours en largeur : terminaison, visite de tous les sommets accessibles, plus court chemin et complexité, puis résolution du jeu.
Chapitres à revoir avant de traiter ce sujet
- Listes et algorithmes de recherche (séquentielle, dichotomique)
- Langage OCaml : expressions, types, filtrage, récursivité
- Complexité des algorithmes itératifs et récursifs
- Tris par sélection, à bulles, par insertion et par comptage
- Piles, files et deques
- Dictionnaires et principes du hachage
- Spécifier, tester, prouver : terminaison et correction
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.