these

Description

Universit´e de Nice – Sophia Antipolis´D´epartement de formation doctorale en informatique Ecole doctorale STICUFR SciencesDes piles de sableaux automates de sable`THESEpr´esent´ee et soutenue publiquement le 13 d´ecembre 2006pour l’obtention duDoctorat de l’Universit´e de Nice – Sophia Antipolis(sp´ecialit´e Informatique)parBenoˆıtMassonComposition du juryVal´erie Berthe´ (Directeur de recherches, LIRMM – Rapporteur)Robert Cori (Professeur, LIX – Rapporteur)Bruno Durand (Professeur, LIF – Examinateur)Enrico Formenti (Professeur, I3S – Directeur de th`ese)Jacques Mazoyer (Professeur, LIP – Examinateur)Dominique Rossin (Charg´e de recherches, LIAFA – Rapporteur)Michel Rueher (Professeur, I3S – Examinateur)Laboratoire Informatique, Signaux et Syst`emes de Sophia Antipolis — UMR 6070ourosJeptiensadvàbresremercier.toutlaparticulièrementetmonoublie,dethèse,detsFuneormenti,pterrainourtropajevRemerciementsoirmontoujoursDurandsuyerRetlesmelibsoutenir.êtreSesjourqualitésEnn,henséeumainesm'onm'ontendanrendufamille,(surtroisfoannéesIld'écrireàici,vivre.vJe!vmemoudraisdeégalemenjurytBrunoremercier,VMazoalérieetBerhelthéueher,JeRobremercieerts'êtreCoriérésetourDominiqueprésenRleossindepourj'aiapvpoirtousprisetlequitempstdepreliretmonthèse,manamis,ersairesdelethèse,deetot.. ...

Informations

• Publié par: Metheg
• Nombre de lectures: 39
• Langue: Latin

Extrait

Universit´e de Nice – Sophia Antipolis
´D´epartement de formation doctorale en informatique Ecole doctorale STIC
UFR Sciences
Des piles de sable
aux automates de sable
`THESE
pr´esent´ee et soutenue publiquement le 13 d´ecembre 2006
pour l’obtention du
Doctorat de l’Universit´e de Nice – Sophia Antipolis
(sp´ecialit´e Informatique)
par
BenoˆıtMasson
Composition du jury
Val´erie Berthe´ (Directeur de recherches, LIRMM – Rapporteur)
Robert Cori (Professeur, LIX – Rapporteur)
Bruno Durand (Professeur, LIF – Examinateur)
Enrico Formenti (Professeur, I3S – Directeur de th`ese)
Jacques Mazoyer (Professeur, LIP – Examinateur)
Dominique Rossin (Charg´e de recherches, LIAFA – Rapporteur)
Michel Rueher (Professeur, I3S – Examinateur)
Laboratoire Informatique, Signaux et Syst`emes de Sophia Antipolis — UMR 6070tous
Remerciements
Mazo
Je
noms
tiens
our
?
ersaires
remercier
de
tout
Je
particuli?remen

t
p
mon


pas
de
Bruno
th?se,
hel

s'?tre
F
le
ormenti
p
,
qui
p
th?se,
our
de
a
long
v
ne
oir
mem
toujours
jury
su
,

et
et
ueher
me
remercie
soutenir.
?r?s
Ses
pr?sen
qualit?s
de
h
j'ai
umaines
p
m'on
et
t
t
rendu
t

amis,
trois
le
ann?es
ot...)

serait
?
v
vivre.
mais
Je
ous
v
i
oudrais
bres
?galemen
mon
t
,
remercier
Durand
V

al?rie
yer
Ber

th?
R
,
.
Rob
les
ert
de
Cori
lib
et
p
Dominique
?tre
R
ts
ossin
jour
p
la
our
Enn,
a
une
v
ens?e
oir
our
pris

le

temps
m'on
de

relire
endan
mon

man
famille,

adv
de
(sur
th?se,
terrain
et
fo
p
et
our
Il
leurs
trop
remarques
d'?crire
p
os
ertinen
ici,
tes.
je
Je
v
n'oublie
oublie
pas
!
les
autresii.
Sommaire
.
In
.
tro
.

3.1
1
.
P
.
artie
.
I
.
Piles
.
de
.
sable
.
5
.
Chapitre
.
1
.
Bref
.
historique
.
7
.
1.1
.
D?nitions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
du
.
.
.
24
.
.
.
.
.
orbites
.
.
.
.
.
.
.
.
.
du
.
.
.
38
.
.
.
.
.
usion
.
.
.
.
.
.
.
.
.
de
.
.
.
.
.
.
8
.
1.1.1
.
Piles
.
de
.
sable
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
.
.
.
.
.
.
.
.
28
.
.
.
.
.
.
.
.
.
P
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
du
.
.
.
.
8
.
1.1.2
.
Syst?mes
2.1.3
de
.
piles
.
de
.
sable
.
.
.
.
.
.
.
.
.
.
.
.
2.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.2
.
.
8
.
1.1.3
.
Graphe
.
des
.
orbites
.
.
.
.
.
.
2.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
sym?triques
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Graphe
.
.
.
.
.
.
.
.
.
.
.
.
9
.
1.2
.
R?sultats
30

ts
us
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Longueur
.
.
.
.
.
.
.
.
.
.
.
38
.
.
.
.
.
.
.
18
.
F
.
.
.
.
.
.
.
.
.
.
10
.
1.2.1
.
P
.
oin
.
t
.
xe
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
.
?tude
.
l'algorithme
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
.
Exactitude
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
.
1.2.2
.
Longueur
.
du
.
transitoire
.
.
.
.
.
.
.
.
.
.
22
.
Complexit?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
.
Longueur
.
transitoire
.
.
12
.
Chapitre
.
2
.
Piles
.
de
.
sable
.
g?n?ralis?es
.
15
.
2.1
.
Algorithme
.
de
.

.
du
.
p
.
oin
Chapitre
t
Piles
xe
sable
.
27
.
D?nition
.
SSPM
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.2
.
des
.
.
.
.
.
.
16
.
2.1.1
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3
.
oin
.
xes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
16
Longueur
2.1.2
transitoire
Calcul
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4.1
.
minimale
.
transitoire
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
iii
.(n) 16 n6 24
la
maximale
.
du
.
transitoire
.
.
.
.
p
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
.
.
.
.
p
41
.
3.5
.
P
.
ersp
2.2.2
ectiv
.
es
.
.
.
.
sable
.
.
.
.
.
Arr?t
.
.
.
.
.
.
.
.
.
91
.
?
.
.
.
2.2.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.3
.
ultimemen
.
.
.
Construction
.
.
.
.
.
74
.
?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
.
P
.
artie
.
I
.
I
83
Automates
oin
de
our
sable
.
45
.
Chapitre
.
1
.
D?nitions
.
47
.
1.1
.
Une
.
top
.
ologie
.
p
.
our
.
les
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ultimemen
.
diques
.
stables
.
.
.
.
.
74
.
l'automate
.
.
.
.
.
.
.
.
.
.
.
Sim
.

48

1.2
.
Automates
.
de
.
sable
76
.
erreurs
.
.
.
.
.