//img.uscri.be/pth/2c4b3e06f53f90de5762b95c01dca9a525888db3
Cette publication est accessible gratuitement
Lire

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

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

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
erivation
´
a
`
gauc
he
selon
m
)
et
A
:m
(d
erivation
´
a
`
dr
oite
selon
F
ormat
de
desciption
d’une
fonction
:
La
description
d’une
fonction,
lorsque
celle-ci
est
demand
ee,
´
m
)
sont
d
efinis
´
par
:
c’est-
a-dire
`
aux
questions
II.23
et
II.29,
doit
au
moins
contenir
:
1
?
m
:
A
=
(
Q;X
;
f
q
2
Q
j
9
i
2
I
;
(
i;m;q
)
2
g
;T
;
)
1.
L
’objectif
g
en
´
eral
´
;
1
?
A
:m
=
(
Q;X
;I
;
f
q
2
Q
j
9
t
2
T
;
(
q
;m;t
)
2
g
;
)
2.
Le
r
ole
ˆ
des
param
etres
`
de
la
fonction
;
1
1
1
1
3.
Les
contraintes
sur
les
v
aleurs
des
param
etres
`
;
Question
I.2
En
consid
er
´
ant
l’e
xemple
I.1,
construir
e
les
automates
a
:
E
,
b
:
E
,
E
:a
et
E
:b
(seuls
les
etats
´
et
les
tr
ansitions
utiles,
c’est-
a-dir
`
e
accessibles
depuis
les
etats
´
initiaux,
de
vr
ont
etr
ˆ
e
4.
Les
caract
eristiques
´
du
r
esultat
´
ren
v
o
y
e
´
par
la
fonction
;
construits).
5.
Le
r
ole
ˆ
des
v
ariables
locales
a
`
la
fonction
;
6.
Le
principe
de
l’algorithme
;
1
1
1
1
Question
I.3
Car
act
eriser
´
les
langa
g
es
r
econnus
par
a
:
E
,
b
:
E
,
E
:a
E
:b
,
par
une
e
xpr
ession
7.
Des
ar
guments
de
terminaison
du
calcul
pour
toutes
les
v
aleurs
des
param
etres
`
qui
v
erifient
´
les
r
eguli
´
er
`
e
ou
ensembliste
.
contraintes
pr
esent
´
ees
´
au
point
3.
2.2
Pr
opri
et
´
es
´
L
’objectif
de
ce
probl
eme
`
est
l’
etude
´
d’une
strat
egie
´
compl
ete
`
et
coh
erente
´
d’interrogation
d’une
?
base
de
connaissances.
Une
base
de
connaissances
est
une
repr
esentation
´
de
relations
logiques
e
xis-
Question
I.4
Montr
er
que
:
si
A
est
un
automate
fini
semi-ind
eterministe
´
et
m
2
X
un
mot,
alor
s
1
1
tant
entre
des
f
aits.
Cette
strat
egie
´
repose
sur
un
algorithme
de
construction
d’une
base
compl
ete,
`
m
:
A
et
A
:m
sont
des
automates
finis
semi-ind
eterministes.
´
coh
erente
´
et
minimale.
Cet
algorithme
qui
pr
eserv
´
e
le
contenu
logique
de
la
base
est
g
en
´
eralement
´
appel
e
´
compl
etion
´
de
la
base.
Question
I.5
Montr
er
que
:
?
?
?
?
?
1
Pr
eliminair
´
e
:
Calcul
des
pr
opositions
8
m
2
X
;
8
n
2
X
;
8
o
2
Q;
8
q
2
Q;
8
d
2
Q;
(
o;m;q
)
2
^
(
q
;n;d
)
2
,
(
o;m:n;d
)
2
La
repr
esentation
´
d’une
base
de
connaissances
repose
sur
le
calcul
des
propositions.
Question
I.6
Soit
A
un
automate
fini
semi-ind
eterministe
´
,
montr
er
que
:
?
?
1
8
m
2
X
;
8
n
2
X
;
n
2
L
(
m
:
A
)
,
m:n
2
L
(
A
)
D
ef
´
.
II.1
(Pr
opositions)
Soit
F
=
f
f
;f
;
:
:
:
g
un
ensemble
d
enombr
´
able
de
symboles,
appel
es
´
faits
0
1
?
?
1
8
m
2
X
;
8
n
2
X
;
n
2
L
(
A
:m
)
,
n:m
2
L
(
A
)
(ou
variables
pr
opositionnelles),
soient
les
constantes
vr
ai
et
faux
not
ees
´
>
;
?
,
soit
l’op
er
´
ateur
unair
e
:
(n
egation),
´
soient
les
op
er
´
ateur
s
binair
es
_
(disjonction),
^
(conjonction),
)
(implication);
l’en-
semble
P
(
F
)
des
pr
opositions
est
le
plus
petit
ensemble
tel
que
:

F
P
(
F
)
;

f>
;
?g
P
(
F
)
;

si
P
2
P
(
F
)
alor
s
:
P
2
P
(
F
)
;
2

si
P
;P
2
P
(
F
)
et
op
2
f_
;
^
;
)g
alor
s
P
op
P
2
P
(
F
)
;
1
2
1
2

les
pr
opositions
de
P
(
F
)
sont
finies,
c’est-
a-dir
`
e
obtenues
par
application
d’un
nombr
e
fini
de
fois
des
r
egles
pr
ec
edentes.
`
´
´
Nous
noterons
les
f
aits
en
utilisant
les
minuscules
de
l’alphabet
romain.
Nous
noterons
les
proposi-
tions
et
les
ensembles
de
f
aits
en
utilisant
les
majuscules
de
l’alphabet
romain.5
6
D
ef
´
.
II.2
(V
aluation)
Soit
B
=
f
0
;
1
g
les
valeur
s
de
v
erit
´
e,
´
une
valuation
est
une
application
2.1
Codage
d’un
fait
:
F
!
B
.
Cette
application
est
etendue
en
une
application
unique
^
:
P
(
F
)
!
B
par
les
egalit
es
:
´
´
´
Un
f
ait
est
repr
esent
´
e
´
par
le
type
de
base
string
.
^
(
>
)
=
1
^
(
?
)
=
0
type
fait
==
string;;
^
(
f
)
=
(
f
)
i
i
^
(
:
P
)
=
1
^
(
P
)
^
(
P
_
P
)
=
1
(1
^
(
P
))
(1
^
(
P
))
1
2
1
2
2.2
Codage
d’un
ensemble
de
faits
^
(
P
^
P
)
=
^
(
P
)
^
(
P
)
1
2
1
2
^
(
P
)
P
)
=
1
^
(
P
)
(1
^
(
P
))
1
2
1
2
Nous
allons
utiliser
un
codage
e
xtr
emement
ˆ
simple
:
un
ensemble
est
une
liste
contenant
e
xac-
tement
un
e
x
emplaire
de
chaque
el
´
ement
´
contenu
dans
l’ensemble.
Les
op
erations
´
de
manipulation
´
D
ef
´
.
II.3
(
Equi
v
alence)
Soient
deux
pr
opositions
P
;P
el
´
ements
´
de
P
(
F
)
,
P
est
equivalente
´
a
`
P
1
2
1
2
d’un
ensemble
de
vront
pr
eserv
´
er
cette
propri
et
´
e.
´
(not
ee
´
P
P
)
si
et
seulement
si
pour
toute
valuation
,
^
(
P
)
=
^
(
P
)
.
1
2
1
2
Un
ensemble
de
f
aits
est
repr
esent
´
e
´
par
le
type
faits
equi
´
v
alent
a
`
une
liste
de
fait
.
Question
II.1
Montr
er
que
a
)
b
:
a
_
b
.
type
faits
==
fait
list;;
D
ef
´
.
II.4
(T
autologie)
Soit
une
pr
oposition
P
2
P
(
F
)
,
P
est
une
tautolo
gie
si
et
seulement
si
P
>
.
Le
parcours
d’un
ensemble
sera
donc
ef
fectu
e
´
de
la
m
eme
ˆ
mani
ere
`
que
celui
d’une
liste.
Nous
allons
maintenant
d
efinir
´
plusieurs
op
erations
´
sur
les
ensembles
de
f
aits
qui
pourront
etre
ˆ
D
ef
´
.
II.5
(Pr
oposition
absurde)
Soit
une
pr
oposition
P
2
P
(
F
)
,
P
est
absur
de
si
et
seulement
si
utilis
ees
´
dans
la
suite
du
sujet.
Ces
op
erations
´
seront
ensuite
etendues
´
aux
ensembles
de
connais-
P
?
.
sances.
Nous
supposons
que
toutes
les
listes
repr
esentant
´
des
ensembles,
qui
sont
pass
ees
´
comme
param
etres
`
D
ef
´
.
II.6
(Litt
eral)
´
Un
litt
er
´
al
est
une
pr
oposition
qui
pr
end
l’une
des
formes
suivantes
:
des
fonctions,
ne
contiennent
au
plus
qu’une
fois
chaque
el
´
ement.
´

