\documentclass[11pt]{article}
\usepackage{alltt}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{pifont}
\usepackage[dvips]{graphics}
\usepackage[dvips]{graphicx}

\parindent=0cm
\oddsidemargin 0.2cm
\evensidemargin 0.2 cm


\textheight 22cm
\textwidth 16.0cm
\title{\bf Examen Prolog  --- ESSI2  \\
{\large( Documents autoris\'es: {\it tous})}}
\author{Michel Rueher}
\date{Mai 1998}

\begin{document}
\maketitle

\begin{enumerate}
\item[1. (3 points)]	
	Ecrire en {\tt prolog} le pr\'edicat d\'efini par la clause:\\

	\((gp(X,Z) \vee \neg p(Y,Z) \vee \neg p(X,Y)) \wedge (gp(X,Z) 
	\vee \neg p(Y,Z) \vee \neg m(X,Y)) \)


\item[2. (3 points)] 
	Expliquer pourquoi la coupure ci-dessous ---appel\'ee {\it red cut}---
	est dangereuse.
\begin	{alltt}
min(X,Y,X) :-  Y \( \ge\) X, !.
min(X,Y,Y).
\end	{alltt}	
\item[3. (3 points)] 
	Expliquer quel est l'avantage du pr\'edicat {\tt len1/2} par rapport
 au pr\'edicat {\tt len2/2} ci-dessous.
\begin	{alltt}
len1(L,N) :- len1(L,0,N).                 len2([],0).
len1([],N,N).                             len2([X|L],N) :- len2(L,N0),
len1([H|T],N0,N) :- N1 is N0 +1,                           N is N0 + 1.
                    len1(T,N1,N).
\end	{alltt}	
\item[4. (3 points)] 
	Expliquer pourquoi le pr\'edicat {\tt tri/2} ci-dessous ne r\'ealise pas un tri sur place.
\begin	{alltt}
tri([],[]).                               p([],_,[],[]).
tri([H|L],T):-                            p([E1|L],H,[E1|P1],P2):- E1 @=< H,
        p(L,H,P1,P2),                                              p(L,H,P1,P2).
        tri(P1,T1),                       p([E1|L],H,P1,[E1|P2]):- E1 @> H,
        tri(P2,T2),                                                p(L,H,P1,P2).
        append(T1,[H|T2],T). 
\% append/3: pr\'edicat de concat\'enation de la biblioth\`eque Sicstus
            (fonctionne comme{\tt  conc/3})
\end	{alltt}	

\item[5. (3 points)] Probl\`eme du z\`ebre. Indiquer comment il faut compl\'eter 
le pr\'edicat {\tt relation/5} ci-dessous si on remplace  {\tt C=[\_,bleu,\_,\_,\_]} 
par {\tt C=[\_,\_,\_,\_,\_] }.
\begin	{alltt}
relation(C,N,F,B,A):-
           C=[_,bleu,_,_,_], N =[norvegien,_,_,_,_],
           B= [_,_,lait,_,_], A= [_,_,_,_,_],
           meme_position(rouge,anglais,C,N),
           meme_position(vert,cafe,C,B),
           meme_position(jaune,kool,C,F),
           voisin_droit(vert,blanc,C),
           meme_position(espagnol,chien,N,A),
           meme_position(ukrainien,the,N,B),
           meme_position(japonais,craven,N,F),
           meme_position(old_gold,escargot,F,A),
           meme_position(gitane,vin,F,B),
           voisin(chesterfield,renard,F,A),
           voisin(kool,cheval,F,A).
\end	{alltt}	

\item[5. (5 points)] Soit une expression bool\'eenne construite \`a l'aide:
\begin{itemize}	
\item	de variables bool\'eennes instanci\'ees \`a {\tt true} ou {\tt false} 
(repr\'esent\'ees par les constantes 1 et 0);
\item 	des op\'erateurs binaires {\tt  et} et {\tt ou} (repr\'esent\'es par les caract\`eres * et +);
\item	de l'op\'erateur unaire de n\'egation (repr\'esent\'e par le caract\`ere -).
\end{itemize}	

\begin{enumerate}	
\item	 Donner la {\tt DCG} qui permet d'analyser ce type d'expression bool\'eenne;
\item	 Donner le programme {\tt prolog} g\'en\'er\'e \`a partir de la {\tt DCG} par 
l'interpr\`ete {\tt Sicstus};
\item	 Donner la {\tt DCG} qui permet d'analyser et d'\'evaluer 
simultan\'ement ce type d'expression bool\'eenne;
\end{enumerate}	
Exemple:
\begin	{alltt}
> eval\_bool(Z,''0*1+-0'',[]).
> Z=0
> eval\_bool(Z,''1+-1'',[])
> Z=1
\end	{alltt}	
\end{enumerate}	

\end{document}	


