Spécialité en Terminale S

Spécialité en Terminale S

Stage de formation continueAcadémie de Dijon


1 – Une introduction

Traitement d’images

Une image en niveaux de gris : mosaïque de pixels ; chaque pixel codé par son intensité lumineuse ; codage sur 1 octet, entre 0 (noir) et 255 (blanc) ; intensité lumineuse des pixels normalisée par un nombre de l'intervalle [0;1] ; palette simplifiée de niveaux de gris ci-contre.

00,10,20,30,40,50,60,70,80,9

1

Introduction aux matrices


Une image carrée de 64 pixels.

On souhaite pouvoir effectuer différents traitements sur cette image comme : éclaircir ; assombrir ; prendre le négatif.

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0


Comment modéliser ces traitements ?


On associe à l’image un tableau de nombres. Modifier l’image revient à modifier les valeurs du tableau: en appliquant une fonction à chaque élément ;

(nécessité d’algorithmes de parcours de la matrice) en définissant une opération sur le tableau.


Traitement d'images : bilan

Notion de matrice apparaît naturellement. Nécessité de définir des opérations sur les matrices justifiée :

par le but recherché (modifier l’image) ; par les logiciels qui donnent pour M² un autre résultat

que le carré de chaque élément de M.


Un réseau de transports

Graphe des connexions entre les gares de trois villes A, B et C.

Les entiers au-dessus des arêtes indiquent le nombre de liaisons pour chaque connexion.

On peut représenter ces informations à l'aide de 2 matrices, puis en déduire la matrice des liaisons de la ville A vers la ville C.


Activité issue du manuel

Odyssée, Terminale S (Hatier)

Un réseau de transports


Un réseau de transports : bilan

Le produit de matrices apparaît comme réponse à un problème de dénombrement.

Pour aller de la gare ai à la gare cj, il y a trois gares intermédiaires possibles, ce qui aide à comprendre dans ce cas la formule

ci j=∑k=1

3

a i k bk j



2 – Le modèle de diffusion d'Ehrenfest

Le modèle de diffusion d'Ehrenfest

Simulation1000 particules et 10 000 échanges


0 50 100 150 200 250 300 350 400 450 5000

20

40

60

80

100

120


Simulation100 particules et 500 échanges

0 50 100 150 200 250 300 350 400 450 5000

2

4

6

8

10

12



0 50 100 150 200 250 300 350 400 450 5000

1

2

3

4

5

6

7



0 50 100 150 200 250 300 350 400 450 5000

0.5

1

1.5

2

2.5



Deux questions :

Peut-on parler de stabilisation ? Peut-on toujours revenir à l'état initial ?


Les trois états possibles

Probabilité de passer à r

1à r

2à r

3

de r1

0 1 0

de r2

1/2 0 1/2

de r3

0 1 0

Le modèle de diffusion d'Ehrenfest : N=2

Graphe et matrice de transition

A= ( 0 1 012

012

0 1 0)

r1

r2

r3

12

12

1

1


État au rang n modélisé par un vecteur ligne :Loi de probabilité de la variable Xn

égale au nombre de particules dans II.

Initial : V0=(1 0 0)Il est certain qu'il n'y a pas de particule dans II.

Rang 1 : V1=V0A=(0 1 0)Il est certain qu'il y a 1 particule dans II.

Rang 2 : V2=V1A=V0A2=(½ 0 ½)Il y a 1 chance sur 2 qu'il n'y ait pas de particule dans II,

1 chance sur 2 qu'il y en ait 2.

Rang 3 : V3=V2A=V0A3=(0 1 0)=V1

Le modèle de diffusion d'EhrenfestLe modèle de diffusion d'Ehrenfest : N=2

(Vn) : suite géométrique de matrices lignes

A3=A donc la suite oscille entre deux valeurs : si n est pair, Vn=(½ 0 ½) si n est impair, Vn=(0 1 0)

Pas d'état stable


Recherche d'un état stable

Sur 2n étapes : T2n nombre d'étapespour un retour à l'état initial

P(T2n=1)=0 P(T2n=2)=½ P(T2n=3)=P(T2n=2k+1)=0 P(T2n=2k)=(½)k


Retour à l'état initial

Espérance de T2n :

Par somme, on obtient :

E (T 2n )=∑i=1

2n

i×P (T 2n =i )=∑k=1

n

2k×P (T 2n=2k )=∑k=1

n

k× 12k−1

∑k=1

n1

2k−1=2−(12 )

n−1

∑k= 2

n1

2k−1=1−(12 )

n−1

∑k= 3

n1

2k−1=1

2−( 12 )

n−1E (T 2n )=4−

n+ 2

2n−1

etc...


Retour à l'état initial

Réfléchir à une mise en place effectiveavec les élèves.


Les cas N=3 et N=4


3 – Échanges autour du programme

• On ne commence pas par exposer pas des contenus, on résout des problèmes.

• Les contenus introduits doivent être motivés, ils sont réponses à une question, ce qui leur donne du sens.

Échanges autour du programme

Exigible au baccalauréat :Les notions expressément écrites dans la colonne contenu.




4 – Le chiffrementde Hill

Code César Codes par substitution monoalphabétique Code de Vigenère (décrypté par Babbage) Enigma : inventé vers 1918 par Scherbius, décryptée pendant le 2nde guerre mondiale par Turing.

Le chiffrement de Hill

Histoire des codes secrets

Fragilité des codes mono-alphabétiques Chaque lettre codée par un caractère unique. Décryptage possible par analyse des fréquences.

