\documentstyle{farticle}
\topmargin -3.5cm
\oddsidemargin -1cm
\evensidemargin -1cm
\textheight 27cm
\textwidth 18.0cm
\title{Examen1  Prolog  --- ESSI2  }
\author{Michel Rueher}

\begin{document}
\maketitle
\begin{center}
\thispagestyle{empty}
{\large Documents autoris\'es: {\it supports (et notes) de cours de TD}}
\end{center}	
\section{{\it QuickSort} en Prolog ---  12 points }
\begin{enumerate}
\item	Ecrire un programme Prolog ---bas\'ee sur le principe du {\it
	QuickSort}--- qui permet de trier une liste de cl\'es
	alphanum\'eriques.
\item	Optimisez ce programme en utilisant des ``listes de
	diff\'erence''.
\item	Donner la complexit\'e en espace de votre programme. Est il
	facile  d'optimiser l'occupation m\'emoire en Prolog ?\\
	Justifiez votre r\'eponse.
\end{enumerate}	
\subsection*{Rappel de l'algorithme du {\it QuickSort} }
\vspace*{6cm}
\section{Gestion d'une biblioth\`eque --- 8 points }

Soit une petite base de donn\'ees pour la gestion d'une biblioth\`eque
avec les transactions suivantes:
\begin{enumerate}
\item	Emprunt / Retour d'un exemplaire d'un livre,
\item 	Ajout / Suppression d'un exemplaire d'un livre dans la biblioth\`eque,
\item	Edition de la liste des livres pour un auteur ou pour un domaine particulier,
\item	Edition de la liste des livres  sortis par un emprunteur particulier,
\item	Edition du dernier emprunteur d'un livre donn\'e.
\end{enumerate}	
Il y a deux types d'utilisateurs du syst\`eme : les employ\'es de la biblioth\`eque
et les adh\'erents ordinaires. Les transactions 1, 2, 4 et 5 sont r\'eserv\'ees aux
employ\'es; les adh\'erents ont toutefois la possibilit\'e d'effectuer la
transaction 4 pour les livres qu'ils ont emprunt\'es.
La base de donn\'ees doit aussi satisfaire les contraintes suivantes:
\begin{itemize}
\item Tous les exemplaires d'un livre doivent \^etre emprunt\'es ou
      disponibles,
\item Aucun  exemplaire d'un livre ne doit \^etre en m\^eme temps emprunt\'es 
      et disponible,
\item Un emprunteur ne peut pas avoir emprunt\'e plus qu'un nombre fixe de
      livres \`a un momemt donn\'e. 
\end{itemize}	

D\'efinir une structure de donn\'ees pour g\'erer une telle
biblioth\`eque en Prolog. Ecrire les pr\'edicats correspondant aux
transactions 1 et 5.

\end{document}     