un
fait
(litt
er
´
al
positif)
;

la
n
egation
´
d’un
fait
(litt
er
´
al
n
egatif).
´
2.3
Op
eration
´
sur
la
structur
e
d’ensemble
D
ef
´
.
II.7
(Clause,
clause
duale)
Une
clause
est
une
disjonction
de
litt
er
´
aux
deux
a
`
deux
distincts.
Une
clause
duale
est
une
conjonction
de
litt
er
aux
deux
a
deux
distincts.
´
`
Pour
les
calculs
de
comple
xit
e,
´
nous
noterons
j
E
j
la
taille
de
l’ensemble
E
,
c’est-
a-dire
`
le
nombre
de
f
aits
qu’il
contient.
Exemple
II.1
c
_
:
b
_
a
est
une
clause
.
b
^
c
^
:
a
est
une
clause
duale
.
D
ef
´
.
II.8
(F
orme
conjoncti
v
e,
disjoncti
v
e)
Une
forme
conjonctive
est
une
conjonction
de
clauses.
2.3.1
A
ppartenance
a
`
un
ensemble
Une
forme
disjonctive
est
une
disjonction
de
clauses
duales.
Une
premi
ere
`
op
eration
´
consiste
a
`
tester
l’appartenance
d’un
f
ait
a
`
un
ensemble.
Exemple
II.2
(
a
_
:
c
)
^
:
b
est
une
forme
conjonctive
.
c
_
(
:
a
^
b
)
est
une
forme
disjonctive
.
´
Question
II.3
Ecrir
e
en
CaML
une
fonction
appartenance
de
type
fait
->
faits
->
bool
Question
II.2
Soit
la
pr
oposition
P
=
(
a
^
c
)
?
)
^
(
a
)
b
)
^
(
>
)
b
_
d
)
,
tr
ansformer
P
en
une
telle
que
l’appel
(appartenance
f
E)
r
en
voie
la
valeur
true
si
l’ensemble
E
contient
le
fait
f
forme
conjonctive
C
,
puis
en
une
forme
disjonctive
D
telles
que
P
C
D
.
V
ous
utiliser
ez
pour
et
la
valeur
false
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
cela
les
formules
de
De
Mor
gan.
r
ecur
´
sives.
Question
II.4
Donner
un
e
xemple
de
valeur
s
des
par
am
etr
es
f
et
E
de
la
fonction
appartenance
`
2
Repr
esentation
´
et
codage
d’un
ensemble
de
faits
qui
corr
espond
au
pir
e
cas
en
nombr
e
d’appels
r
ecur
´
sifs
ef
fectu
es.
´
Calculer
une
estimation
de
la
comple
xit
e
´
dans
le
pir
e
cas
de
la
fonction
en
La
repr
´
et
les
op
erations
´
de
manipulation
des
bases
de
connaissances
reposent
sur
la
fonction
de
la
taille
de
l’ensemble
E
.
Cette
estimation
ne
pr
endr
a
en
compte
que
le
nombr
e
d’appels
structure
d’ensemble.
Nous
allons
dans
une
premi
ere
`
etape
´
etudier
´
un
codage
de
cette
structure
qui
r
ecur
´
sifs
ef
fectu
es.
´
contiendra
des
f
aits.
Cette
structure
sera
ensuite
adapt
ee
´
aux
connaissances.7
8
2.3.2
Ajout
dans
un
ensemble
2.3.6
A
utr
es
op
erations
´
pr
ed
´
efinies
´
Nous
supposons
pr
ed
´
efinies
´
les
fonctions
sui
v
antes
pour
les
ensembles,
dont
le
calcul
se
termine
La
deuxi
eme
`
op
eration
´
est
l’ajout
d’un
f
ait
a
`
un
ensemble.
quelles
que
soient
les
v
aleurs
de
leurs
param
etres.
`
Elles
pourront
ev
´
entuellement
etre
ˆ
utilis
ees
´
dans
les
r
eponses
´
aux
questions
:
´
Question
II.5
Ecrir
e
en
CaML
une
fonction
ajout
de
type
fait
->
faits
->
faits
telle

