Examen de Logique et de Prolog — ESSI2

(Documents autorisés: tous)

Hélène Collavizza et Michel Rueher

Mai 2000

1 Logique

1. Dans la théorie τ des listes avec les constructeurs suivants (les c_{i} représentent des atomes,

nil et l correspondent à des listes): • nil

• c.nil

• c_{1}.c_{2}.l

(a) (3 points) Donner les axiomes définissant :

• pair(l) : les éléments de rang pair de l

• impair(l) : les éléments de rang impair de l

• alterne(l_{1}, l_{2}) : la liste contenant les éléments pris alternativement dans l_{1} et l_{2}. (remarque : si les listes l_{1} et l_{2} sont de longueurs différentes on ajoute à la fin les éléments de la plus longue des listes).

Exemple:

• pair(a.b.c.d.nil) = b.d.nil

• impair(a.b.c.d.e.nil) = a.c.e.nil

• alternee(a.b.c.d.nil, 1.2.3.4.5.nil) = a.1.b.2.c.3.d.4.5.nil

(b) (3 points) Montrer que alternee(impair(l), pair(l)) = l est vrai dans les modèles initiaux de τ.

2. On considère les prédicats:

• milieu(p_{1}, p_{2}, m): m est le milieu du segment [p_{1}, p_{2}]

• perpendiculaire(p_{1}, p_{2}, p_{3}, p_{4}) : le segment [p_{1}, p_{2}] est perpendiculaire au segment [p_{3}, p_{4}]

• isocelle(p_{1}, p_{2}, p_{3}) : le triangle défini par les points (p_{1}, p_{2}, p_{3}) est isocelle

(a) (3 points) Ecrire à l’aide de ces seuls prédicats les énoncés suivants sous forme de formules en logique du premier ordre : i. Si la hauteur en B du triangle ABC passe par le milieu du segment[A, C] alors

ABC est isocelle. ii. Pour tout couple de points (AB), il existe un point C tel que AB soit perpen-

diculaire au segment déterminé par C et le milieu du segment[A, B] iii. Pour tout couple de points (AB), il existe un point C qui est le milieu du

segment[A, B]

(b) (3 points) Utiliser les énoncés précédents pour montrer que pour tout couple de points (AB) il existe un point C tel que le triangle ABC soit isocelle. Détailler les différentes étapes de la preuve par résolution (distinguer clairement les variables des constantes).

2 Prolog

1. (2 points) Expliquer pourquoi le prédicat renverser 1 est moins efficace que le prédicat

renverser 2.
renverser_1([],[]).                      renverser_2(L1,L2):- renverser(L1,[],L2)
renverser_1([A|L],Z):-                   renverser([],L,L).
renverser_1(L,L1),               renverser([T|Q],L_aux,L):-
append(L1,[A],Z).                    renverser(Q,[T|L_aux],L

2. Soit le programme Prolog qui résoud “l’équation” SEND + MORE = MONEY :

:- use_module(library(lists)).
mm1([S,E,N,D,M,O,R,Y]) :-                 mm2([S,E,N,D,M,O,R,Y]) :-
generate1([S,E,N,D,M,O,R,Y]),              generate2([S,E,N,D,M,O,R,Y]),
S>0, M >0,                                 S>0, M >0,
alldiff([S,E,N,D,M,O,R,Y]),                alldiff([S,E,N,D,M,O,R,Y]),
test_sum(S,E,N,D,M,O,R,Y).                 test_sum(S,E,N,D,M,O,R,Y)
test_sum(S, E, N, D, M, O, R, Y) :-
V  is             1000*S + 100*E + 10*N + D
 +            1000*M + 100*O + 10*R + E,
V is 10000*M + 1000*O + 100*N + 10*E + Y,
generate1([]).                            generate2([]).
generate1([X|Xs]):-                       generate2([X|Xs]):-
member(X,[0,1,2,3,4,5,6,7,8,9]),            digit(X),
generate1(Xs).                              generate2(Xs).
alldiff([]).                              digit(0).
                                 digit(1).
alldiff([X|L]):-                          digit(2).
diff(X,L),                            ...
alldiff(L).                           digit(9).
diff(X,[]).
diff(X,[V|L]):-
X ¯ V,
diff(X,L).

(a) (2 points) Comparer et expliquer les différences de performance des appels

mm1([S,E,N,D,M,O,R,Y]) et mm2([S,E,N,D,M,O,R,Y]) (syntaxiquement ces prédicats
ne diffèrent que par generate1/1 et generate2/1).

(b) (2 points) Donner 2 ordonnancements de la liste [S,E,N,D,M,O,R,Y] pour le prédicat

generate1/1 qui accélèrent considérablement les performances de mm1/. Expliquer.

3. Machine de Türing déterministe

(a) (3 points) Ecrire un interprète t machine/2 pour une machine de Türing déterministe. Cet interprète fera appel à un prédicat transition/5 qui sera défini pour chaque langage.

• t machine(T ape, Answer) :

– T ape: liste binaire qui contient le mot à lire sur le ruban,

– Answer: liste binaire qui contient le résultat de l’interprétation (ok ou ko),

l’état de la machine et l’état du ruban.

• transition(Q_{0}, W_{0}, Q_{1}, W_{1}, D) :

– Q_{0}: l’état de la machine avant la transition,

– W_{0}: le caractère se trouvant sous la tête de lecture,

– Q_{1}: l’état de la machine après la transition,

– W_{1}: le caractère qui sera écrit sur le ruban à la place du caractère se trouvant sous la tête de lecture,

– D: le sens de déplacement de la tête de lecture.

(b) (3 points) Ecrire les règles de transition pour les langages suivants:

• a^{n}b^{n}

• mots sur l’alphabet {a,b} dont la longueur est une puissance de 2. Annexe

Définition d’une machine de Türing déterministe(rappel)

Une machine de türing déterministe est un automate défini par M = (Q, Γ, Σ, δ, s, B, F) où: • Q est un ensemble fini d’états,

• Γ est l’alphabet utilisé sur le ruban,

• Σ ⊆ Γ est l’alphabet utilisé pour le mot d’entrée,

• δ : Q × Γ → Q × Γ × {L, R} est la fonction de transition,

• s ∈ Q est l’état initial,

• B ∈ Γ − Σ est le symbole blanc (noté #),

• F ⊆ Q est l’ensemble des états accepteurs.

Une configuration contient toute l’information nécessaire pour poursuivre l’exécution (i.e., l’état, le mot écrit sur le ruban avant la tête de lecture, le mot se trouvant entre la position de la tête de lecture et le dernier caractère non blanc). Les configurations dérivable à partir de (q, α_{1}, bα_{2}) sont :

• (q′, α_{1}b′, α_{2}) si δ(q, b) = (q′, b′, R)

• (q, α′_{1}, ab′α_{2}) si δ(q, b) = (q′, b′, L) et α_{1} = α′_{1}a