Informatique 2004 Concours Instituts Nat. Polytechniques (INP - ENSI)

Description

Concours du Supérieur Concours Instituts Nat. Polytechniques (INP - ENSI). Sujet de Informatique 2004. Retrouvez le corrigé Informatique 2004 sur Bankexam.fr.

Sujets

• Informatique
• 2004

Informations

• Publié par: bankexam
• Publié le: 28 février 2007
• Nombre de lectures: 51
• Langue: Français

Extrait

1
2
Les
calculatrices
sont
inter
dites.
1.2
Repr
esentation
´
graphique
d’un
automate
Les
automates
peuv
ent
etre
ˆ
repr
esent
´
es
´
par
un
sch
ema
´
sui
v
ant
les
con
v
entions
:
N.B.
:
Le
candidat
attachera
la
plus
grande
importance
a
`
la
clart
e,
´
a
`
la
pr
ecision
´
et
a
`
la
concision
de
la
r
edaction.
´
Si
un
candidat
est
amen
e
´
a
`
rep
erer
´
ce
qui
peut
lui
sembler
etre
ˆ
une
erreur
d’
enonc
´
e,
´
il
le
signalera
sur
–
les
v
aleurs
de
la
relation
de
transition
sont
repr
esent
´
ees
´
par
un
graphe
orient
e
´
dont
les
nœuds
sa
copie
et
de
vra
poursui
vre
sa
composition
en
e
xpliquant
les
raisons
des
initiati
v
es
qu’il
a
et
´
e
´
amen
e
´
sont
les
etats
´
et
les
ar
etes
ˆ
sont
les
transitions
;
a
`
prendre.
–
un
etat
´
initial
est
entour
e
´
d’un
cercle
i
;
´
–
un
etat
´
terminal
est
entour
e
´
d’un
double
cercle
t
;
P
R
E
A
M
B
U
L
E
:
Les
deux
parties
qui
composent
ce
sujet
sont
ind
ependantes
´
et
peuv
ent
etre
ˆ
trait
ees
´
par
les
candidats
dans
un
ordre
quelconque.
–
un
etat
´
qui
est
a
`
la
fois
initial
et
terminal
est
entour
e
´
d’un
triple
cercle
it
;
–
une
ar
ete
ˆ
etiquet
´
ee
´
par
le
symbole
e
2
X
v
a
de
l’
etat
´
o
a
`
l’
etat
´
d
si
et
seulement
si
(
o;e;d
)
2
.
P
artie
I
:
Automates
et
lang
ages
Exemple
I.1
L
’automate
E
=
(
Q;X
;I
;T
;
)
avec
:
1
Le
b
ut
de
cet
e
x
ercice
est
l’
etude
´
des
propri
et
´
es
´
des
op
erations
´
de
d
eri
´
v
ation
a
`
gauche
m
:
A
et
a
`
1
droite
A
:m
d’un
automate
fini
A
selon
un
mot
m
.
Q
=
f
A;B
;C
;D
;E
g
X
=
f
a;b
g
I
=
f
A;B
g
T
=
f
D
;E
g
1
A
utomate
fini
=
f
(
A;a;C
)
;
(
A;b;D
)
;
(
B
;a;D
)
;
(
B
;b;B
)
;
(
C
;b;E
)
;
(
D
;a;C
)
;
(
E
;a;C
)
g
Pour
simplifier
les
preuv
es,
nous
nous
limiterons
au
cas
des
automates
finis
semi-ind
eterministes,
´
c’est-
a-dire
`
les
automates
finis
non
d
eterministes
´
qui
ne
contiennent
pas
de
transitions
instantan
ees
´
est
r
epr
esent
´
e
´
par
le
gr
aphe
suivant
:
(ou
-transitions).
Les
r
esultats
´
etudi
´
es
´
s’
etendent
´
au
cadre
des
automates
finis
quelconques.
a
a
A
C
E
b
1.1
Repr
esentation
´
d’un
automate
fini
b
a
a
D
ef
´
.
I.1
(A
utomate
fini
semi-ind
eterministe)
´
Soit
l’alphabet
X
(un
ensemble
de
symboles),
soit
B
D
?
le
symbole
r
epr
esentant
´
le
mot
vide
(
62
X
),
soit
X
l’ensemble
contenant
et
les
mots
compos
es
´
?
b
de
symboles
de
X
(donc
2
X
),
un
automate
fini
semi-ind
eterministe
´
sur
X
est
un
quintuplet
A
=
(
Q;X
;I
;T
;
)
compos
e
´
de
:
–
Un
ensemble
fini
d’
etats
´
:
Q
;
1.3
Langage
r
econnu
par
un
automate
fini
–
Un
ensemble
d’
etats
´
initiaux
:
I
Q
;
?
?
Soit
l’e
xtension
de
a
`
Q
X
Q
d
efinie
´
par
:
–
Un
ensemble
d’
etats
´
terminaux
:
T
Q
;
–
Une
r
elation
de
tr
ansition
confondue
avec
son
gr
aphe
:
Q
X
Q
.
?
8
q
2
Q;
(
q
;
;q
)
2
?
?
?
8
e
2
X
;
8
m
2
X
;
8
o
2
Q;
8
d
2
Q;
(
o;e:m;d
)
2
,
9
q
2
Q;
((
o;e;q
)
2
)
^
((
q
;m;d
)
2
)
Pour
une
transition
(
o;e;d
)
donn
ee,
´
nous
appelons
o
l’origine
de
la
transition,
e
l’
etiquette
´
de
la
transition
et
d
la
destination
de
la
transition.
?
Le
langage
sur
X
reconnu
par
un
automate
fini
est
:
Remarquons
que
est
le
graphe
d’une
application
de
transition
:
Q
X
!
P
(
Q
)
dont
les
v
aleurs
sont
d
efinies
´
par
:
?
?
L
(
A
)
=
f
m
2
X
j
9
o
2
I
;
9
d
2
T
;
(
o;m;d
)
2
g
8
o
2
Q;
8
e
2
X
;
(
o;e
)
=
f
d
2
Q
j
(
o;e;d
)
2
g
Question
I.1
Donner
sans
la
justifier
une
e
xpr
ession
r
eguli
´
er
`
e
ou
ensembliste
r
epr
esentant
´
le
lan-
La
notation
est
plus
adapt
ee
´
que
a
`
la
formalisation
et
la
construction
des
preuv
es
dans
le
cadre
ga
g
e
r
econnu
par
l’automate
E
de
l’e
xemple
I.1.
des
automates
ind
eterministes.
´3
4
´
´
2
Op
erations
de
d
eri
v
ation
P
artie
II
:
Algorithmique
et
programmation
en
CaML
2.1
D
efinitions
´
Cette
partie
doit
etre
ˆ
trait
ee
´
par
les
etudiants
´
qui
ont
utilis
e
´
le
langage
CaML
dans
le
cadre
des
ensei-
Soient
les
op
erations
´
internes
sur
les
automates
finis
semi-ind
eterministes
´
d
efinies
´
par
:
gnements
d’informatique.
Les
fonctions
ecrites
´
de
vront
etre
ˆ
r
ecursi
´
v
es
ou
f
aire
appel
a
`
des
fonctions
auxiliaires
r
ecursi
´
v
es.
Elles
ne
de
vront
pas
utiliser
d’instructions
it
erati
´
v
es
(
for
,
while
,
.
.
.
)
ni
de
´
´
´
D
ef
.
I.2
(D
eri
v
ees
selon
un
mot)
Soient
A
=
(
Q;X
;I
;T
;
)
un
automate
fini
semi-ind
eterministe
´
et
r
ef
´
erences.
´
?
1
1
m
2
X
,
les
automates
m
:
A
(d
erivatio