Mines Informatique optionnelle MP 2016

Thème de l'épreuve Graphe du Web et automates probabilistes
Principaux outils utilisés parcours de graphe, tri fusion, automate fini, probabilités
Mots clefs pagerank, web, URL, langage stochastique

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


A 2016 - INFO MP. École des PONTS ParisTech, ISAE-SUPAERO, ENSTA ParisTech, TÉLÉCOM ParisTech, MINES ParisTech, MINES Saint-Étienne, MINES Nancy, TÉLÉCOM Bretagne, ENSAE ParisTech (Filière MP). CONCOURS 2016 ÉPREUVE D'INFORMATIQUE (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. Page 1 sur 10 Épreuve d'informatique 2016 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 n) 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. 1 ­ Coder une fonction aplatir : ('a * 'a list) list -> 'a list, telle que, si liste est une liste de couples [(x1 , lx1 ); . . . ; (xn , lxn )], où chaque xi est un élément de type 'a, et lxi une liste d'éléments de type 'a de la forme [yi1 ; . . . ; yiki ], aplatir liste est une liste d'éléments de type 'a : [x1 ; y11 ; . . . ; y1k1 ; x2 ; y21 ; . . . ; y2k2 ; . . . ; xn ; yn1 ; . . . ; ynkn ]. 2 ­ Coder une fonction tri_fusion : ('a * 'b) list -> ('a * 'b) list triant une liste de couples (x, y) par ordre décroissant de la valeur de la seconde composante y de chaque couple. On devra utiliser l'algorithme de tri par partition­fusion (aussi appelé « tri fusion »). Quelle est la complexité de cet algorithme ? Page 2 sur 10 Épreuve d'informatique 2016 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(log n) où n 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(log n) où n 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(log n) où n 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. 3 ­ 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. 4 ­ Quelle est la complexité de la fonction unique en terme de la longueur n de la liste liste en argument et du nombre m 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 p et renvoyant la liste des URL des pages q pour lesquelles il existe un hyperlien de p à q, dans l'ordre lexicographique. Page 3 sur 10 Épreuve d'informatique 2016 Pour illustrer le comportement de cette fonction, nous considérons un exemple de mini-graphe du Web à six pages et neuf hyperliens comme suit : p2 p1 p4 p3 p6 p5 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. 5 ­ Coder crawler_bfs : int -> string -> (string * string list) list qui prend en entrée un nombre n de pages et une URL u et renvoie en sortie une liste de longueur au plus n de couples (v, l) où v est l'URL d'une page visitée (les pages apparaissant dans l'ordre où elles ont été visitées) et l la liste des liens récupérés sur la page v. 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 n pages distinctes, et donc appeler n 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 : ["p1", "p2", "p5", "p4", ["p2"; "p5"]; ["p1"; "p4"]; ["p5"]; ["p3"; "p5"]] 6 ­ Coder crawler_dfs : int -> string -> (string * string list) list qui prend en entrée un nombre n de pages et une URL u et renvoie en sortie une liste de longueur au plus n de couples (v, l) où v est l'URL d'une page Page 4 sur 10 Épreuve d'informatique 2016 visitée (les pages apparaissant dans l'ordre où elles ont été visitées) et l la liste des liens récupérés sur la page v. 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 n pages distinctes, et donc appeler n 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 : ["p1", "p2", "p4", "p3", ["p2"; ["p1"; ["p3"; ["p5"; "p5"]; "p4"]; "p5"]; "p6"]] 7 ­ 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 v et de la liste des liens récupérés sur la page v), alors construit_graphe crawl est un couple (l, G) où l est une liste de toutes les URL de pages contenues dans la liste crawl et G est la matrice d'adjacence du sous-graphe partiel du Web restreint aux pages de la liste l : Gij est le nombre de liens découverts dans le crawl de la page d'indice i dans l vers la page d'indice j dans l. 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 : ["p1"; [|[|0; [|1; [|0; [|0; [|0; "p2"; 1; 1; 0; 0; 0; 1; 0; 1; 0; 0; "p5"; "p4"; "p3"], 0; 0|]; 1; 0|]; 0; 0|]; 0; 1|]; 0; 0|]|] En particulier : -- 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é. Page 5 sur 10 Épreuve d'informatique 2016 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 n - 1), la matrice de surf aléatoire dans cette partie du Web est la matrice M de taille n × n définie comme suit : -- S'il n'y a aucun lien depuis une page Web d'indice i, alors pour tout j, Mij := 1/n. -- Sinon, s'il y a ki liens depuis la page Web d'indice i, alors pour tout j, on a Mij := (1 - d) × Gij /ki + d/n, où Gij est le nombre de liens depuis la page d'indice i vers la page d'indice j et d est un nombre réel fixé appartenant à [0, 1] (on prend souvent d = 0,15). 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 à 1 - d un des liens sortants de cette page, et avec une probabilité égale à d une page Web arbitraire, choisie aléatoirement de façon uniforme. 8 ­ Coder surf_aleatoire : float -> int vect vect -> float vect vect telle que si d est un nombre entre 0 et 1, et si G est la matrice d'adjacence d'un sous-graphe partiel du Web, alors surf_aleatoire d G renvoie la matrice M de surf aléatoire dans ce sous-graphe. 9 ­ Coder multiplie : float vect -> float vect vect -> float vect, une fonction prenant en argument un vecteur ligne v de taille n et une matrice M de taille n × n et renvoyant le vecteur ligne w de taille n résultant du produit de v par la matrice M : w = vM . En d'autres termes, pour tout j, q wj = i vi Mij . Le PageRank des pages d'un sous-graphe du Web à n pages se calcule par des multiplications successives d'un vecteur ligne par la matrice de surf aléatoire M de ce sous-graphe. Plus précisément, soit un nombre réel strictement positif (par exemple, = 10-4 ) et soit v (0) le vecteur ligne de taille n dont toutes les composantes valent 1/n. On pose pour un entier naturel p arbitraire v (p) := v (0) M p . L'algorithme de PageRank calcule la suite des v (p) pour p = 0, 1, . . . jusqu'à ce que ëv (p+1) - v (p) ë1 6 et renvoie alors le vecteur v (p+1) , 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 d est strictement positif. PageRank est utilisé pour affecter un score d'importance aux pages du Web. Le vecteur de scores v retourné par l'algorithme de PageRank donne dans vi le score d'importance Page 6 sur 10 Épreuve d'informatique 2016 de la page d'indice i. Les pages de plus haut score de PageRank sont considérées comme les plus importantes. 10 ­ Coder pagerank : float -> float vect vect -> float vect, une fonction prenant en argument un nombre > 0 et une matrice M de surf aléatoire d'un sous-graphe du Web et renvoyant le vecteur des scores de PageRank pour et M . La fonction pagerank devra faire appel à la fonction multiplie précédemment codée. 11 ­ Coder calcule_pagerank : float -> float -> (string * string list) list -> (string * float) list telle que calcule_pagerank d theta crawl renvoie une liste de couples (u, s), un couple pour chaque URL découverte dans le crawl crawl, triée par valeur décroissante de s, où u est l'URL de cette page et s son score de PageRank. Ici, d 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 = {0, 1}. Un automate probabiliste sur l'alphabet est un quadruplet A = (Q, q0 , F, Pr) où : (i) Q est un ensemble fini non vide dont les éléments sont appelés états ; (ii) q0 Q est appelé état initial ; (iii) F Q est un ensemble dont les éléments sont appelés états finals ; (iv) Pr : Q××Q [0, 1] est une application appelée fonction probabiliste de transition ; q on suppose que pour tout q Q, pour tout , q Q Pr(q, , q ) = 1. On note Pr(q - q ) pour Pr(q, , q ). Une transition est un triplet (q, , q ) Q × × Q, noté q - q , avec Pr(q - q ) > 0. 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 Pr(q - q ) est un nombre p > 0, on met une flèche de l'état q à l'état q , annotée par « (p) ». Page 7 sur 10 Épreuve d'informatique 2016 Ainsi, l'automate A0 = ({q0 , q1 }, q0 , {q1 }, Pr) représenté ci-dessous : 0 ( 34 ), 1 (1) 0 ( 14 ) q0 q1 0 (1), 1 (1) a pour fonction probabiliste de transition Pr la fonction suivante (seules les valeurs non nulles sont mentionnées) : q q Pr(q - q ) q0 q0 q0 q1 q1 0 0 1 0 1 q0 q1 q0 q0 q0 3/4 1/4 1 1 1 Étant donné un automate probabiliste A = (Q, q0 , F, Pr) sur , un chemin est une 1 1 2 n n suite finie de transitions qi1 - qi2 , . . ., qin - qin+1 aussi notée qi1 - qi2 - . . . - qin+1 ; on dit que a pour étiquette le mot 1 . . . n , pour état de départ l'état qi1 Q et pour état d'arrivée l'état qin+1 Q. La probabilité de , notée Pr(), est définie par r k Pr() := nk=1 Pr(qik - qik+1 ). 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 u est un chemin dont l'étiquette est u et l'état de départ est q0 . Ce chemin est acceptant si l'état d'arrivée est un état de F , non-acceptant sinon. La probabilité d'un mot u , notée Pr(u), est par définition la somme des probabilités de tous les chemins acceptants pour le mot u : Ø Pr(u) := Pr(). chemin acceptant pour u 12 ­ Calculer les probabilités Pr(), Pr(0), Pr(010) pour l'automate A0 (ici, est le mot vide). 13 ­ Montrer, pour tout automate probabiliste A = (Q, q0 , F, Pr) et tout mot u , l'égalité suivante en utilisant une récurrence sur la longueur du mot u : Ø Pr(u) = 1 - Pr(). chemin non-acceptant pour u 14 ­ On revient à l'automate probabiliste A0 . Quels sont les mots u dont la probabilité Pr(u) pour A0 est égale à 0 ? Quels sont ceux dont la probabilité est égale à 1 ? Page 8 sur 10 Épreuve d'informatique 2016 15 ­ Proposer (sans justification) une expression rationnelle pour le langage des mots u dont la probabilité Pr(u) pour A0 est non nulle. 16 ­ Montrer que pour tout automate probabiliste A = (Q, q0 , F, Pr), il existe un automate non nécessairement déterministe A qui accepte exactement les mots u dont la probabilité Pr(u) pour A0 est non nulle. 17 ­ Appliquer la construction de la question précédente à l'automate A0 pour obtenir un automate non-déterministe qui accepte exactement les mots u dont la probabilité Pr(u) pour A0 est non nulle. Déterminiser cet automate. Soit A = (Q, q0 , F, Pr) un automate probabiliste sur . Pour un réel [0, 1[, le -langage reconnu par A, noté L (A), est défini par : L (A) := { u | Pr(u) > } . On dit qu'un langage L est stochastique s'il existe un automate probabiliste A et un réel [0, 1[ tel que L = L (A). 18 ­ Démontrer que tout langage rationnel est stochastique. Étant donné un mot 1 . . . n sur l'alphabet {0, 1}, on dit que l'expression « 0, 1 . . . n 2 » q est une écriture (finie) en base 2 du nombre réel ni=1 2-i i . On note alors : n Ø 2-i i = 0, 1 2 . . . n 2 . i=1 Ainsi, 14 = 2-2 = 0, 012 = 0, 01002 . On considère maintenant l'automate A1 = ({q0 , q1 }, q0 , {q1 }, Pr) ci-dessous : 0 ( 12 ), 1 (1) 0 (1), 1 ( 12 ) 1 ( 12 ) q0 q1 0 ( 12 ) 1 1 1 0 1 19 ­ Dans l'automate A1 , calculer Pr(q0 - q0 - q1 - q1 - q0 - q1 ) et en donner une écriture finie en base 2. 20 ­ Dans l'automate A1 , calculer Pr(10) et en donner une écriture finie en base 2. 21 ­ Dans l'automate A1 , calculer Pr(1101) et en donner une écriture finie en base 2. Page 9 sur 10 Épreuve d'informatique 2016 22 ­ Soit u un mot arbitraire sur . Montrer que Pr(u) pour A1 admet une écriture finie en base 2, et en donner une expression. Prouver que cette écriture est correcte. 23 ­ Soit [0, 1[. Prouver l'égalité suivante : L (A1 ) = { 1 . . . n | 0, n . . . 1 2 > }. 24 ­ En déduire qu'il existe des langages stochastiques qui ne sont pas rationnels. Fin de l'épreuve Page 10 sur 10

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Informatique optionnelle MP 2016 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (Enseignant-chercheur à l'université) ; il a été relu par Vincent Puyhaubert (Professeur en CPGE) et Guillaume Batog (Professeur en CPGE). Ce sujet est composé de deux parties indépendantes abordant le graphe du Web puis les automates probabilistes. Il est d'une longueur raisonnable, même si les nombreuses questions de programmation réclament du sang-froid pour être résolues le plus rapidement possible. · La première partie contient exclusivement des questions de programmation et de complexité. Après le codage de fonctions très classiques sur les listes, l'énoncé expose comment se calcule le score de Pagerank de pages web, celui qui est utilisé par le moteur de recherche Google. On s'intéresse à un sous-graphe des pages web issues d'une même URL source. Ce graphe est parcouru en largeur puis en profondeur. De ce parcours, appelé crawl, on extrait une matrice d'adjacence des hyperliens reliant les pages visitées. Cette matrice est à la base du calcul du score. Ce dernier représente la probabilité qu'un « surfeur » aléatoire visite une certaine page web en supposant qu'il peut soit avancer de page en page via les hyperliens, soit sauter à une page web choisie aléatoirement de façon uniforme. Le score est finalement calculé à l'aide de multiplications de matrices de probabilités. · Dans la seconde partie, les automates finis sont enrichis de probabilités. Contrairement aux automates finis qui décrivent des langages de mots finis (un mot u est-il accepté ou non ?), les automates probabilistes associent à un mot fini u une probabilité dans [ 0 ; 1 ]. Les automates probabilistes sont une généralisation des chaînes de Markov ; ils sont notamment utilisés pour le traitement des langues naturelles et la traduction automatique. Introduits par Michael O. Rabin en 1963, les langages qu'ils décrivent sont dits stochastiques : une fois fixé un seuil [ 0 ; 1 [, un tel langage contient tous les mots u dont la probabilité d'être reconnu par l'automate probabiliste est strictement supérieure à . En particulier, le sujet propose de prouver que tout langage rationnel est stochastique, puis étudie un cas particulier d'automate probabiliste qui montre l'existence d'un langage stochastique non rationnel. Les deux parties font appel aux probabilités. La première contient des questions très classiques de programmation (tri fusion, parcours en profondeur et en largeur) traitées avec la structure de dictionnaire (introduite dans le sujet). La seconde est plus originale. Signalons que les questions 13 et 22 demandent un raisonnement non trivial, à base de récurrence, et que la dernière demande une preuve technique originale. Indications Partie 1 1 Utiliser l'opérateur @ permettant de concaténer deux listes. 2 Adapter l'algorithme vu en cours au cas d'un tri par ordre décroissant de la seconde composante de chaque couple. 4 Estimer la complexité du traitement d'un élément de la liste en majorant la taille du dictionnaire utilisé. 5 Exécuter un parcours en largeur à l'aide d'une file, qu'on pourra implémenter à l'aide d'une liste : les éléments sont insérés en fin de liste et extraits en tête de liste. 6 Modifier la fonction de la question 5 pour obtenir un parcours en profondeur à l'aide d'une pile, plutôt qu'une file. 7 Construire la liste l ainsi qu'un dictionnaire associant à chaque URL sa position dans la liste à l'aide des fonctions unique et aplatir. Pour connaître la position d'une URL dans la liste, utiliser la fonction valeur. 8 Transformer un entier en flottant à l'aide de la fonction float_of_int. Penser à utiliser les opérateurs flottants, suffixés d'un point. 10 Commencer par coder une fonction calculant la distance, au sens de la norme 1, entre deux vecteurs. 11 Calculer la liste des URL du crawl ainsi que le vecteur de score de Pagerank associé à l'aide des fonctions construit_graphe, surf_aleatoire et pagerank. Associer chaque score à son URL puis utiliser la fonction tri_fusion. Partie 2 13 Prouver par récurrence sur la longueur des mots u que la somme des probabilités des chemins pour u est égale à 1. Pour l'hérédité, écrire u = u avec . Décomposer alors chaque chemin pour u en un chemin pour u puis une transition d'étiquette . 18 Pour tout langage rationnel, considérer un automate déterministe complet le reconnaissant et l'interpréter comme un automate probabiliste. 22 Inférer à partir des questions 20 et 21 la valeur de Pr(1 2 · · · n ) en fonction du mot n · · · 2 1 . 24 Montrer que si 0 6 1 < 2 < 1, alors L2 (A1 ) ( L1 (A1 ). Conclure en observant qu'il n'y a qu'un nombre dénombrable de langages rationnels. 1. Graphe du Web 1 Aplatissons la liste de couples [(x1 , lx1 ); . . . ; (xn , lxn )] à l'aide d'une fonction récursive qui parcourt de gauche à droite la liste et concatène les unes aux autres les listes de premier élément xi et de reste lxi . let rec aplatir = function | [] -> [] | (x,l)::liste -> (x::l)@(aplatir liste);; On peut profiter de la fonction flat_map dans cette question. En effet, cette fonction, de type ('a -> 'b list) -> 'a list -> 'b list, associe à une fonction f de type 'a -> 'b list et une liste [l1 ; ... ; ln] d'éléments de type 'a, la liste (f l1) @ (f l2) @ ... @ (f ln). On obtient alors l'implémentation suivante : let aplatir liste = flat_map (fun (x,l) -> x::l) liste;; 2 Afin de coder la fonction tri_fusion, introduisons d'abord deux fonctions auxiliaires. Tout d'abord, la fonction diviser de type 'a list -> 'a list * 'a list prend en argument une liste et la scinde en deux listes de tailles identiques à une unité près. Elle est implémentée de façon récursive en isolant le cas des listes contenant zéro ou un élément. let | | | rec diviser = function [] -> [],[] [a] -> [a],[] a::b::l -> let (l1,l2) = diviser l in (a::l1,b::l2);; Ensuite, la fonction fusionner de type ('a * 'b) list -> ('a * 'b) list -> ('a * 'b) list prend en arguments deux listes supposées triées par ordre décroissant suivant la valeur de la seconde composante de chaque couple et les fusionne. Elle est aussi implémentée de manière récursive. let rec fusionner l1 l2 = match (l1,l2) with | [],_ -> l2 | _,[] -> l1 | (x1,y1)::q1, (x2,y2)::q2 -> if (y1 >= y2) then (x1,y1)::(fusionner q1 l2) else (x2,y2)::(fusionner l1 q2);; L'opérateur infixe d'ordre >= est polymorphe en Caml. Ainsi, on pourra instancier la fonction fusionner, puis la fonction tri_fusion, avec un type 'b quelconque, par exemple le type int des entiers ou le type string des chaînes de caractères. Dans ce dernier cas, l'ordre utilisé est l'ordre lexicographique. Finalement, la fonction récursive tri_fusion traite trivialement le cas d'une liste d'au plus un élément et trie une liste plus grande en la divisant, puis en fusionnant le résultat des appels récursifs aux deux sous-listes ainsi obtenues. let | | | rec tri_fusion = function [] -> [] [a] -> [a] l -> let (l1,l2) = diviser l in fusionner (tri_fusion l1) (tri_fusion l2);; D'après le cours, L'algorithme de tri par partition-fusion trie une liste de taille n avec une complexité en O(n log n). 3 La fonction unique utilise un dictionnaire qui associe à chaque chaîne de caractères rencontrée jusqu'alors sa position dans la liste liste en train d'être créée. Pour retenir la position courante, utilisons une référence valeur, initialisée à 0. Puisque la fonction d'ajout dans le dictionnaire renvoie le nouveau dictionnaire modifié, on stocke le dictionnaire dans une référence également. Une fonction auxiliaire récursive parcourir, de type string list -> string list, permet de parcourir de droite à gauche la liste donnée en entrée et de renvoyer la liste liste contenant ses chaînes distinctes. Pour chaque élément, s'il n'est pas déjà contenu dans le dictionnaire (ce que teste la fonction contient), il est ajouté au dictionnaire (grâce à la fonction ajoute) en lui associant la valeur courante, puis celle-ci est incrémentée. Dans tous les cas, le reste de la liste est traité à l'aide d'un appel récursif. let unique liste = let dict = ref (dictionnaire_vide ()) and valeur = ref 0 in let rec parcourir = function | [] -> [] | s :: q -> if (contient s !dict) then parcourir q else ( dict := ajoute s !valeur !dict; incr valeur; s::(parcourir q) ) in let l = parcourir liste in (l, !dict);; Contrairement aux apparences, la dernière ligne de cette fonction n'est pas équivalente à in (parcourir liste, !dict) ; ; En effet, l'exécution de cette version modifiée renverrait à chaque fois un dictionnaire vide en deuxième élément de la paire. Ceci s'explique par le fait qu'en Caml, le code d'une paire est exécuté de droite à gauche : ici, le dictionnaire serait donc renvoyé avant même l'appel à parcourir. 4 Considérons une liste liste de taille n contenant m chaînes de caractères distinctes. Lors de l'exécution de la fonction unique, et plus précisément de la fonction auxiliaire parcourir, chaque chaîne de la liste est traitée indépendamment. À la fin de l'exécution, le dictionnaire contient exactement m clefs correspondant aux chaînes distinctes de liste. Ainsi, à tout moment, le dictionnaire contient moins de m clefs et les fonctions contient et ajoute s'exécutent en temps O(log m). Pour chaque chaîne de caractères de la liste, un test d'appartenance au dictionnaire courant est réalisé. Lors de la première occurrence de cette chaîne, la chaîne est de plus ajoutée au dictionnaire. Dans tous les cas, le traitement d'une chaîne s'exécute donc en temps O(log m). Puisqu'il y a n chaînes dans la liste, la complexité totale est en O(n log m).