Applications informatiques

10.1 Transformations geometriques

Les matrices permettent de representer des transformations du plan.

Translation (en coordonnees homogenes) :

Pour translater un point (x, y) de (tx, ty) :

[ 1  0  tx ] [ x ]   [ x + tx ]
[ 0  1  ty ] [ y ] = [ y + ty ]
[ 0  0   1 ] [ 1 ]   [   1    ]

Rotation d'angle theta autour de l'origine :

[ cos(theta)  -sin(theta) ] [ x ]   [ x.cos(theta) - y.sin(theta) ]
[ sin(theta)   cos(theta) ] [ y ] = [ x.sin(theta) + y.cos(theta) ]

Exemple : rotation de 90 degres (cos 90 = 0, sin 90 = 1).

R = [ 0  -1 ]
    [ 1   0 ]

Appliquee au point (3, 2) :

[ 0  -1 ] [ 3 ]   [ 0 x 3 + (-1) x 2 ]   [ -2 ]
[ 1   0 ] [ 2 ] = [ 1 x 3 +   0  x 2 ] = [  3 ]

Le point (3, 2) est transforme en (-2, 3).

Homothetie (mise a l'echelle) de facteur k :

[ k  0 ] [ x ]   [ kx ]
[ 0  k ] [ y ] = [ ky ]

10.2 PageRank simplifie

Le PageRank de Google modelise le web comme un graphe. Chaque page est un sommet, chaque lien est un arc. La matrice de transition T represente les probabilites de naviguer d'une page a une autre.

Principe : si une page a n liens sortants, chaque lien transmet une probabilite 1/n.

Exemple avec 3 pages :

• Page 1 pointe vers Page 2 et Page 3.
• Page 2 pointe vers Page 3.
• Page 3 pointe vers Page 1.

Matrice de transition :

        P1    P2    P3
T = [  0    1/2   1/2 ]   P1 (2 liens sortants, chacun vaut 1/2)
    [  0     0     1  ]   P2 (1 lien sortant)
    [  1     0     0  ]   P3 (1 lien sortant)

En partant de la distribution uniforme P₀ = [1/3 1/3 1/3], on itere P_{n+1} = P_n x T.

P₁ = [1/3  1/3  1/3] x T

composante 1 : (1/3) x 0 + (1/3) x 0 + (1/3) x 1 = 0 + 0 + 1/3 = 1/3
composante 2 : (1/3) x (1/2) + (1/3) x 0 + (1/3) x 0 = 1/6 + 0 + 0 = 1/6
composante 3 : (1/3) x (1/2) + (1/3) x 1 + (1/3) x 0 = 1/6 + 1/3 + 0 = 1/6 + 2/6 = 3/6 = 1/2

P₁ = [1/3  1/6  1/2]

La Page 3 a le score le plus eleve (1/2), ce qui est logique car elle recoit des liens de la Page 1 et de la Page 2.

10.3 Chaines de Markov : distribution stationnaire

La distribution stationnaire pi est le vecteur tel que pi x T = pi et la somme des composantes vaut 1.

Cela revient a resoudre un systeme d'equations lineaires.

Exemple avec la matrice :

T = [ 0.2  0.8 ]
    [ 0.5  0.5 ]

On cherche pi = [pi₁ pi₂] tel que pi x T = pi et pi₁ + pi₂ = 1.

pi₁ = 0.2 x pi₁ + 0.5 x pi₂
pi₂ = 0.8 x pi₁ + 0.5 x pi₂

Premiere equation :

pi₁ = 0.2 pi₁ + 0.5 pi₂
pi₁ - 0.2 pi₁ = 0.5 pi₂
0.8 pi₁ = 0.5 pi₂
pi₂ = (0.8/0.5) pi₁ = 1.6 pi₁

Avec pi₁ + pi₂ = 1 :

pi₁ + 1.6 pi₁ = 1
2.6 pi₁ = 1
pi₁ = 1/2.6 = 5/13
pi₂ = 1.6 x (5/13) = 8/13

Distribution stationnaire : pi = [5/13, 8/13], soit environ [0.385, 0.615].