union
:
faits
->
faits
->
faits
telle
que
l’appel
(union
E1
E2)
ren
v
oie
un
que
l’appel
(ajout
f
E)
r
en
voie
un
ensemble
contenant
les
m
emes
ˆ
que
l’ensemble
E
ainsi
ensemble
contenant
les
f
aits
contenus
dans
E1
ainsi
que
les
f
aits
contenus
dans
E2
;
que
le
fait
f
s’il
ne
figur
ait
pas
d
ej
´
a
`
dans
E
.
L
’ensemble
r
en
voy
e
´
contiendr
a
e
xactement
une
fois
le
fait
f
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.

intersection
:
faits
->
faits
->
faits
telle
que
l’appel
(intersection
E1
E2)
ren
v
oie
un
ensemble
contenant
les
f
aits
contenus
a
`
la
fois
dans
E1
et
dans
E2
.
2.3.3
Inclusion
entr
e
deux
ensembles
La
troisi
eme
`
op
eration
´
est
le
test
d’inclusion
du
contenu
de
deux
ensembles.
3
Repr
esentation
´
et
codage
d’une
connaissance
3.1
Repr
´
d’une
connaissance
´
Question
II.6
Ecrir
e
en
CaML
une
fonction
inclusion
de
type
faits
->
faits
->
bool
telle
que
l’appel
(inclusion
E1
E2)
r
en
voie
la
valeur
true
si
l’ensemble
E2
contient
au
moins
D
ef
´
.
II.9
(Connaissance)
Une
connaissance
not
ee
´
=
H

C
est
compos
ee
´
de
deux
ensembles
les
m
emes
ˆ
faits
que
l’ensemble
E1
et
la
valeur
false
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
finis
de
faits
(ou
variables
pr
opositionnelles)
:
les
hypoth
eses
`
H
=
f
h
g
et
les
conclusions
C
=
i
i
2
I
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
f
c
g
.
j
j
2
J
Nous
noterons
les
connaissances
en
utilisant
les
minuscules
de
l’alphabet
grec.
Question
II.7
Donner
un
e
xemple
de
valeur
s
des
par
am
etr
`
es
E1
et
E2
de
la
fonction
inclusion
qui
corr
espond
au
pir
e
cas
en
nombr
e
d’appels
r
ecur
´
sifs
ef
fectu
es.
´
D
ef
´
.
II.10
(Inter
pr
etation
´
logique)
L
’interpr
etation
´
lo
gique
,
not
ee
´
I
(
)
,
d’une
connaissance
Calculer
une
estimation
de
la
comple
xit
e
dans
le
pir
e
cas
de
la
fonction
inclusion
en
fonction
´
=
f
h
g

f
c
g
est
:
i
i
2
I
j
j
2
J
des
tailles
des
ensembles
E1
et
E2
.
Cette
estimation
ne
pr
endr
a
en
compte
que
le
nombr
e
d’appels
r
ecur
´
sifs
ef
fectu
es.
´
^
_
I
(
)
=
(
>
^
h
)
)
(
?
_
c
)
i
j
i
2
I
j
2
J
´
2.3.4
Egalit
e
´
entr
e
deux
ensembles
Intuitivement,
elle
signifie
que
sous
les
hypoth
eses
`
de
f
h
g
,
nous
pouvons
d
eduir
´
e
une
des
i
i
2
I
conclusions
de
f
c
g
.
>
permet
de
tr
aiter
le
cas
I
=
;
.
?
permet
de
tr
aiter
le
cas
J
=
;
.
Notons
j
j
2
J
La
quatri
eme
`
op
eration
´
est
le
test
d’
egalit
´
e
´
du
contenu
de
deux
ensembles.
que
:
W

I
(
;

f
c
g
)
=
>
)
(
?
_
c
)
;
j
j
2
J
j
j
2
J
´
V
Question
II.8
Ecrir
e
en
CaML
une
fonction
egalite
de
type
faits
->
faits
->
bool
telle

I
(
f
h
g

;
)
=
(
>
^
h
)
)
?
;
i
i
2
I
i
i
2
I
que
l’appel
(egalite
E1
E2)
r
en
voie
la
valeur
true
si
les
deux
ensembles
E1
et
E2
contiennent

I
(
;

;
)
=
>
)
?
.
e
xactement
les
m
emes
ˆ
faits
et
la
valeur
false
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
des
fonctions
auxiliair
es
r
ecur
sives.
`
´
Exemple
II.3
Les
formules
lo
giques
suivantes
sont
des
connaissances
:

f
a
g

f
b
g
;
2.3.5
Soustraction
de
deux
ensembles

f
a,
c
g

;
;

;

f
b,
d
g
.
La
derni
ere
`
op
eration
´
etudi
´
ee
´
est
la
construction
d’un
ensemble
r
esultant
´
de
la
soustraction
d’un
ensemble
depuis
un
autre
ensemble.
Question
II.10
Soit
=
f
h
g

f
c
g
une
connaissance
quelconque
,
donner
une
clause
P
telle
i
i
2
I
j
j
2
J
que
I
(
)
P
.
´
Question
II.9
Ecrir
e
en
CaML
une
fonction
soustraction
de
type
faits
->
faits
->
´
D
ef
.
II.11
(Connaissance
absurde)
Une
connaissance
est
absur
de
si
et
seulement
si
son
interpr
etation
´
faits
telle
que
l’appel
(soustraction
E1
E2)
r
en
voie
un
ensemble
contenant
les
faits
qui
I
(
)
est
absur
de
.
sont
contenus
dans
E1
et
ne
sont
pas
contenus
dans
E2
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
Question
II.11
Montr
er
que
la
seule
connaissance
absur
de
est
;

;
.9
10
3.2
Codage
d’une
connaissance
Exemple
II.4
La
base
compos
ee
´
des
connaissances
de
l’e
xemple
II.3
ser
a
r
epr
esent
´
ee
´
par
la
valeur
:
[
Pour
les
v
ariables
ou
les
constantes
dont
le
nom
est
pris
dans
l’alphabet
grec
(
,
.
.
.
),
l’identifiant
en
(
[
"a"
]
,
[
"b"
]
)
;
CaML
sera
leur
nom
en
toute
lettre
(
gamma
,
.
.
.
).
(
[
"a"
;
"c"
]
,
[]
)
;
(
[
]
,
[
"b"
;
"d"
]
)
Une
connaissance
est
repr
esent
´
ee
´
par
le
type
connaissance
equi
´
v
alent
a
`
un
couple
compos
e
´
]
de
deux
ensembles
de
f
aits.
Une
base
est
un
ensemble
de
connaissances.
Il
est
donc
n
ecessaire
´
d’adapter
les
op
erations
´
d
efinies
´
type
connaissance
==
faits
*
faits
;;
dans
la
sous-section
2.2
sur
les
ensembles
de
f
aits.
Nous
supposons
pr
ed
´
efinies
´
les
fonctions
sui
v
antes
pour
les
bases,
dont
le
calcul
se
termine
´
Question
II.12
Ecrir
e
en
CaML
une
fonction
comparaison
de
type
connaissance
->
quelles
que
soient
les
v
aleurs
de
leurs
param
etres.
`
Elles
pourront
ev
´
entuellement
etre
ˆ
utilis
ees
´
dans
connaissance
->
bool
telle
que
l’appel
(comparaison
gamma1
gamma2)
r
en
voie
la
les
r
eponses
´
aux
questions
:
valeur
true
si
les
deux
connaissances
gamma1
et
gamma2
contiennent
e
xactement
les
m
emes
ˆ
hy-
poth
eses
`
et
conclusions
et
la
valeur
false
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel

appartenanceB
:
connaissance
->
base
->
bool
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.

ajoutB
:
connaissance
->
base
->
base

inclusionB
:
base
->
base
->
bool
4
Repr
esentation
´
et
codage
d’une
base
de
connaissances

egaliteB
:
base
->
base
->
bool

unionB
:
base
->
base
->
base
4.1
Repr
´
d’une
base
de
connaissances

intersectionB
:
base
->
base
->
base
´
D
ef
.
II.12
(Base
de
connaissances)
Une
base
de
est
un
ensemble
fini
de
connais-

