Centrale-Supélec 2021 PSI Mathématiques 1 : sujet en PDF

Sujet de l'épreuve de Mathématiques 1 du Concours Centrale-Supélec, France, session 2021, filière PSI, en 4 heures. Thème : Marches aléatoires sur un graphe, matrices stochastiques et algorithme PageRank.

Remarque sur une entreprise citée. La partie III du sujet nomme Google, à propos de l'algorithme PageRank et de ses inventeurs. Google est visée par la pression du mouvement BDS et par la campagne No Tech for Apartheid depuis 2021, à cause du 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 cas de façon neutre, comme le sujet le demande.

Ce que traite le sujet, partie par partie

• Partie I : marche aléatoire sur un graphe. Matrice de transition T d'un graphe orienté, relation P^(k+1) = P^(k) T et propriétés d'une limite éventuelle. Tétraèdre : expression de T à l'aide de J_4 et I_4, réduction par une matrice orthogonale, limite géométrique de T^k et convergence de (P^(k)). Pyramide tronquée à base carrée : matrice de transition, partition des sommets en deux parties et question de la convergence.
• Partie II : matrices stochastiques et distributions de probabilité. Caractérisation matricielle, stabilité par produit et combinaison convexe, inégalités sur les valeurs propres et leur interprétation géométrique, valeurs propres de module 1. Cas des coefficients strictement positifs : dim ker(M - I_n) = 1, encadrement des coefficients de M^k, convergence de (M^k) vers une matrice à lignes égales et unicité de la distribution invariante.
• Partie III : le graphe du web. Modèle de navigation sur le web, matrice A puis matrice B = (1 - alpha)A + (alpha/n)J_n de l'algorithme PageRank, stochasticité, convergence de QB^k et relation vérifiée par les pertinences. Fonctions Python de calcul de B^k par l'algorithme naïf et par exponentiation rapide avec numpy, décompte des appels à np.dot dans le pire et le meilleur des cas.

Chapitres à revoir avant de traiter ce sujet

• Réduction des endomorphismes et des matrices carrées
• Bases de Python : expressions, types, instructions, fonctions
• Récursivité
• Espaces vectoriels normés
• Nombres complexes et trigonométrie
• Arithmétique dans l'ensemble des entiers relatifs
• Compléments d'algèbre linéaire
• Nombres réels et suites numériques

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.