\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 de Logique et de  Prolog  --- ESSI2  \\
{\large(Documents autoris\'es: {\it tous})}}
\author{H\'el\`ene Collavizza et Michel Rueher}
\date{Mai 2000}

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Logique}

\begin{enumerate}
\item 	Dans la th\'eorie $\tau$ des listes avec les constructeurs suivants (les  $c_i$ 
	repr\'esentent des atomes, $nil$ et $l$ correspondent \`a des listes):
	\begin{itemize}	
	\item	$nil$
	\item	$c.nil$
	\item	$c_1.c_2.l$
	\end{itemize}	
	\begin{enumerate}	
	\item (3 points)	Donner les axiomes d\'efinissant :
	\begin{itemize}	
	\item	 $pair(l)$ : les \'el\'ements de rang pair de $l$
	\item	 $impair(l)$ : les \'el\'ements de rang impair de $l$	
	\item	 $alterne(l_1,l_2)$ : la liste contenant les \'el\'ements pris alternativement 
		dans $l_1$ et $l_2$. \\
		(remarque : si les listes  $l_1$ et $l_2$ sont de longueurs diff\'erentes on 
		ajoute \`a la fin les \'el\'ements de la plus longue des listes).
	\end{itemize}	
	Exemple:
	\begin{itemize}	
	\item	 $pair(a.b.c.d.nil)=b.d.nil$
	\item	 $impair(a.b.c.d.e.nil)=a.c.e.nil$	
	\item	 $alternee(a.b.c.d.nil,1.2.3.4.5.nil)=a.1.b.2.c.3.d.4.5.nil$
	\end{itemize}		
	\item	(3 points) Montrer que $alternee(impair(l),pair(l))=l$ est vrai dans
		les  mod\`eles initiaux de  $\tau$.
	\end{enumerate}	
\item  On consid\`ere les pr\'edicats:
	\begin{itemize}	
	\item	$milieu(p_1,p_2,m)$: $m$ est le milieu du segment [$p_1,p_2$]
	\item	$perpendiculaire(p_1,p_2,p_3,p_4)$ : le segment [$p_1,p_2$] est perpendiculaire
		au segment [$p_3,p_4$]
	\item	$isocelle(p_1,p_2,p_3)$ : le triangle d\'efini par les points $(p_1,p_2,p_3)$ 
		est isocelle
	\end{itemize}
	\begin{enumerate}	
	\item (3 points) Ecrire \`a l'aide de ces seuls pr\'edicats les 
		\'enonc\'es suivants sous forme de formules en logique du premier ordre :
	\begin{enumerate}		
	\item	Si la hauteur en $B$ du triangle $ABC$ passe par le milieu du segment[$A,C$]
	alors $ABC$ est isocelle. 
	\item 	Pour tout couple de points ($AB$), il existe un point $C$
		 tel que $AB$ soit perpendiculaire au segment d\'etermin\'e par $C$
		 et le milieu du segment[$A,B$]
	\item	Pour tout couple de points ($AB$), il existe un point $C$ qui est le milieu
		du segment[$A,B$]
	\end{enumerate}	
	\item (3 points) Utiliser les \'enonc\'es pr\'ec\'edents pour montrer que pour tout couple de 
	points ($AB$) il existe un point $C$ tel que le triangle $ABC$ soit isocelle. D\'etailler 
	les diff\'erentes \'etapes de la preuve par r\'esolution (distinguer clairement les variables 
	des constantes).
	\end{enumerate}	

\end{enumerate}	



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Prolog}
\begin{enumerate}
\item (2 points)
	Expliquer pourquoi le pr\'edicat {\tt renverser\_1} est moins efficace que le pr\'edicat 
	 {\tt renverser\_2}.
\begin	{alltt}
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
\end	{alltt}	

\item 	
	Soit le programme Prolog qui r\'esoud ``l'\'equation'' {\tt SEND + MORE = MONEY} :
\small
\begin	{alltt}
:- 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).
\end	{alltt}	
\normalsize

	\begin{enumerate}	
	\item	(2 points) Comparer et expliquer les diff\'erences de performance 
des appels\\ {\tt  mm1([S,E,N,D,M,O,R,Y])} et  
{\tt mm2([S,E,N,D,M,O,R,Y]) } (syntaxiquement ces pr\'edicats ne diff\`erent que 
par {\tt  generate1/1} et {\tt  generate2/1}).
	\item (2 points) Donner 2 ordonnancements de la liste [S,E,N,D,M,O,R,Y] pour le pr\'edicat 
	{\tt  generate1/1} qui acc\'el\`erent consid\'erablement les performances de {\tt  mm1/}. Expliquer.
	\end{enumerate}	
\item  Machine de
T\"uring d\'eterministe
	\begin{enumerate}	
	\item (3 points)	
Ecrire un interpr\`ete $t\_machine/2$ pour une machine de
T\"uring d\'eterministe. Cet interpr\`ete fera appel \`a un pr\'edicat
$transition/5$ qui sera d\'efini pour chaque langage.
\begin	{itemize}
\item	$t\_machine(Tape,Answer)$ :
	\begin	{itemize}
	\item	$Tape$: liste binaire qui contient le mot \`a lire sur le
		ruban,
	\item	$Answer$: liste binaire qui contient le r\'esultat de
		l'interpr\'etation ($ok$ ou $ko$), l'\'etat de la
		machine et l'\'etat du ruban.
	\end	{itemize}	
\item	$transition(Q_0,W_0,Q_1,W_1,D)$ :
	\begin	{itemize}
	\item	$Q_0$: l'\'etat de la machine avant la transition,
	\item	$W_0$: le caract\`ere se trouvant sous la t\^ete de lecture,
	\item	$Q_1$: l'\'etat de la machine apr\`es la transition,
	\item	$W_1$: le caract\`ere qui sera \'ecrit sur le ruban
		\`a la place  du caract\`ere se trouvant sous la
		t\^ete de lecture, 
	\item	$D$: le sens de d\'eplacement de la t\^ete de lecture.
	\end	{itemize}	
\end	{itemize}	

\item (3 points)	Ecrire les r\`egles de transition
pour les langages suivants:
\begin	{itemize}
\item	$a^{n}b^n$
\item	mots sur l'alphabet \{a,b\} dont la longueur est une puissance
de 2.
\end	{itemize}
\end{enumerate}	
	
\end{enumerate}	

\centerline{Annexe}
\subsection*{D\'efinition d'une machine de T\"uring d\'eterministe(rappel) }

Une machine de t\"uring d\'eterministe est un automate d\'efini par
$M=(Q,\Gamma,\Sigma,\delta,s,B,F)$ o\`u:
\begin	{itemize}
\item 	$Q$ est un ensemble fini d'\'etats,
\item 	$\Gamma$ est l'alphabet utilis\'e sur le ruban,
\item  	$\Sigma \subseteq \Gamma$  est l'alphabet utilis\'e pour le
	mot d'entr\'ee,
\item 	$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times
	\{L,R\} $ est la fonction de transition, 
\item 	$s \in Q$ est l'\'etat initial,
\item 	$B \in \Gamma - \Sigma$ est le symbole blanc (not\'e \#),
\item 	$F \subseteq  Q$ est l'ensemble des \'etats accepteurs.

\end	{itemize}	

Une configuration contient toute l'information n\'ecessaire pour
poursuivre l'ex\'ecution (i.e., l'\'etat, le mot \'ecrit sur le ruban
avant la t\^ete de lecture, le mot se trouvant entre la position de la
t\^ete de lecture et le dernier caract\`ere non blanc). 
Les configurations d\'erivable \`a partir de $(q,\alpha_1,b \alpha_2)$
sont :
\begin	{itemize}
\item 	 $(q',\alpha_1 b',\alpha_2)$ si $\delta(q,b)=(q',b',R)$
\item 	 $(q,\alpha_1',ab' \alpha_2)$ si $\delta(q,b)=(q',b',L)$ et
	$\alpha_1=\alpha_1'a$
\end	{itemize}	

\end{document}         



