\documentclass[10pt]{article}
 
\usepackage{french}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{pifont}
\usepackage[dvips]{graphics}
\usepackage[dvips]{graphicx}
\usepackage{prefmr}

\topmargin -2.5cm
\oddsidemargin -0.5cm
\evensidemargin -0.5cm
\textheight 27cm
\textwidth 16.0cm
\title{\bf Examen Prolog  --- ESSI2  }
\author{Michel Rueher}
\date{12 Janvier 1996}

\begin{document}
\maketitle
\begin{center}
\thispagestyle{empty}
{\large Documents autoris\'es: {\it supports (et notes) de cours ou TD}}
\end{center}

\section{Transformation d'une forme clausale en Prolog ---  5 points }

Soit les \'enonc\'es :
\begin{itemize}	
\item	Pour tout crime, il y a quelqu'un qui l'a commis;
\item	Seuls les gens malhonn\^etes commettent des crimes; 
\item	Ne sont arr\^et\'es que les gens malhonn\^etes;
\item	Les gens  malhonn\^etes arr\^et\'es ne commettent pas de crimes;
\item	Il y a des crimes.
\end{itemize}
	
On cherche \`a \'etabir la proposition ``{\it Il y a des gens malhonn\^etes non
arr\^et\'es}''.\\
 
\begin{enumerate}	
\item	Mettre les \'enonc\'es et la proposition ci-dessus sous forme de
clauses. On utilisera pour cela les pr\'edicats suivants:
	\begin{itemize}
	\item	{\tt ar(y)} : $y$ est arr\^et\'e;
	\item	{\tt ma(y)} : $y$ est malhonn\^ete;
	\item	{\tt co(y,x)} : $y$ commet $x$;
	\item	{\tt cr(x)} : $x$ est un crime.
	\end{itemize}		
\item	Peut on prouver ou refuter la proposition \`a l'aide d'un interpr\`ete
	Prolog en: 
	\begin{enumerate}
	\item	Transformant automatiquement les clauses obtenues en un
		programme Prolog;
	\item	Utilisant la clause correspondant \`a la proposition \`a \'etablir
		comme r\'esolvante.
	\end{enumerate}	
\end{enumerate}	
		
\section{Strat\'egie de recherche de Prolog ---  5 points }
\begin{enumerate}	
\item	Est ce que la strat\'egie de recherche standard de Prolog garantit la
	correction et la compl\'etude des r\'esultats ?\\
	Pourquoi ?
\item	Quelles autres strat\'egies de recherche pourraient \^etre utilis\'ees par un
	interpr\`ete Prolog ?\\
	Expliquer quels sont leurs avantages et leurs inconv\'enients.
\end{enumerate}	



\section{Programmez .... ---  5 points }

	Ecrire un pr\'edicat Prolog {\tt liaisons(A,B,C,T)} qui recherche
l'ensemble des liaisons a\'eriennes entre les villes $A$ et $B$ avec un co\^ut
inf\'erieur \`a $T$. Le chemin utilis\'e est donn\'e par $C$. L'existence d'un vol
entre les villes $A$ et $B$ avec un co\^ut de $C$ est exprim\'e par un pr\'edicat
{\tt vol(A,B,C)}; le co\^ut associ\'e \`a une escale de 1.\\

{\bf Exemple}\\
{\small 
\begin{verbatim}	
vol(a,b,5).       vol(b,c,3).       vol(a,c,6)..       
vol(c,a,9).       vol(b,a,1).       vol(c,d,5).
| ?- liaisons(a,d,C,19).            | ?- liaisons(a,d,C,15)..            | ?- liaisons(a,d,C,12).
 
C = [a,b,c,d] ? ;                   C = [a,c,d] ? ;                      no
 
C = [a,c,d] ? ;
 
no                                  no

\end{verbatim}	}

\pagebreak
\vspace*{2cm}

\section{Expliquez le programme {\tt mybagof/3 } ---  5 points }
\begin{enumerate}
\item   Expliquer le r\^ole  du {\tt fail} dans la premi\`ere  clause du
	pr\'edicat {\tt add\_mylist/1 } dans le  programme {\tt bagof};

\item	Expliquer le fonctionnement de la deuxi\`eme  clause du
	pr\'edicat {\tt add\_mylist/1 } dans le  programme {\tt bagof}.

\end{enumerate}	

{\bf Rappel du programme  {\tt bagof/3 }}
     { \small
     \begin{verbatim}
       
mybagof(O,P,L):-
       P,
       add_mylist(O),
       fail.

mybagof(_,_,L) :- !,
       retract(mylist(L-[])).

add_mylist(O) :-
       \+(clause(mylist(_),_)), ! ,
       L = [O|S],
       assert(mylist(L-S)).
add_mylist(O) :- 
       retract(mylist(L-S)),
       S=[O|S1], 
       assert(mylist(L-S1)).
       

mysetof(O,P,L) :-
       mybagof(O,P,L1),
       sort(L1,L).
\end{verbatim}       }
    

\end{document}	


