(Durée de l'épreuve : 3 heures) L'usage d'une calculatrice est autorisé.
Sujet mis à la disposition des concours : Concours Commun TPE/EIVP, Concours Mines-Télécom, Concours Centrale-Supélec (Cycle international).
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : INFORMATIQUE - MP
L'énoncé de cette épreuve comporte 10 pages de texte. L'épreuve est composée de deux exercices indépendants, l'ensemble du sujet comportant 24 questions.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré.
Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement.
Préliminaire concernant la programmation
Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout autre langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire appel à d'autres fonctions définies dans les questions précédentes; il pourra aussi définir des fonctions auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas nécessaire de justifier que celle-ci est correcte, sauf si l'énoncé le demande explicitement. Enfin, si les paramètres d'une fonction à coder sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'écriture de cette fonction de tester si les hypothèses sont bien vérifiées.
Dans les énoncés du premier exercice, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique pour la police en italique (par exemple ) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n ).
1 Graphe du Web
Le World Wide Web, ou Web, est un ensemble de pages Web (identifiées de manière unique par leurs adresses Web, ou URL pour Uniform Resource Locators, de la forme http://mines-ponts.fr/index.php) reliées les unes aux autres par des hyperliens. Le Web est souvent modélisé comme un graphe orienté dont les sommets sont les pages Web et les arcs les hyperliens entre pages. Le Web étant potentiellement infini, on s'intéresse à des sous-graphes du Web obtenus en naviguant sur le Web, c'est-à-dire en le parcourant page par page, en suivant les hyperliens d'une manière bien déterminée. Ce parcours du Web pour en collecter des sous-graphes est réalisé de manière automatique par des logiciels autonomes appelés Web crawlers ou crawlers en anglais, ou collecteurs en français.
Fonctions utilitaires
Nous allons tout d'abord coder certaines fonctions de manipulation de structures de données de base, qui seront utiles dans le reste de l'exercice. - Coder une fonction aplatir : ('a * 'a list) list -> 'a list, telle que, si liste est une liste de couples , où chaque est un élément de type 'a, et une liste d'éléments de type 'a de la forme , aplatir liste est une liste d'éléments de type 'a:
- Coder une fonction tri_fusion : (' a * ' b ) list (' a * ' b ) list triant une liste de couples ( ) par ordre décroissant de la valeur de la seconde composante de chaque couple. On devra utiliser l'algorithme de tri par partition-fusion (aussi appelé «tri fusion»). Quelle est la complexité de cet algorithme?
On va utiliser dans la suite de l'exercice un type de données dictionnaire qui permet de stocker des couples formés d'une chaîne de caractères (une clef) et d'un entier (une valeur). On dit que le dictionnaire associe la valeur à la clef. À chaque clef présente dans le dictionnaire est associée une seule valeur. Les fonctions suivantes sont supposées être prédéfinies :
dictionnaire_vide : unit -> dictionnaire.
L'appel dictionnaire_vide () crée un nouveau dictionnaire vide.
ajoute : string -> int -> dictionnaire -> dictionnaire.
L'appel ajoute clef valeur dict renvoie un nouveau dictionnaire identique au dictionnaire dict, sauf qu'un couple (clef, valeur) y a été ajouté. Cette fonction s'exécute en temps où est le nombre d'entrées du dictionnaire.
contient : string -> dictionnaire -> bool.
L'appel contient clef dict renvoie un booléen indiquant s'il y a un couple dont la clef est clef dans le dictionnaire dict. Cette fonction s'exécute en temps où est le nombre d'entrées du dictionnaire.
valeur : string -> dictionnaire -> int.
L'appel valeur clef dict renvoie la valeur associée à la clef clef dans le dictionnaire dict. Cette fonction s'exécute en temps où est le nombre d'entrées du dictionnaire. Cette fonction ne peut être appelée que si la clef clef est présente dans le dictionnaire.
On suppose pour la suite de l'exercice que le type de données dictionnaire est prédéfini; on ne demande pas de l'implémenter. - Coder unique : string list -> string list * dictionnaire, qui est telle que unique liste renvoie un couple (liste', dict) où liste' est la liste des chaînes de caractères de liste distinctes (dans l'ordre de leur première occurrence dans liste) et où dict associe à chaque chaîne de caractères dans liste' sa position dans liste' (en numérotant à partir de 0 ). Ainsi l'appel unique ["x";"zz";"x";"x";"zz";"yt"] renvoie un couple formé de la liste ["x";"zz";"yt"] et d'un dictionnaire associant à "x" la valeur 0, à "zz" la valeur 1 et à "yt" la valeur 2 . - Quelle est la complexité de la fonction unique en terme de la longueur de la liste liste en argument et du nombre d'éléments distincts dans la liste liste? Justifier la réponse.
Crawler simple
Nous allons maintenant implémenter un crawler simple en Caml. On suppose fournie une fonction recupere_liens : string -> string list prenant en argument l'URL d'une page Web et renvoyant la liste des URL des pages pour lesquelles il existe un hyperlien de à , dans l'ordre lexicographique.
Pour illustrer le comportement de cette fonction, nous considérons un exemple de mini-graphe du Web à six pages et neuf hyperliens comme suit :
Dans cette représentation, p1, p2, etc., sont les URL de pages Web (simplifiées pour l'exemple), et les arcs représentent les hyperliens entre pages Web.
Dans ce mini-graphe, un appel à recupere_liens "p1" retourne la liste ["p2"; "p5"].
Un crawler est un programme qui, à partir d'une URL, parcourt le graphe du Web en visitant progressivement les pages dont les liens sont présents dans chaque page rencontrée, en suivant une stratégie de parcours de graphe (par exemple, largeur d'abord, ou profondeur d'abord). À chaque nouvelle page, si celle-ci n'a pas déjà été visitée, tous ses hyperliens sont récupérés et ajoutés à une liste de liens à traiter. Le processus s'arrête quand une condition est atteinte (par exemple, un nombre fixé de pages ont été visitées). Le résultat renvoyé par le crawler, que l'on définira plus précisément plus loin, est appelé un crawl. - Coder crawler_bfs : int -> string -> (string * string list) list qui prend en entrée un nombre de pages et une URL et renvoie en sortie une liste de longueur au plus de couples ( ) où est l'URL d'une page visitée (les pages apparaissant dans l'ordre où elles ont été visitées) et la liste des liens récupérés sur la page . On demande que crawler_bfs parcoure le graphe du Web en suivant une stratégie en largeur d'abord (breadth-first search), c'est-à-dire en visitant en priorité les pages rencontrées le plus tôt dans l'exploration. Le crawler doit visiter pages distinctes, et donc appeler fois la fonction recupere_liens (sauf s'il n'y a plus de pages à visiter). On utilisera une variable de type dictionnaire pour se souvenir des pages déjà visitées.
Par exemple, sur le mini-graphe, crawler_bfs 4 "p1" pourra renvoyer le résultat:
- Coder crawler_dfs : int -> string -> (string * string list) list qui prend en entrée un nombre de pages et une URL et renvoie en sortie une liste de longueur au plus de couples où est l'URL d'une page
visitée (les pages apparaissant dans l'ordre où elles ont été visitées) et la liste des liens récupérés sur la page . On demande que crawler_dfs parcoure le graphe du Web en suivant une stratégie en profondeur d'abord (depth-first search), c'est-à-dire en visitant en priorité les pages rencontrées le plus récemment dans l'exploration. Le crawler doit visiter pages distinctes, et donc appeler fois la fonction recupere_liens (sauf s'il n'y a plus de pages à visiter). On utilisera une variable de type dictionnaire pour se souvenir des pages déjà visitées.
Par exemple, sur le mini-graphe, crawler_dfs 4 "p1" pourra renvoyer le résultat :
- Coder une fonction Caml construit_graphe :
(string * string list) list -> string list * int vect vect telle que si crawl est le résultat renvoyé par un crawler (une liste de couples formés d'une URL et de la liste des liens récupérés sur la page ), alors construit_graphe crawl est un couple ( ) où est une liste de toutes les URL de pages contenues dans la liste crawl et est la matrice d'adjacence du sous-graphe partiel du Web restreint aux pages de la liste est le nombre de liens découverts dans le crawl de la page d'indice dans vers la page d'indice dans . On fera commencer les indices à 0 . Pour coder la fonction construit_graphe, on pourra utiliser les fonctions aplatir et unique.
Par exemple, sur le mini-graphe, si crawl est une variable contenant le résultat de l'appel crawler_bfs 4 "p1" (voir question 5), alors construit_graphe crawl doit renvoyer :
p3 apparaît même s'il n'a pas été visité dans le crawl;
p6 n'apparaît pas car il n'a pas été découvert dans le crawl;
l'hyperlien de p3 à p5 n'apparaît pas car p3 n'a pas été visité.
Calcul de PageRank
PageRank est une manière d'affecter un score à l'ensemble des pages du Web, imaginée par Sergey Brin et Larry Page, les fondateurs du moteur de recherche Google. L'introduction de PageRank a révolutionné la technologie des moteurs de recherche sur le Web. Nous allons maintenant implémenter le calcul de PageRank.
Étant donnée une partie du Web (où l'ensemble des pages est indexé entre 0 et ), la matrice de surf aléatoire dans cette partie du Web est la matrice de taille définie comme suit :
S'il n'y a aucun lien depuis une page Web d'indice , alors pour tout .
Sinon, s'il y a liens depuis la page Web d'indice , alors pour tout , on a , où est le nombre de liens depuis la page d'indice vers la page d'indice et est un nombre réel fixé appartenant à (on prend souvent .
Cette matrice peut être vue comme décrivant la marche aléatoire d'un surfeur sur le Web. À chaque fois que celui-ci visite une page Web :
Si cette page ne comporte aucun lien, il visite une page Web arbitraire, choisie aléatoirement de façon uniforme.
Si cette page comporte au moins un lien, il visite avec une probabilité égale à un des liens sortants de cette page, et avec une probabilité égale à une page Web arbitraire, choisie aléatoirement de façon uniforme. -Coder surf_aleatoire : float -> int vect vect -> float vect vect telle que si est un nombre entre 0 et 1 , et si est la matrice d'adjacence d'un sous-graphe partiel du Web, alors surf_aleatoire d G renvoie la matrice de surf aléatoire dans ce sous-graphe. - Coder multiplie : float vect -> float vect vect -> float vect, une fonction prenant en argument un vecteur ligne de taille et une matrice de taille et renvoyant le vecteur ligne de taille résultant du produit de par la matrice . En d'autres termes, pour tout , .
Le PageRank des pages d'un sous-graphe du Web à pages se calcule par des multiplications successives d'un vecteur ligne par la matrice de surf aléatoire de ce sous-graphe. Plus précisément, soit un nombre réel strictement positif (par exemple, ) et soit le vecteur ligne de taille dont toutes les composantes valent . On pose pour un entier naturel arbitraire . L'algorithme de PageRank calcule la suite des pour jusqu'à ce que et renvoie alors le vecteur , considéré comme le vecteur des scores de PageRank. On peut montrer (à l'aide du théorème de Perron-Frobenius) que l'algorithme termine dès lors que est strictement positif.
PageRank est utilisé pour affecter un score d'importance aux pages du Web. Le vecteur de scores retourné par l'algorithme de PageRank donne dans le score d'importance
de la page d'indice . Les pages de plus haut score de PageRank sont considérées comme les plus importantes. - Coder pagerank : float -> float vect vect -> float vect, une fonction prenant en argument un nombre et une matrice de surf aléatoire d'un sous-graphe du Web et renvoyant le vecteur des scores de PageRank pour et . La fonction pagerank devra faire appel à la fonction multiplie précédemment codée. - Coder calcule_pagerank :
float -> float -> (string * string list) list -> (string * float) list telle que calcule_pagerank d theta crawl renvoie une liste de couples ( ), un couple pour chaque URL découverte dans le crawl crawl, triée par valeur décroissante de , où est l'URL de cette page et son score de PageRank. Ici, et sont les deux paramètres nécessaires au calcul de la matrice de surf aléatoire et du PageRank respectivement. On pourra faire appel à la fonction tri_fusion et à l'ensemble des fonctions développées dans les questions précédentes.
2 Automates probabilistes
On fixe dans cet exercice un alphabet .
Un automate probabiliste sur l'alphabet est un quadruplet où :
(i) est un ensemble fini non vide dont les éléments sont appelés états;
(ii) est appelé état initial ;
(iii) est un ensemble dont les éléments sont appelés états finals;
(iv) est une application appelée fonction probabiliste de transition ; on suppose que pour tout , pour tout . On note pour .
Une transition est un triplet , noté , avec . On représente un automate probabiliste de manière graphique, de façon similaire à la représentation des automates non-déterministes classiques : les états sont représentés par des cercles, l'état initial par une flèche arrivant sur le cercle correspondant, les états finals par des cercles doubles. La fonction probabiliste de transition est représentée par une flèche entre états : si est un nombre , on met une flèche de l'état à l'état , annotée par « .
Ainsi, l'automate représenté ci-dessous :
a pour fonction probabiliste de transition Pr la fonction suivante (seules les valeurs non nulles sont mentionnées) :
1
1
1
Étant donné un automate probabiliste sur , un chemin est une suite finie de transitions aussi notée ; on dit que a pour étiquette le mot , pour état de départ l'état et pour état d'arrivée l'état . La probabilité de , notée , est définie par . Un état peut être vu comme un chemin de longueur nulle; la probabilité d'un chemin de longueur nulle est égale à 1 . Un chemin pour le mot est un chemin dont l'étiquette est et l'état de départ est . Ce chemin est acceptant si l'état d'arrivée est un état de , non-acceptant sinon. La probabilité d'un mot , notée , est par définition la somme des probabilités de tous les chemins acceptants pour le mot :
- Calculer les probabilités pour l'automate (ici, est le mot vide). - Montrer, pour tout automate probabiliste et tout mot , l'égalité suivante en utilisant une récurrence sur la longueur du :
14 - On revient à l'automate probabiliste . Quels sont les mots dont la probabilité pour est égale à 0 ? Quels sont ceux dont la probabilité est égale à 1 ? - Proposer (sans justification) une expression rationnelle pour le langage des mots dont la probabilité pour est non nulle. - Montrer que pour tout automate probabiliste , il existe un automate non nécessairement déterministe qui accepte exactement les mots dont la probabilité pour est non nulle. - Appliquer la construction de la question précédente à l'automate pour obtenir un automate non-déterministe qui accepte exactement les mots dont la probabilité pour est non nulle. Déterminiser cet automate.
Soit un automate probabiliste sur . Pour un réel , le -langage reconnu par , noté , est défini par :
On dit qu'un langage est stochastique s'il existe un automate probabiliste et un réel tel que . - Démontrer que tout langage rationnel est stochastique.
Étant donné un mot sur l'alphabet , on dit que l'expression « » est une écriture (finie) en base 2 du nombre réel . On note alors :
Ainsi, .
On considère maintenant l'automate ci-dessous : - Dans l'automate , calculer et en donner une écriture finie en base 2. - Dans l'automate , calculer et en donner une écriture finie en base 2. - Dans l'automate , calculer et en donner une écriture finie en base 2. - Soit un mot arbitraire sur . Montrer que pour admet une écriture finie en base 2, et en donner une expression. Prouver que cette écriture est correcte. - Soit . Prouver l'égalité suivante :
- En déduire qu'il existe des langages stochastiques qui ne sont pas rationnels.
Fin de l'épreuve
Mines Option Informatique MP 2016 - Version Web LaTeX | WikiPrépa | WikiPrépa