soustractionB
:
base
->
base
->
base
sances
=
f
g
.
k
k
2
K
´
Nous
noterons
les
bases
de
connaissances
en
utilisant
les
majuscules
de
l’alphabet
grec.
5
Elimination
des
tautologies
Une
base
de
connaissances
peut
contenir
des
connaissances
inutiles,
c’est-
a-dire
`
qui
n’apportent
D
ef
´
.
II.13
(Inter
pr
etation
´
logique)
L
’interpr
etation
´
lo
gique
,
not
ee
´
I
( )
,
d’une
base
=
f
g
k
k
2
K
aucune
information
pertinente
lors
d’une
interrogation,
par
e
x
emple
les
tautologies.
Pour
r
eduire
´
la
est
d
efinie
´
par
:
taille
de
la
base
et
les
co
uts
ˆ
de
l’op
eration
´
d’interrogation,
nous
nous
int
eressons
´
a
`
l’
elimination
´
des
^
tautologies.
I
( )
=
>
^
I
(
)
k
k
2
K
D
ef
´
.
II.15
(T
autologie)
Une
connaissance
est
une
tautolo
gie
si
et
seulement
si
son
interpr
etation
´
Elle
corr
espond
a
`
la
conjonction
des
interpr
etations
´
lo
giques
de
c
haque
connaissance
.
I
(
)
est
une
tautolo
gie
.
Notons
que
:
I
(
;
)
=
>
.
Question
II.14
Quelles
sont
les
tautolo
gies
parmi
les
connaissances
suivantes
(justifier
vos
r
eponses)
´
:
Question
II.13
Soit
=
f
g
avec
=
f
h
g

f
c
g
une
base
de
connaissances
quel-
k
k
2
K
k
i
i
2
I
j
j
2
J
k
k
conque
,
donner
une
forme
conjonctive
C
telle
que
I
( )
C
.

=
f
a;b
g

f
c
g
;
1

=
f
a
g

f
a
g
;
2
´
D
ef
´
.
II.14
(
Equi
v
alence)
Soient
deux
bases
et
,
est
equivalente
´
a
`
(not
ee
´
)
si
et
1
2
1
2
1
2

=
f
b
g

f
b;c
g
;
3
seulement
si
I
(
)
I
(
)
.
1
2

=
f
a;c
g

f
c
g
;
4

=
f
b
g

;
;
5
4.2
Codage
d’une
base
de
connaissances

=
;

