G. Hunault  Licence Mass

Mini-projet en Algorithmique (octobre 96)

1. Introduction

On appelle ensemble d’entiers multivalués un ensemble dont les éléments peuvent être égaux et dont on compte les occurrences. Il ne s’agit donc pas d’ensembles au sens classique du terme. On convient de noter _{i}x un élément qui apparait i fois. L’ensemble classique A = {a, b, c} correspond donc à l’ensemble d’entiers multivalués {_{1}a,_{1}b,_{1}c} et l’ensemble d’entiers multivalués B = {_{2}a,_{1}b,_{1}c} contient les éléments a, a, b et c ou encore : a deux fois, b 1 fois, c 1 fois. Pour simplifier la notation, si i est égal à 0, on omettra d’indiquer l’élément et si i vaut 1, on utilisera la notation ”normale” x au lieu de _{1}x. A s’écrit donc {a, b, c} et B {_{2}a, b, c}.

Afin de se ramener à des structures de données classiques, on implémente les ensembles d’entiers multivalués par des matrices à deux colonnes, la colonne 1 donne x et la colonne 2 donne i. On impose que la matrice soit triée par ordre croissant d’élements. Pour l’ensemble d’entiers multivalués {4,_{2}1,_{3}6}, on utilise donc la matrice

1 2 4 1 6 3

2. Algorithmes de lecture

On suppose qu’un ensemble d’entiers multivalués E est défini par les lignes du fichier E.eme. Ecrire l’algorithme de lecture de ce fichier qui construit la matrice M de E. On utilisera les fonctions ouvre, mots... vues en cours. Attention : cet algorithme doit gérer un fichier comme

              1   2
              2   1
              3   1
              4   5
              1   2

et produire la matrice

1 4 2 1 3 2 4 5

soit l’ensemble d’entiers multivalués {_{4}1, 2,_{2}3,_{5}4}.

3. Union et intersection de deux ensembles d’entiers multivalués

Ecrire un algorithme qui, étant donné deux matrices d’ensembles d’entiers multivalués construit la matrice correspondant à l’ensemble d’entiers multivalués union des deux ensembles avec addition des nombres de fois. Ainsi {a, b} ∪ {a} vaut {_{2}a, b}.

Ecrire ensuite un algorithme qui, étant donné deux matrices d’ensembles d’entiers multivalués construit la matrice correspondant à l’ensemble d’entiers multivalués intersection des deux ensembles. Ainsi {_{4}a,_{5}b, c} ∪ {_{2}a,_{7}b} vaut {_{2}a,_{5}b}.

Ecrire les algorithmes des autres opérations classiques sur ensembles (différence symétrique, complémentaire...).

4. Tris des matrices d’ensembles d’entiers multivalués

Une matrice d’ensemble d’entiers multivalués est dite sous forme standard si ses lignes sont en ordre croissant de valeur puis éventuellement par nombre d’occurences croissant. Une matrice d’ensemble d’entiers multivalués est dite sous forme normalisée si ses lignes sont en ordre croissant du nombre d’occurences et ensuite éventuellement par ordre de valeur croissant. Ainsi la matrice X est quelconque, la matrice Y est sous forme normalisée et la matrice Z sous forme standard. On notera que ces matrice correspondent au même ensemble d’entiers multivalués.

2 4 1 1 5 2  1 1 5 2 2 4  1 1 2 4 5 2

Matrice X  Matrice Y  Matrice Z

Ecrire un algorithme qui convertit une matrice d’ensemble d’entiers multivalués M en une matrice sous forme standard S.

Ecrire ensuite un algorithme qui convertit une matrice d’ensemble d’entiers multivalués M en une matrice sous forme normalisée N.

5. Programmation en Lisp et en Apl

Traduire les différents algorithmes en programmes (ou fonctions) Lisp et Apl. On détaillera les problèmes de traduction, d’implémentation, le choix des structures de données, la syntaxe d’appel des modules... On pourra éventuellement inventer une fonction HAZAR(n) qui renverra une matrice d’ensemble d’entiers multivalués dont les n éléments sont 1,_{2}2..._{n}n pour automatiser la vérification et les jeux d’essais. On soignera la lecture sur fichier.

6. Remarques sur le miniprojet

Ce miniprojet est à réaliser seul(e). Vous avez certainement à effectuer une recherche bibliographique simple (indiquez vos sources, par exemple Web). Vous fournirez sur la disquette prévue à cet effet une zone de travail Apl (workspace), un fichier texte des fonctions Lisp ainsi qu’un document au sens Word pour Windows ou L^{A}TEXqui contiendra les algorithmes, la documentation et vos commentaires. Ces fichiers auront pour nom vos initiales. Jomes Band fournira donc Jb.ws, Jb.lsp et Jb.doc ou jb.tex ; par contre Nona Higane rendra nh.ws, nh.lsp, nh.doc ou nh.tex.

Ce travail de recherche, programmation et rédaction est à rendre pour le lundi 16 décembre, 14 h. (aucun retard ne sera toléré). Il vaut mieux rendre un travail incomplet que de ne rien rendre. La qualité des algorithmes, en particulier leur simplicité et leur lisibilité sera appréciée.

Indiquez clairement vos choix : si un terme vous parait ambigu, précisez sa définition pour vous. Justifiez vos modes de programmation, récursivité ou linéarité, appel d’opérateurs, de fonctions prédéfinies, écriture de boucles explicites... Nommez distinctement vos variables (en particulier utilisez systématiquement au moins 3 lettres par identificateur). N’hésitez pas à commenter sans toutefois dépasser un commentaire toutes les 8 lignes en moyenne (sauf pour l’en-tête).

Vous n’êtes pas obligé(e) de tout tester dans tous les sens. Affectuez donc des test élémentaires (positivité par exemple). L’affichage des résultats à l’écran devra être très propre et très soigné. Ainsi en cas d’affichage numérique multilignes, on mettra bien les unités sous les unités, les dizaines sous les dizaines etc.. Soignez aussi la rédaction, l’orthographe. Une erreur est pardonnable, sauf si un correcteur orthographique et grammatical la détecte...