\documentclass[10pt]{article}
 
\usepackage{french}
\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  }
\author{Michel Rueher}
\date{4 F\'evrier 1997}

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


\section{G\'en\'erateur de plans pour robots }

On voudrait d\'eplacer trois cubes A, B et C dispos\'es sur les emplacements 1, 2
et 3 (situation {\bf Init}) pour obtenir  
la configuration finale suivante (situation {\bf Final}).
On dispose pour cela d'un petit robot qui sait d\'eplacer les cubes:
quand il re\c coit la commande {\tt transfert(X,I,J)}, le robot
enl\`eve le cube {\tt X}  \`a la position {\tt I}
et le pose  \`a la position {\tt J}. 
Le robot peut uniquement d\'eplacer les cubes au sommet d'une pile.\\

\noindent Ecrivez le pr\'edicat {\tt plan\_robot(P,N)} o\`u {\tt P} est une
suite de commandes pour d\'eplacer les cubes de la
configuration initiale \`a la configuration finale et {\tt N} le nombre
maximal d'op\'erations. \\ 
       

\begin{verbatim} 
                                                              --- 
                                                             | A |       
        ___                                                   ---       
       | A |                                                 | B |  
        ---       ---                                         ---
       | C |     | B |                                       | C |   
        ---       ---                                         ---   
       ---------------------------       -------------------------               
         1         2         3             1         2         3   

                 (Init)                             (Final)
\end{verbatim} 

\noindent Exemple:
{ \small 
\begin{verbatim} 
| ?- robot(A,5).
 
A = [t(a,c,b),t(c,1,3),t(a,b,1),t(b,2,c),t(a,1,b)]
\end{verbatim}
}	

\section{Expliquez ... } 

Expliquer le fonctionnement du pr\'edicat {\tt prouve/2} ci-dessous. Vous pouvez
utiliser un exemple. 


{ \small
     \begin{verbatim}
prouve(Nil) :-
       Nil = vide ; Nil = [].
prouve([Goal|OtherGoal]) :-
       list_of_clauses(L),
       member([Goal,Tail],L),
       prouve(Tail), 
       prouve(OtherGoal).
\end{verbatim}      
}
\pagebreak
\section{Un pr\'edicat {\tt power\_set/2}... }

Le pr\'edicat {\tt power\_set(Set, Power\_Of\_Set)} doit calculer:
\begin{itemize}	
\item[$\circ$] l'ensemble des parties {\tt Power\_Of\_Set} \`a partir de
l'ensemble {\tt Set};
\item[$\circ$] l'ensemble {\tt Set}  \`a partir de 	 l'ensemble de ses parties
{\tt Power\_Of\_Set}.\\
\end{itemize}

Algorithme G\'en\'eral:

{\small 
\begin{verbatim}	
 1.	If Set = {}, Power_Of_Set = {{}}
 2.	If Set = {Elt} U Rest, then
 2.1.      Let Power_Of_Rest = power_set(Rest)
 2.2.	   Power_Of_Set = {{Elt} U X | X in Power_Of_Rest} U Power_Of_Rest
\end{verbatim}	
}		
Exemples:

{\small 
\begin{verbatim}	
?- power_set(X, [[1,2],[1],[2],[]]).
X = [1, 2]

?- power_set(X, [[1,2],[2],[1],[]]).
fail.

?- power_set([1,2,3], X).
X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

\end{verbatim}	
}
\begin{enumerate}	
\item	L'algorithme ci-dessus effectue un certain nombre de choix qui
autorisent une efficacit\'e raisonnable. Lesquels ?
\item	Ecrire {\tt power\_set/2} en Prolog.    
\end{enumerate}	
\end{document}	


