Cours de mathématique de l'informatique

Informations

• Publié par: Naphug
• Nombre de lectures: 67
• Langue: Français

Extrait

Mathematiques de l’information
Pierre Boulet
[e-mail]
e
DEUG MIAS 2 annee
Mathematiques de l’information { p. 1/111Plan
Automates cellulaires
Reseaux
Reseaux de neurones
RSA
Introduction a la cryptographie
Cout^ des calculs
Generation des cles RSA
Pourquoi RSA fonctionne-t-il ?
Qualites de RSA
Mathematiques de l’information { p. 2/111Automates cellulaires
Mathematiques de l’information { p. 3/111Reseaux d’automates
But de cette partie : illustrer par quelques exemples
comment le developpement du traitement de l’information
depuis un demi-siecle suscite une demarche de modelisation
et d’experimentation comparable a celle de la physique pour
les sciences de la matiere.
type de regles d’evolution
mode d’iteration
secteur applicatif
Mathematiques de l’information { p. 4/111Reseaux cellulaires
de nition : reseau de cellules
toutes identiques
qui peuvent prendre un nombre ni d’etats
temps discretise
iterations paralleles
application d’une regle deterministe faisant intervenir les cellules du
voisinage
Mathematiques de l’information { p. 5/111Voisinages
voisinage propre = voisins autres que soi-m^eme
exemples en dimension 2 :
voisinage de voisinage de
Moore Von Neumann
Mathematiques de l’information { p. 6/111Premier exemple
modele tres pauvre
2 etats : blanc et noir
regles :
blanc ! noir
noir ! blanc
voisinage = la cellule seulement
pour toute con guration : clignotement general
(periode 2)
Mathematiques de l’information { p. 7/111Jeu de la vie
Conway, 1970
modele tres riche
2 etats : vivant et mort
voisinage de Von Neumann propre
regles :
naissance : si exactement 3 voisines fi vivantes fl
survie : si 2 ou 3 voisines fi vivantes fl
sinon : la cellule fi meurt fl
une evolution = une fi generation fl
on suppose la grille in nie
on peut faire tous les calculs avec ce reseau (simule une
machine de Turing universelle)
Mathematiques de l’information { p. 8/111Con gurations interessantes
Stable Clignotant Glisseur
comment faire pour simuler une grille in nie sur un ecran ni ?
Mathematiques de l’information { p. 9/111De nitions formelles
automate A a n entrees :
un ensemble ni S d’etats
un ensemble ni I d’entrees
un ensemble T de regles de transition (ou d’evolution) de la forme
(i ;:::;i ) ! s avec i ;:::;i dans I et s dans S
1 n 1 n
reseau d’automates : ensemble d’automates connectes
evolution parallele, deterministe
soit A (t) l’etat de A a l’instant t ;
i i
si A est connecte a A ;:::;A ;
i j j
1 p
A (t + 1) = T(A (t);:::;A (t))
i j j
1 p
Mathematiques de l’information { p. 10/111