Informatique 2004 Concours Instituts Nat. Polytechniques (INP - ENSI)
13 pages
Français

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

Cet ouvrage peut être téléchargé gratuitement
13 pages
Français
Cet ouvrage peut être téléchargé gratuitement

Description

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

Sujets

Informations

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

Exrait

corrigé Informatique 2004 sur Bankexam.fr." />

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
(
;
)
=
>
.

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents