Chapitre 1

1.9.1

Le score d'un post p pour un utilisateur u dans EdgeRank est donné par la formule
score(p,u) = a · t · f
où a est l'affinité de u pour l'auteur du post, t est le poids du post et f est un facteur inversément proportionnel à la durée de vie du post.

t est a priori constant (si l'on ne considère pas les éditions) et donc n'influence pas le score au cours du temps. f diminue avec temps et donc n'augmente pas le score avec le temps. a peut potentiellement augmenter avec le temps si la proximité entre u et l'auteur du post augmente. Il est donc possible que le score augmente si l'affinité augmente.

1.9.2

On obtient le graphe suivant :

On pose :
score(q) = 1
score(p) = ½ score(q) = ½
score(p') = ½ score(q) + ½ score(q' ) = ½ + ½ score(q' )

On cherche donc score(q' ) tel que score(p) < score(p' ), ce qui nous donne :
score(p) = ½ < ½ + ½ score(q' ) = score(p' )

L'inégalité est satisfaite du moment que score(q' ) > 0.

1.9.3

On essaye de trouver les utilisateurs qui ont aimé tous les films que u a aimé, et de proposer à u les films que ces utilisateurs ont aimé le plus, mais que u n'a pas encore vu. Plus concrètement, on cherche l'ensemble d'utilisateurs V qui satisfont la condition suivante:

Soit F l'ensemble de films que u a aimé. Alors, v appartient à V si pour chaque f dans F, aime(f, u, v) est vrai.

Ensuite, on veut proposer à u les films les plus appréciés par les utilisateurs dans V, et que u n'a pas encore vus. À cet effet, on peut trier en ordre décroissant les films vus par les utilisateurs V en fonction du nombre d'utilisateurs dans V qui les ont aimé, et proposer à u les premiers films dans cette liste qu'il n'a pas encore vus.

1.9.4

1. L'algorithme présenté ne se termine pas parce que r ne change jamais. Et comme r est strictement supérieur à 0, la boucle (et donc l'algorithme) ne se termine jamais.
2. r doit changer, et finalement arriver à 0, pour tout a et b. Par exemple :

1.9.5

• c secondes. L'algorithme A de complexité O(1) prendrait un temps de l'ordre d'une constante c multipliée par une seconde. Par exemple, un algorithme de complexité O(1) consisterait à prendre le modulo du premier élément d'une liste de taille n.
• 10⁶ c secondes. L'algorithme B de complexité O(n) prendrait un temps de l'ordre d'une constante c multipliée par 10⁶ secondes. Il s'agit par exemple de traverser une liste et multiplier chaque élément par 2.
• 10¹² c secondes. L'algorithme C de complexité O(n²) prendrait un temps de l'ordre d'une constante c multipliée par 10¹² secondes. Il s'agit par exemple de prendre toutes les paires à partir d'éléments dans une liste de taille n.
• 20 c secondes. L'algorithme D de complexité O(log₂(n)) prendrait un temps de l'ordre d'une constante c multipliée par 20 secondes. Il s'agit par exemple d'une recherche par dichotomie sur une liste triée de taille n.

1.9.6

Table de transition :

• Q1 : état initial
• QY : état final "oui"
• QN: état final "non"