1931 : Nouvel algorithme publié par Lester Hill : Codage des caractères par bloc. Une même lettre codé par un caractère différent en fonction de sa position.


Un nouvel algorithme de codage

Chaque lettre codée par un nombre de 0 à 25. Clé de chiffrement constituée de 4 entiers compris entre 0 et 25 : a, b, c, d.

À chaque couple d'entiers (x ,y) on associe le couple d'entiers compris entre 0 et 25 (x' ,y') tels que :


Principe

x'≡ax+by [26 ]y'≡cx+dy [26 ]


Exercice 1



Exercice 2



Exercice 3



Exercice 4


Le chiffrement de Hill est sensible à l'analyse des fréquences : chaque couple de lettres est codé par le même couple de lettres ; on peut donc étudier la fréquence des différents digrammes.

Pour rendre l'analyse plus difficile, on peut coder par groupes de 3 lettres ou plus.


Inconvénient et extensions

On peut écrire la méthode sous forme matricielle :

X'=AX

où X est le vecteur colonne correspondant à deux lettres à coder simultanément, A est la matrice clé et X' est le vecteur colonne des lettres codées, avec des calculs modulo 26.


Approche matricielle

Intérêt d'utiliser le tableur pour automatiser les calculs.

Sujet charnière entre arithmétique et matrices.

Réinvestissement des congruences.

Introduction du concept de matrice inversible.


Synthèse


5 – La pertinence d'une page Web et

l'algorithme PageRank

World Wide Web : Système hypertexte public permettant de consulter des contenus multimedia par internet. Idée développée par Tim Berners-Lee au Cern en mars 1989. Projet rendu public en août 1991. Ne pas confondre avec internet, réseau physique support de plusieurs protocoles (http, ftp, mail, newsgroup).

Pertinence d'une page Web : Pagerank

Une histoire du Web

1990-1992 : Liste de serveurs par Tim Berners-Lee. 1990 : Archie, liste de serveurs FTP 1993 : Catalogue du Web, W3Catalog (pas de recherche) 1993 : WWW Wanderer, premier robot

Aliweb, référencement par admins 1994 : Webcrawler, robot + interface de recherche

Apparition de Lycos 1995 : Yahoo (catalogue), Altavista Fin 90s : Nombreux moteurs, bulle financière 1998-2000 : Montée en puissance de Google 2011 : Google reçoit toujours 85 % des requêtes


Les moteurs de recherche

Une vision globale, alliant architecture complexe et théorie mathématique approfondie pour la recherche. Théorie basée sur des recherches antérieures. Une approche différente du classement des réponses. La qualité (réelle ou ressentie) des réponses.


Les raisons du succès de Google

Un large éventail de services “annexes”.

Un outil majeur : l’algèbre linéaire

1 2

1 2

1( ) n

n

PR T PR T PR TdPR A d

N L T L T L T


La formule de Brin et Page

Le web est un graphe orienté.


Un exemple

Comptage naïf :


Comptage pondéré :


Une page j est importante si beaucoup de pages importantes pointent vers j. On tient compte de l’importance de la page d’origine i et du nombre de liens qui en sont émis.


Comptage récursif : 1

j ii j il

Plausibilité Robustesse

où

1si

0 sinonii j

i jla


Comptage récursif

1

1n

j i j ii

a j n

Les coefficients vérifient :

1

0 pour tout , et

1 pour tout

i j

n

i jj

a i j

a i

: probabilité d’aller de la page i à la page j, en suivant

un des liens au hasard. On modélise ainsi un surfeur aléatoire.

i ja

W WA


Comptage récursif

La matrice A constituée par les coefficients aij est une matrice stochastique.

Les mesures de pertinences des pages, μi sont solutions

du système linéaire de n équations à n inconnues noté

où W est la matrice ligne ayant pour coefficients les μi

Si l’on note Xp la position du surfeur après p étapes :

1 11

p

n

p p pX ii

P X j P X j P X i

11

n

p i j pi

P X j a P X i


Comptage récursif

c'est-à-dire

En notant Up la matrice ligne des pP X i

1p pU U A

0p

pU U A


Comptage récursif

La suite des matrices lignes Up est donc géométrique :

Les pertinences sont bien définies si la suite (Ap) des puissances de la matrice Ap est convergente.


Limites du comptage récursif

Probabilité c : le surfeur abandonne la page actuelle se téléporte au hasard vers une des n pages du web ; Probabilité 1-c : modélisation précédente.

On obtient :

ou encore

puisque


Comptage récursif avec téléportation

11

1n

p i j pi

cP X j c a P X i

n

11

1n

p i j pi

cP X j c a P X i

n

1

1n

pi

P X i

Notation matricielle, où J désigne la matrice carrée (n,n) dont tous les coefficients sont égaux à 1,

ou encore

avec

1 1p p

cU U J c A

n



1 1p pU c U A L

L=cn(11 .. . 1 )

La suite des matrices lignes Up est donc alors arithmetico-géométrique. Pour démontrer l'existence d'un état stable : on commence par chercher un point fixe : H en posant : , on obtient :

puis

La constante c est un paramètre du modèle. c=0,15 correspond à suivre environ 6 liens en moyenne.

p pV U H

01p p

pV c V A

01p p

pU c U H A H




Exercice

Document ressource Éduscol (juin 2012)

Michael EisermannComment fonctionne Google ?www-fourier.ujf-grenoble.fr/~eiserm

Christiane Rousseau et Yvan Saint-AubinMathématiques et Technologie (Springer)


Bibliographie


6 – Échanges autour de l'évaluation

Documents

Spécialité en Terminale S