f
c
g
.
6
Une
base
de
connaissances
est
repr
esent
´
ee
´
par
le
type
base
equi
´
v
alent
a
`
une
liste
de
connais-
sances.
Question
II.15
Donner
une
r
elation
entr
e
les
hypoth
eses
`
et
les
conclusions
d’une
connaissance
qui
soit
une
condition
n
ecessair
´
e
et
suf
fisante
pour
que
cette
connaissance
soit
une
tautolo
gie
.
Donner
type
base
==
connaissance
list;;
une
pr
euve
de
cette
condition.6
11
12
´
Nous
supposons
pr
ed
´
efinie
´
la
fonction
tautologie
de
type
connaissance
->
bool
telle
Question
II.20
Ecrir
e
en
CaML
une
fonction
absorbable
de
type
connaissance
->
base
que
l’appel
(tautologie
gamma)
ren
v
oie
la
v
aleur
true
si
la
gamma
est
une
->
bool
telle
que
l’appel
(absorbable
gamma
Omega)
r
en
voie
la
valeur
true
si
la
base
tautologie
et
la
v
aleur
false
sinon.
Son
calcul
se
termine
quelles
que
soient
les
v
aleurs
de
son
Omega
contient
une
connaissance
plus
g
en
´
er
´
ale
que
gamma
et
la
valeur
false
sinon.
Cette
fonction
param
etre.
`
Elle
pourra
ev
´
entuellement
etre
ˆ
utilis
ee
´
dans
les
r
eponses
´
aux
questions.
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
Nous
supposons
pr
ed
´
efinie
´
la
fonction
minimisation
de
type
base
->
base
telle
que
l’ap-
Question
II.16
Soit
une
base
et
une
tautolo
gie
,
montr
er
que
[
f
g
.
pel
(minimisation
Omega)
ren
v
oie
.
Son
calcul
se
termine
quelles
que
soient
les
v
aleurs
de
son
param
etre.
`
Elle
pourra
ev
´
entuellement
etre
ˆ
utilis
ee
´
dans
les
r
eponses
´
aux
questions.
D
ef
´
.
II.16
Soit
une
base
,
nous
noter
ons
]
[
la
base
priv
ee
de
ses
tautolo
gies,
c’est-
a-dir
e
:
´
`
]
[
=
f
2
j
6
>g
´
7
Compl
etion
d’une
base
de
connaissances
Nous
pouvons
d
eduir
´
e
de
la
question
II.16
que
]
[
.
La
compl
etion
´
d’une
base
de
connaissances
consiste
a
`
construire
l’ensemble
de
toutes
les
connais-
´
sances
qui
peuv
ent
etre
ˆ
d
eduites
´
d’une
base
donn
ee.
´
Cette
op
eration
´
permet
ensuite
de
r
eduire
´
les
Question
II.17
Ecrir
e
en
CaML
une
fonction
elimination
de
type
base
->
base
telle
que
co
uts
ˆ
d’interrogation
de
la
base.
l’appel
(elimination
Omega)
r
en
voie
une
base
de
connaissances
contenant
les
m
emes
ˆ
connais-
sances
que
]
[
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
D
ef
´
.
II.19
(D
eduction
´
de
connaissances)
Soient
les
connaissances
=
H

C
et
=
H

C
,
1
1
1
2
2
2
l’op
er
´
ateur
B
de
d
eduction
´
de
connaissances
construit
une
base
not
ee
´
B
et
d
efinie
´
par
:
1
2
6
Minimisation
d’une
base
de
connaissances
B
=
f
(
H
n
f
f
g
)
[
H

C
[
(
C
n
f
f
g
)
j
f
2
H
\
C
g
1
2
1
2
1
2
1
2
Une
base
de
connaissances
peut
contenir
des
redondantes,
en
particulier
,
elle
peut
Notons
que
B
=
;
si
H
\
C
=
;
.
contenir
des
plus
g
en
´
erales
´
que
d’autres.
Pour
r
eduire
´
la
taille
de
la
base
et
les
co
uts
ˆ
1
2
1
2
L
’ensemble
des
connaissances
qui
peuvent
etr
ˆ
e
d
eduites
´
d’une
base
est
l’ensemble
des
connais-
de
l’op
eration
´
d’interrogation,
nous
nous
int
eressons
´
a
`
la
minimisation
de
la
base,
c’est-
a-dire
`
a
`
ne
conserv
er
que
les
connaissances
les
plus
g
en
´
erales.
´
sances
construites
par
application
d’un
nombr
e
quelconque
de
fois
de
l’op
er
´
ateur
B
a
`
partir
des
connaissances
de
.
D
ef
´
.
II.17
Une
connaissance
=
H

C
est
dite
plus
g
en
´
er
´
ale
qu’une
connaissance
1
1
1
=
H

C
si
et
seulement
si
H
H
et
C
C
.
Cette
r
elation
ser
a
not
ee
´
.
Question
II.21
Appliquer
l’op
er
´
ateur
B
sur
les
connaissances
suivantes
(ne
donner
que
les
r
esultats
´
2
2
2
1
2
1
2
2
1
dif
f
er
´
ents
de
;
)
:
Question
II.18
Donner
les
r
elations
entr
e
les
connaissances
suivantes
:

=
f
a;b
g

f
c;d
g
;
1

=
f
a;b
g

f
c;d
g
;
1

=
f
b;c
g

f
e
g
;
2

=
f
a;c
g

f
b;d
g
;
2

=
f
e
g

;
;
3

=
f
a
g

f
d
g
;
3

=
;

f
b;c
g
.
4

=
f
c
g

f
b;d
g
;
4

=
;

;
.
Question
II.22
Soient
les
connaissances
=
H

C
et
=
H

C
,
montr
er
que
si
1
1
1
2
2
2
5
j
H
\
C
j
>
1
alor
s
B
ne
contient
que
des
tautolo
gies.
Que
peut-on
en
conclur
e
?
1
2
1
2
Question
II.19
Soient
deux
connaissances
et
,
montr
er
que
les
bases
f
;
g
et
f
g
sont
1
2
1
2
1
La
composition
d’une
connaissance
et
d’une
base
consiste
a
`
appliquer
l’op
erateur
´
de
d
eduction
´
equivalentes
si
et
seulement
si
.
P
our
cela,
vous
pouvez
consid
er
er
une
valuation
et
en-
´
´
2
1
B
sur
et
sur
chaque
de
.
visa
g
er
les
dif
f
er
´
ents
cas
possibles.
Nous
souhaitons
ecrire
´
une
fonction
composition
qui
prend
en
param
etre
`
une
connaissance
et
une
base
et
qui
construit
une
nouv
elle
base
contenant
les
connaissances
r
esultant
´
de
la
compo-
D
ef
´
.
II.18
(Base
minimale)
Soit
une
base
de
connaissance
,
la
base
minimale
associ
ee
a
´
`
sition
de
gamma
a
v
ec
chaque
connaissance
de
la
base
Omega
.
Cette
fonction
de
vra
etre
ˆ
r
ecursi
´
v
e
ou
est
d
efinie
´
par
:
f
aire
appel
a
`
des
fonctions
auxiliaires
r
ecursi
´
v
es.
=
f
2
j
8
2
;
=
)
g
Question
II.23
D
ecrir
´
e
cette
fonction
composition
et
e
xpliquer
son
algorithme
selon
le
format
Nous
pouvons
d
eduir
´
e
de
la
question
II.19
que
.
pr
esent
´
e
´
en
pa
g
e
4.13
14
´
Question
II.24
Ecrir
e
en
CaML
cette
fonction
composition
de
type
connaissance
->
base
8
Interr
ogation
d’une
base
->
base
telle
que
l’appel
(composition
gamma
Omega)
r
en
voie
une
base
contenant
les
Les
connaissances
contenues
dans
la
base
etablissent
´
un
lien
entre
des
f
aits
hypoth
eses
`
et
des
connaissances
r
esultant
´
de
la
composition
de
avec
les
connaissances
de
la
base
Omega
.
f
aits
conclusions
.
Intuiti
v
ement,
l’interrogation
de
la
base
consiste
a
`
:
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
Nous
supposons
pr
ed
´
efinie
´
la
fonction
deduction
de
type
base
->
base
telle
que
l’appel

compl
eter
´
la
base
(v
oir
section
7),
minimiser
la
base
compl
et
´
ee
´
(v
oir
section
6)
et
en
eliminer
´
(deduction
Omega)
ren
v
oie
une
base
de
connaissances
qui
contient
les
connaissances
de
la
base
les
tautologies
(v
oir
section
5)
;
Omega
ainsi
que
le
r
esultat
´
des
compositions
deux
a
`
deux
des
connaissances
de
Omega
.
Son
calcul

fournir
une
liste
de
f
aits
vrais
et
une
liste
de
f
aits
faux
;
se
termine
quelles
que
soient
les
v
aleurs
de
son
param
etre.
`
Elle
pourra
ev
´
entuellement
etre
ˆ
utilis
ee
´

int
egrer
´
ces
f
aits
dans
la
base
compl
et
´
ee
´
;
dans
les
r
eponses
´
aux
questions.

rendre
la
base
obtenue
minimale
(v
oir
section
6)
pour
obtenir
la
r
eponse
´
a
`
la
requ
ete.
ˆ
Question
II.25
Soient
deux
connaissances
=
H

C
et
=
H

C
telles
que
H
\
C
=
f
f
g
,
1
1
2
2
2
2
1
2
D
efinissons
´
ceci
formellement
:
montr
er
que
les
bases
f
;
g
[
B
et
f
;
g
sont
equivalentes.
´
1
2
1
2
1
2
D
ef
´
.
II.20
(Interr
ogation
d’une
base)
Soit
une
base
,
la
r
eponse
´
a
`
la
r
equ
ete
ˆ
compos
ee
´
des
faits
Question
II.26
Soit
une
base
de
connaissances
quelconque
,
soit
la
suite
f
g
d
efinie
´
par
:
i
vr
ais
V
et
des
faits
faux
F
est
la
base
d
efinie
´
par
:
V
;F
8
=
<
0
[
=
f
(
H
n
V
)

(
C
n
F
)
j
H

C
2
]
[
g
=
[
B
i
+1
i
i
j
V
;F
:
2
;
2
i
j
i
Question
II.31
Soit
la
base
de
connaissances
pr
opos
ee
´
a
`
la
question
II.27,
construir
e
la
r
eponse
´
a
`
Nous
admettr
ons
que
le
r
esultat
´
de
la
question
II.25
peut
etr
ˆ
e
etendu
´
a
`
:
8
i
2
N
;
.
i
+1
i
la
r
equ
ete
ˆ
V
=
f
b
g
;F
=
f
d
g
.
1.
Montr
er
que
la
suite
f
g
est
cr
oissante
;
i
Question
II.32
Montr
er
que
]
(
)
[
.
2.
Montr
er
que
:
9
k
2
N
;
=
(soit
l
=
min
f
k
2
N
j
=
g
,
nous
noter
ons
alor
s
k
+1
k
k
+1
k
V
;F
V
;F
=
et
nous
appeler
ons
la
compl
etion
de
la
base
)
;
´
l
3.
Montr
er
que
.
Question
II.33
Montr
er
que
(
)
.
V
;F
V
;F
Question
II.27
Calculer
la
compl
etion
´
de
la
base
contenant
les
connaissances
suivantes
:
´
Question
II.34
Ecrir
e
en
CaML
une
fonction
interrogation
de
type
faits
->
faits
->

=
f
a;b
g

f
c;d
g
;
1
base
->
base
telle
que
l’appel
(interrogation
V
F
Omega)
r
en
voie
une
base
de
connais-

=
f
b;c
g

f
e
g
;
2
sances
contenant
les
m
emes
ˆ
connaissances
que
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e

=
f
e
g

;
.
V
;F
3
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
L

elimination
´
des
tautologies
et
la
minimisation
de
la
base
obtenue
permettent
ensuite
de
r
eduire
´
la
taille
de
la
base
et
les
co
uts
ˆ
d’interrogation.
´
Question
II.28
Eliminer
les
tautolo
gies
et
minimiser
la
r
eponse
´
que
vous
avez
pr
opos
ee
´
pour
la
question
pr
ec
´
edente
´
.
Nous
souhaitons
ecrire
´
une
fonction
completion
qui
prend
en
param
etre
`
une
base
et
qui
construit
une
nouv
elle
base
contenant
les
m
emes
ˆ
connaissances
que
.
Cette
fonction
de
vra
etre
ˆ
r
ecursi
´
v
e
ou
f
aire
appel
a
`
des
fonctions
auxiliaires
r
ecursi
´
v
es.
Question
II.29
D
ecrir
´
e
cette
fonction
completion
et
e
xpliquer
son
algorithme
selon
le
format
pr
esent
´
e
´
en
pa
g
e
4.
´
Question
II.30
Ecrir
e
en
CaML
cette
fonction
completion
de
type
base
->
base
telle
que
l’appel
(completion
Omega)
r
en
voie
une
base
de
connaissances
contenant
les
m
emes
ˆ
connais-
sances
que
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.15
16
D
ef
´
.
II.2
(V
aluation)
Soit
B
=
f
0
;
1
g
les
valeur
s
de
v
erit
´
e,
´
une
valuation
est
une
application
P
artie
II
:
Algorithmique
et
programmation
en
P
ASCAL
:
F
!
B
.
Cette
application
est
etendue
en
une
application
unique
^
:
P
(
F
)
!
B
par
les
egalit
es
:
´
´
´
Cette
partie
doit
etre
ˆ
trait
ee
´
par
les
etudiants
´
qui
ont
utilis
e
´
le
langage
P
ASCAL
dans
le
cadre
des
^
(
>
)
=
1
enseignements
d’informatique.
Les
fonctions
ecrites
´
de
vront
etre
ˆ
r
ecursi
´
v
es
ou
f
aire
appel
a
`
des
^
(
?
)
=
0
fonctions
auxiliaires
r
ecursi
´
v
es.
Elles
ne
de
vront
pas
utiliser
d’instructions
it
erati
´
v
es
(
for
,
while
,
^
(
f
)
=
(
f
)
i
i
repeat
,
.
.
.
).
^
(
:
P
)
=
1
^
(
P
)
^
(
P
_
P
)
=
1
(1
^
(
P
))
(1
^
(
P
))
1
2
1
2
F
ormat
de
desciption
d’une
fonction
:
La
description
d’une
fonction,
lorsque
celle-ci
est
demand
ee,
´
^
(
P
^
P
)
=
^
(
P
)
^
(
P
)
1
2
1
2
c’est-
a-dire
`
aux
questions
II.23
et
II.29,
doit
au
moins
contenir
:
^
(
P
)
P
)
=
1
^
(
P
)
(1
^
(
P
))
1
2
1
2
1.
L
’objectif
g
en
´
eral
´
;
´
D
ef
´
.
II.3
(
Equi
v
alence)
Soient
deux
pr
opositions
P
;P
el
´
ements
´
de
P
(
F
)
,
P
est
equivalente
´
a
`
P
2.
Le
r
ole
ˆ
des
param
etres
`
de
la
fonction
;
1
2
1
2
(not
ee
´
P
P
)
si
et
seulement
si
pour
toute
valuation
,
^
(
P
)
=
^
(
P
)
.
1
2
1
2
3.
Les
contraintes
sur
les
v
aleurs
des
param
etres
`
;
4.
Les
caract
eristiques
´
du
r
esultat
´
ren
v
o
y
e
´
par
la
fonction
;
Question
II.1
Montr
er
que
a
)
b
:
a
_
b
.
5.
Le
r
ole
ˆ
des
v
ariables
locales
a
`
la
fonction
;
6.
Le
principe
de
l’algorithme
;
D
ef
´
.
II.4
(T
autologie)
Soit
une
pr
oposition
P
2
P
(
F
)
,
P
est
une
tautolo
gie
si
et
seulement
si
7.
Des
ar
guments
de
terminaison
du
calcul
pour
toutes
les
v
aleurs
des
param
etres
`
qui
v
erifient
´
les
P
>
.
contraintes
pr
esent
´
ees
´
au
point
3.
D
ef
´
.
II.5
(Pr
oposition
absurde)
Soit
une
pr
oposition
P
2
P
(
F
)
,
P
est
absur
de
si
et
seulement
si
L
’objectif
de
ce
probl
eme
`
est
l’
etude
´
d’une
strat
egie
´
compl
ete
`
et
coh
erente
´
d’interrogation
d’une
P
?
.
base
de
connaissances.
Une
base
de
connaissances
est
une
repr
esentation
´
de
relations
logiques
e
xis-
tant
entre
des
f
aits.
Cette
strat
egie
´
repose
sur
un
algorithme
de
construction
d’une
base
compl
ete,
`
D
ef
´
.
II.6
(Litt
eral)
´
Un
litt
er
´
al
est
une
pr
oposition
qui
pr
end
l’une
des
formes
suivantes
:
coh
erente
´
et
minimale.
Cet
algorithme
qui
pr
eserv
´
e
le
contenu
logique
de
la
base
est
g
en
´
eralement
´

un
fait
(litt
er
´
al
positif)
;
appel
e
´
compl
etion
´
de
la
base.

la
n
egation
´
d’un
fait
(litt
er
´
al
n
egatif).
´
1
Pr
eliminair
´
e
:
Calcul
des
pr
opositions
D
ef
´
.
II.7
(Clause,
clause
duale)
Une
clause
est
une
disjonction
de
litt
er
´
aux
deux
a
`
deux
distincts.
Une
clause
duale
est
une
conjonction
de
litt
er
aux
deux
a
deux
distincts.
´
`
La
repr
esentation
´
d’une
base
de
connaissances
repose
sur
le
calcul
des
propositions.
Exemple
II.1
c
_
:
b
_
a
est
une
clause
.
b
^
c
^
:
a
est
une
clause
duale
.
´
D
ef
.
II.1
(Pr
opositions)
Soit
F
=
f
f
;f
;
:
:
:
g
un
ensemble
d
enombr
´
able
de
symboles,
appel
es
´
faits
0
1
(ou
variables
pr
opositionnelles),
soient
les
constantes
vr
ai
et
faux
not
ees
´
>
;
?
,
soit
l’op
er
´
ateur
unair
e
D
ef
´
.
II.8
(F
orme
conjoncti
v
e,
disjoncti
v
e)
Une
forme
conjonctive
est
une
conjonction
de
clauses.
:
(n
egation),
´
soient
les
op
er
´
ateur
s
binair
es
_
(disjonction),
^
(conjonction),
)
(implication);
l’en-
Une
forme
disjonctive
est
une
disjonction
de
clauses
duales.
semble
P
(
F
)
des
pr
opositions
est
le
plus
petit
ensemble
tel
que
:
Exemple
II.2
(
a
_
:
c
)
^
:
b
est
une
forme
conjonctive
.
c
_
(
:
a
^
b
)
est
une
forme
disjonctive
.

F
P
(
F
)
;

f>
;
?g
P
(
F
)
;
Question
II.2
Soit
la
pr
oposition
P
=
(
a
^
c
)
?
)
^
(
a
)
b
)
^
(
>
)
b
_
d
)
,
tr
ansformer
P
en
une

si
P
2
P
(
F
)
alor
s
:
P
2
P
(
F
)
;
forme
conjonctive
C
,
puis
en
une
forme
disjonctive
D
telles
que
P
C
D
.
V
ous
utiliser
ez
pour
2

si
P
;P
2
P
(
F
)
et
op
2
f_
;
^
;
)g
alor
s
P
op
P
2
P
(
F
)
;
1
2
1
2
cela
les
formules
de
De
Mor
gan.

les
pr
opositions
de
P
(
F
)
sont
finies,
c’est-
a-dir
`
e
obtenues
par
application
d’un
nombr
e
fini
de
fois
des
r
egles
`
pr
ec
´
edentes.
´
2
Repr
esentation
´
et
codage
d’un
ensemble
de
faits
Nous
noterons
les
f
aits
en
utilisant
les
minuscules
de
l’alphabet
romain.
Nous
noterons
les
proposi-
La
repr
´
et
les
op
erations
´
de
manipulation
des
bases
de
connaissances
reposent
sur
la
tions
et
les
ensembles
de
f
aits
en
utilisant
les
majuscules
de
l’alphabet
romain.
structure
d’ensemble.
Nous
allons
dans
une
premi
ere
`
etape
´
etudier
´
un
codage
de
cette
structure
qui
contiendra
des
f
aits.
Cette
structure
sera
ensuite
adapt
ee
´
aux
connaissances.17
18
2.1
Codage
d’un
fait
Question
II.4
Donner
un
e
xemple
de
valeur
s
des
par
am
etr
`
es
f
et
E
de
la
fonction
appartenance
qui
corr
espond
au
pir
e
cas
en
nombr
e
d’appels
r
ecur
sifs
ef
fectu
es.
´
´
Un
f
ait
est
repr
esent
´
e
´
par
le
type
de
base
STRING
.
Calculer
une
estimation
de
la
comple
xit
e
´
dans
le
pir
e
cas
de
la
fonction
en
fonction
de
la
taille
de
l’ensemble
E
.
Cette
estimation
ne
pr
endr
a
en
compte
que
le
nombr
e
d’appels
r
ecur
´
sifs
ef
fectu
es.
´
2.2
Codage
d’un
ensemble
de
faits
Nous
allons
utiliser
un
codage
e
xtr
emement
ˆ
simple
:
un
ensemble
est
une
liste
contenant
e
xac-
2.3.2
Ajout
dans
un
ensemble
tement
un
e
x
emplaire
de
chaque
el
´
ement
´
contenu
dans
l’ensemble.
Les
op
erations
´
de
manipulation
La
deuxi
eme
`
op
eration
´
est
l’ajout
d’un
f
ait
a
`
un
ensemble.
d’un
ensemble
de
vront
pr
eserv
´
er
cette
propri
et
´
e.
´
Un
ensemble
de
f
aits
est
repr
esent
´
e
´
par
le
type
de
base
FAITS
correspondant
a
`
une
liste
de
f
aits.
´
Question
II.5
Ecrir
e
en
P
ASCAL
une
fonction
ajout(f:FAIT;E:FAITS):FAITS;
telle
que
Le
parcours
d’un
ensemble
sera
donc
ef
fectu
e
´
de
la
m
eme
ˆ
mani
ere
`
que
celui
d’une
liste.
l’appel
ajout(f,E)
r
en
voie
un
ensemble
contenant
les
m
emes
ˆ
faits
que
l’ensemble
f
ainsi
que
le
Nous
supposons
pr
ed
´
efinies
´
les
constantes
et
les
fonctions
sui
v
antes
dont
le
calcul
se
termine
fait
E
s’il
ne
figur
ait
pas
d
ej
´
a
`
dans
E
.
L
’ensemble
r
en
voy
e
´
contiendr
a
e
xactement
une
fois
le
fait
f
.
quelles
que
soient
les
v
aleurs
de
leurs
param
etres.
`
Elles
pourront
ev
´
entuellement
etre
ˆ
utilis
ees
´
dans
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
les
r
eponses
´
aux
questions
:
2.3.3
Inclusion
entr
e
deux
ensembles

NIL
repr
esente
´
la
liste
vide
de
f
aits
;

FUNCTION
LF
Ajout(f:FAIT;E:FAITS):FAITS;
ren
v
oie
une
liste
de
f
aits
compos
ee
´
La
troisi
eme
`
op
eration
´
est
le
test
d’inclusion
du
contenu
de
deux
ensembles.
d’un
premier
f
ait
f
et
du
reste
de
la
liste
contenu
dans
E
;
´
Question
II.6
Ecrir
e
en
P
ASCAL
une
fonction

FUNCTION
LF
Premier(E:FAITS):FAIT;
ren
v
oie
le
premier
f
ait
de
la
liste
E
.
Cette
inclusion(E1:FAITS;E2:FAITS):BO
OLEAN
;
telle
que
l’appel
liste
ne
doit
pas
etre
ˆ
vide
;
inclusion(E1,E2)
r
en
voie
la
valeur
TRUE
si
l’ensemble
E2
contient
au
moins
les
m
emes
ˆ
faits

FUNCTION
LF
Reste(E:FAITS):FAITS;
ren
v
oie
le
reste
de
la
liste
E
pri
v
ee
´
de
son
pre-
que
l’ensemble
E1
et
la
valeur
FALSE
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
mier
f
ait.
Cette
liste
ne
doit
pas
etre
ˆ
vide
;
fonctions
auxiliair
es
r
ecur
´
sives.

FUNCTION
LF
Juxtaposition(E1:FAITS;E2:FA
ITS):
FAIT
S;
ren
v
oie
la
liste
com-
pos
ee
´
de
la
liste
E1
sui
vie
de
la
liste
E2
.
Question
II.7
Donner
un
e
xemple
de
valeur
s
des
par
am
etr
`
es
E1
et
E2
de
la
fonction
inclusion
qui
corr
espond
au
pir
e
cas
en
nombr
e
d’appels
r
ecur
´
sifs
ef
fectu
es.
´
Nous
allons
maintenant
d
efinir
´
plusieurs
op
erations
´
sur
les
ensembles
de
f
aits
qui
pourront
etre
ˆ
Calculer
une
estimation
de
la
comple
xit
e
´
dans
le
pir
e
cas
de
la
fonction
inclusion
en
fonction
utilis
ees
´
dans
la
suite
du
sujet.
Ces
op
erations
´
seront
ensuite
etendues
´
aux
ensembles
de
connais-
des
tailles
des
ensembles
E1
et
E2
.
Cette
estimation
ne
pr
endr
a
en
compte
que
le
nombr
e
d’appels
sances.
r
ecur
sifs
ef
fectu
es.
´
´
Nous
supposons
que
toutes
les
listes
repr
esentant
´
des
ensembles,
qui
sont
pass
ees
´
comme
param
etres
`
´
des
fonctions,
ne
contiennent
au
plus
qu’une
fois
chaque
el
´
ement.
´
2.3.4
Egalit
e
´
entr
e
deux
ensembles
La
quatri
eme
`
op
eration
´
est
le
test
d’
egalit
´
e
´
du
contenu
de
deux
ensembles.
2.3
Op
eration
´
sur
la
structur
e
d’ensemble
´
Question
II.8
Ecrir
e
en
P
ASCAL
une
fonction
egalite(E1:FAITS;E2:FAITS):BOOL
EAN;
telle
que
l’appel
egalite(E1,E2)
r
en
voie
la
Pour
les
calculs
de
comple
xit
e,
´
nous
noterons
j
E
j
la
taille
de
l’ensemble
E
,
c’est-
a-dire
`
le
valeur
TRUE
si
les
deux
ensembles
E1
et
E2
contiennent
e
xactement
les
m
emes
ˆ
faits
et
la
valeur
nombre
de
f
aits
qu’il
contient.
FALSE
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
2.3.1
A
ppartenance
a
`
un
ensemble
2.3.5
Soustraction
de
deux
ensembles
Une
premi
ere
`
op
eration
´
consiste
a
`
tester
l’appartenance
d’un
f
ait
a
`
un
ensemble.
La
derni
ere
`
op
eration
´
etudi
´
ee
´
est
la
construction
d’un
ensemble
r
esultant
´
de
la
soustraction
d’un
ensemble
depuis
un
autre
ensemble.
´
Question
II.3
Ecrir
e
en
P
ASCAL
une
fonction
´
appartenance(f:FAIT;E:FAITS):BO
OLEAN
;
telle
que
l’appel
appartenance(f,E)
r
en-
Question
II.9
Ecrir
e
en
P
ASCAL
une
fonction
voie
la
valeur
TRUE
si
l’ensemble
E
contient
le
fait
f
et
la
valeur
FALSE
sinon.
Cette
fonction
de
vr
a
soustraction(E1:FAITS;E2:FAITS)
:FAIT
S;
telle
que
l’appel
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
soustraction(E1,E2)
r
en
voie
un
ensemble
contenant
les
faits
qui
sont
contenus
dans
E1
et19
20
ne
sont
pas
contenus
dans
E2
.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
D
ef
´
.
II.11
(Connaissance
absurde)
Une
connaissance
est
absur
de
si
et
seulement
si
son
interpr
etation
´
auxiliair
es
r
ecur
sives.
I
(
)
est
absur
de
.
´
Question
II.11
Montr
er
que
la
seule
connaissance
absur
de
est
;

;
.
2.3.6
A
utr
es
op
erations
´
pr
ed
´
efinies
´
Nous
supposons
pr
ed
´
efinies
´
les
fonctions
sui
v
antes
pour
les
ensembles,
dont
le
calcul
se
termine
3.2
Codage
d’une
connaissance
quelles
que
soient
les
v
aleurs
de
leurs
param
etres.
`
Elles
pourront
ev
´
entuellement
etre
ˆ
utilis
ees
´
dans
les
r
eponses
´
aux
questions
:
Pour
les
v
ariables
ou
les
constantes
dont
le
nom
est
pris
dans
l’alphabet
grec
(
,
.
.
.
),
l’identifiant
en
P
ASCAL
sera
leur
nom
en
toute
lettre
(
gamma
,
.
.
.
).

union(E1:FAITS;E2:FAITS):FAITS;
ren
v
oie
un
ensemble
contenant
les
f
aits
contenus
dans
E1
ainsi
que
les
f
aits
contenus
dans
E2
;
Une
connaissance
est
repr
esent
´
ee
´
par
le
type
de
base
CONNAISSANCE
correspondant
a
`
un
couple
compos
e
´
de
deux
ensembles
de
f
aits.

intersection(E1:FAITS;E2:FAITS)
:FAI
TS;
ren
v
oie
un
ensemble
contenant
les
f
aits
Nous
supposons
pr
ed
´
efinies
´
les
constantes
et
les
fonctions
sui
v
antes
dont
le
calcul
se
termine
contenus
a
`
la
fois
dans
E1
et
dans
E2
.
quelles
que
soient
les
v
aleurs
de
leurs
param
etres.
`
Elles
pourront
ev
´
entuellement
etre
ˆ
utilis
ees
´
dans
les
r
eponses
´
aux
questions
:
3
Repr
esentation
´
et
codage
d’une
connaissance

FUNCTION
C
Creer(H:FAITS;C:FAITS):CONNAI
SSANC
E;
ren
v
oie
une
connaissance
dont
les
hypoth
eses
`
sont
les
f
aits
de
l’ensemble
H
et
les
conclusions
sont
les
f
aits
de
l’ensemble
3.1
Repr
´
d’une
connaissance
C
;
D
ef
´
.
II.9
(Connaissance)
Une
connaissance
not
ee
´
=
H

C
est
compos
ee
´
de
deux
ensembles

FUNCTION
C
Hypotheses(gamma:CONNAISSANCE
):FAI
TS;
ren
v
oie
les
hypoth
eses
`
finis
de
faits
(ou
variables
pr
opositionnelles)
:
les
hypoth
eses
`
H
=
f
h
g
et
les
conclusions
C
=
i
i
2
I
de
la
connaissance
gamma
,
f
c
g
.
j
j
2
J

FUNCTION
C
Conclusions(gamma:CONNAISSANC
E):FA
ITS;
ren
v
oie
les
conclusions
de
la
connaissance
gamma
.
Nous
noterons
les
connaissances
en
utilisant
les
minuscules
de
l’alphabet
grec.
´
Question
II.12
Ecrir
e
en
P
ASCAL
une
fonction
comparaison(gamma1:CONNAISSANCE
;gamm
a2:C
ONNAI
SSAN
CE):B
OOLE
AN;
telle
que
D
ef
´
.
II.10
(Inter
pr
etation
´
logique)
L
’interpr
etation
´
lo
gique
,
not
ee
´
I
(
)
,
d’une
connaissance
l’appel
comparaison(gamma1,gamma2)
r
en
voie
la
valeur
TRUE
si
les
deux
connaissances
=
f
h
g

f
c
g
est
:
i
i
2
I
j
j
2
J
gamma1
et
gamma2
contiennent
e
xactement
les
m
emes
ˆ
hypoth
eses
`
et
conclusions
et
la
valeur
FALSE
^
_
sinon.
Cette
fonction
de
vr
a
etr
ˆ
e
r
ecur
´
sive
ou
fair
e
appel
a
`
des
fonctions
auxiliair
es
r
ecur
´
sives.
I
(
)
=
(
>
^
h
)
)
(
?
_
c
)
i
j
i
2
I
j
2
J
´
Intuitivement,
elle
signifie
que
sous
les
hypoth
eses
`
de
f
h
g
,
nous
pouvons
d
eduir
´
e
une
des
4
Repr
esentation
et
codage
d’une
base
de
connaissances
i
i
2
I
conclusions
de
f
c
g
.
>
permet
de
tr
aiter
le
cas
I
=
;
.
?
permet
de
tr
aiter
le
cas
J
=
;
.
Notons
j
j
2
J
que
:
4.1
Repr
´
d’une
base
de
connaissances
W
D
ef
´
.
II.12
(Base
de
connaissances)
Une
base
de
est
un
ensemble
fini
de
connais-

I
(
;

f
c
g
)
=
>
)
(
?
_
c
)
;
j
j
2
J
j
j
2
J
V
sances
=
f
g
.
k
k
2
K

I
(
f
h
g

;
)
=
(
>
^
h
)
)
?
;
i
i
2
I
i
i
2
I

I
(
;

;
)
=
>
)
?
.
Nous
noterons
les
bases
de
connaissances
en
utilisant
les
majuscules
de
l’alphabet
grec.
Exemple
II.3
Les
formules
lo
giques
suivantes
sont
des
connaissances
:
D
ef
´
.
II.13
(Inter
pr
etation
´
logique)
L
’interpr
etation
´
lo
gique
,
not
ee
´
I
( )
,
d’une
base
=
f
g
k
k
2
K

f
a
g

f
b
g
;
est
d
efinie
´
par
:

f
a,
c
g

;
;
^
I
( )
=
>
^
I
(
)
k

;

f
b,
d
g
.
k
2
K
Question
II.10
Soit
=
f
h
g

f
c
g
une
connaissance
quelconque
,
donner
une
clause
P
telle
Elle
corr
espond
a
`
la
conjonction
des
interpr
etations
´
lo
giques
de
c
haque
connaissance
.
i
i
2
I
j
j
2
J
que
I
(
)
P
.
Notons
que
:
I
(
;
)
=
>
.