Mines-Ponts 2016 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2016, filière MP, en 3 heures. Thème : Graphe du Web et calcul de PageRank ; automates probabilistes et langages stochastiques.
Remarque sur une entreprise citée. Le sujet cite Google. Cette entreprise est visée par le boycott : contrat Project Nimbus (1,2 milliard de dollars, 2021) : nuage et intelligence artificielle pour le gouvernement et l'armée d'occupation. Le jour du concours, traite le sujet de façon neutre, comme il le demande.
Ce que traite le sujet, partie par partie
- 1 Graphe du Web : fonctions utilitaires et crawlers. Fonctions Caml d'aplatissement et de dédoublonnage avec un dictionnaire de positions, collecteurs de pages en largeur puis en profondeur d'abord qui mémorisent les pages visitées, et construction de la matrice d'adjacence du sous-graphe collecté.
- 1 Graphe du Web : calcul de PageRank. Matrice de surf aléatoire avec facteur d'amortissement, produit d'un vecteur ligne par une matrice, itération jusqu'à stabilisation du vecteur des scores et classement des pages par tri fusion.
- 2 Automates probabilistes. Probabilité d'acceptation d'un mot comme somme sur les chemins acceptants, preuve par récurrence de la formule complémentaire, automate non déterministe des mots de probabilité non nulle et sa déterminisation, langages stochastiques contenant les langages rationnels, puis écriture en base 2 des probabilités d'un automate particulier qui montre l'existence de langages stochastiques non rationnels.
Chapitres à revoir avant de traiter ce sujet
- Graphes : représentations et parcours
- Dictionnaires et principes du hachage
- Langage OCaml : expressions, types, filtrage, récursivité
- Piles, files et deques
- Tri par fusion et tri rapide
- Espaces probabilisés
- Architecture de l'ordinateur et représentation des nombres
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.