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

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).