Examen1 Prolog — ESSI2

Michel Rueher 30 mars 1995

Documents autorisés: supports (et notes) de cours de TD

1 QuickSort en Prolog — 12 points

1. Ecrire un programme Prolog —basée sur le principe du QuickSort— qui permet de trier une liste de clés alphanumériques.

2. Optimisez ce programme en utilisant des “listes de différence”.

3. Donner la complexité en espace de votre programme. Est il facile d’optimiser l’occupation mémoire en Prolog ? Justifiez votre réponse.

Rappel de l’algorithme du QuickSort

2 Gestion d’une bibliothèque — 8 points

Soit une petite base de données pour la gestion d’une bibliothèque avec les transactions suivantes:

1. Emprunt / Retour d’un exemplaire d’un livre,

2. Ajout / Suppression d’un exemplaire d’un livre dans la bibliothèque,

3. Edition de la liste des livres pour un auteur ou pour un domaine particulier,

4. Edition de la liste des livres sortis par un emprunteur particulier,

5. Edition du dernier emprunteur d’un livre donné. Il y a deux types d’utilisateurs du système : les employés de la bibliothèque et les adhérents ordinaires. Les transactions 1, 2, 4 et 5 sont réservées aux employés; les adhérents ont toutefois la possibilité d’effectuer la transaction 4 pour les livres qu’ils ont empruntés. La base de données doit aussi satisfaire les contraintes suivantes:

• Tous les exemplaires d’un livre doivent être empruntés ou disponibles,

• Aucun exemplaire d’un livre ne doit être en même temps empruntés et disponible,

• Un emprunteur ne peut pas avoir emprunté plus qu’un nombre fixe de livres à un momemt donné. Définir une structure de données pour gérer une telle bibliothèque en Prolog. Ecrire les prédicats correspondant

aux transactions 1 et 5.