% miniprojet96.tex
%
\def\eme{{\it ensemble d'entiers multivalu\'{e}s}}
\def\emes{{\it ensembles d'entiers multivalu\'{e}s}}
\def\ems{{ensembles d'entiers multivalu\'{e}s}}
%
\documentclass[12pt]{article}
\renewcommand{\thesection}{\arabic{section}. }
\parindent 0cm
\parskip 0.5cm
%
\begin{document}
{\Large
 \begin{tabular}{lr}
 \hspace{-0.5cm} G. Hunault & \hspace{4cm} \textit{Licence Mass}\\[1cm]
 \end{tabular}
 }% fin de large

\begin{center}
{\bf \LARGE Mini-projet en Algorithmique
(octobre 96)\\[2.5cm]
}
\end{center}
\thispagestyle{empty}
\section{Introduction}

On appelle \eme\ un ensemble dont les \'{e}l\'{e}ments peuvent \^{e}tre \'{e}gaux et dont on compte les
occurrences. Il ne s'agit donc pas d'ensembles au sens classique du terme.
On convient de noter ${}_ix$ un \'{e}l\'{e}ment qui apparait $i$ fois.
L'ensemble classique $A=\{a,b,c\}$ correspond donc \`{a} l'\eme\
$\{{}_1a, {}_1b, {}_1c\}$
et l'\eme\ $B=\{ {}_2a, {}_1b, {}_1c\}$ contient les \'{e}l\'{e}ments $a$, $a$, $b$ et $c$
ou encore~:~$a$ deux fois, $b$ 1 fois, $c$ 1 fois. Pour simplifier la notation,
si $i$ est \'{e}gal \`{a} $0$, on omettra
d'indiquer l'\'{e}l\'{e}ment et si $i$ vaut $1$, on utilisera la notation "normale" $x$ au lieu
de $ {}_1x$. $A$ s'\'{e}crit donc $\{a,b,c\}$ et $B$ $\{ {}_2a,b,c\}$.

Afin de se ramener \`{a} des structures de donn\'{e}es classiques, on impl\'{e}mente
les \emes\ par des matrices \`{a} deux colonnes,
la colonne 1 donne $x$ et la colonne 2 donne $i$.
On impose que la matrice soit tri\'{e}e par ordre croissant d'\'{e}lements.
Pour l'\eme\ $\{4, {}_21, {}_36\}$,
on utilise donc la matrice

\begin{center}
\begin{tabular}{|c|c|}
 \hline
 1 & 2 \\ \hline
 4 & 1 \\ \hline
 6 & 3 \\ \hline
\end{tabular}
\end{center}

\section{Algorithmes de lecture}

On suppose qu'un \eme\ $E$ est d\'{e}fini par les lignes du fichier {\texttt 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\'{e}rer un fichier comme

\begin{center}
\begin{verbatim}
              1   2
              2   1
              3   1
              4   5
              1   2
\end{verbatim}
\end{center}

et produire la matrice

\begin{center}
\begin{tabular}{|c|c|}
 \hline
 1 & 4 \\ \hline
 2 & 1 \\ \hline
 3 & 2 \\ \hline
 4 & 5 \\ \hline
\end{tabular}
\end{center}

soit l'\eme\ $\{ {}_41, 2,  {}_23,  {}_54\}$.

\section{Union et intersection de deux \ems}

Ecrire un algorithme qui, \'{e}tant donn\'{e} deux matrices d'\emes\
construit la matrice correspondant \`{a} l'\eme\ union
des deux ensembles avec addition des nombres de fois. Ainsi $\{a,b\}\ \cup\ \{a\}$  vaut
$\{ {}_2a,b\}$.


Ecrire ensuite un algorithme qui, \'{e}tant donn\'{e} deux matrices d'\emes\
construit la matrice correspondant \`{a} l'\eme\ intersection
des deux ensembles. Ainsi $\{ {}_4a, {}_5b, c\}\ \cup\ \{ {}_2a, {}_7b\}$  vaut
$\{ {}_2a, {}_5b\}$.

Ecrire les algorithmes des autres op\'{e}rations classiques sur ensembles (diff\'{e}-rence sym\'{e}trique, compl\'{e}mentaire...).

\section{Tris des matrices d'\ems}

Une matrice d'\eme\ est dite sous forme standard si ses lignes sont en
ordre croissant de valeur puis \'{e}ventuellement par nombre d'occurences croissant.
Une matrice d'\eme\ est dite sous forme normalis\'{e}e si ses lignes sont en ordre croissant du nombre
d'occurences et ensuite \'{e}ventuellement par ordre de valeur croissant. Ainsi la matrice $X$ est quelconque,
la matrice $Y$ est sous forme normalis\'{e}e et la matrice $Z$ sous forme standard. On notera que ces
matrice correspondent au m\^{e}me \eme.

\begin{center}
\begin{tabular}{ccccc}
{\begin{tabular}{|c|c|}
\hline
2 & 4 \\ \hline
1 & 1 \\ \hline
5 & 2 \\ \hline
\end{tabular}} & &
{\begin{tabular}{|c|c|}
\hline
1 & 1 \\ \hline
5 & 2 \\ \hline
2 & 4 \\ \hline
\end{tabular}} & &

{\begin{tabular}{|c|c|}
\hline
1 & 1 \\ \hline
2 & 4 \\ \hline
5 & 2 \\ \hline
\end{tabular}} \\[1.cm]
Matrice $X$ & \hspace{2cm} & Matrice $Y$ & \hspace{2cm} & Matrice $Z$
\end{tabular}
\end{center}

Ecrire un algorithme  qui convertit une matrice d'\eme\ $M$ en une matrice sous forme standard $S$.

Ecrire ensuite un algorithme  qui convertit une matrice d'\eme\ $M$ en une matrice sous
forme normalis\'{e}e $N$.

\section{Programmation en Lisp et en Apl}

Traduire les diff\'{e}rents algorithmes en programmes (ou fonctions) Lisp et Apl. On d\'{e}taillera
les probl\`{e}mes de traduction, d'impl\'{e}mentation, le choix des structures de donn\'{e}es, la syntaxe
d'appel des modules... On pourra \'{e}ventuellement inventer une fonction $HAZAR(n)$ qui renverra une
matrice d'\eme\ dont les $n$ \'{e}l\'{e}ments sont $1,{}_22...{}_nn$ pour automatiser la v\'{e}rification et les
jeux d'essais. On soignera la lecture sur fichier.

\section{Remarques sur le miniprojet}

Ce miniprojet est \`{a} r\'{e}aliser seul(e). Vous avez certainement \`{a} effectuer une recherche bibliographique
simple (indiquez vos sources, par exemple Web). Vous fournirez sur la disquette pr\'{e}vue \`{a} cet effet
une zone de travail Apl (\textit{workspace}), un fichier texte des fonctions Lisp ainsi qu'un document
au sens \textit{Word pour Windows} ou \LaTeX qui 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\'{e}daction est \`{a} rendre pour le \textbf{lundi 16 d\'{e}cembre,
14 h.} (aucun retard ne sera tol\'{e}r\'{e}). Il vaut mieux rendre un travail incomplet que de ne rien rendre.
La qualit\'{e} des algorithmes, en particulier leur simplicit\'{e} et leur lisibilit\'{e} sera appr\'{e}ci\'{e}e.

Indiquez clairement vos choix~:~si un terme vous parait ambigu, pr\'{e}cisez sa d\'{e}finition pour vous.
Justifiez vos modes de programmation, r\'{e}cursivit\'{e} ou lin\'{e}arit\'{e},
appel d'op\'{e}rateurs, de fonctions pr\'{e}d\'{e}finies,
\'{e}criture de boucles explicites... Nommez distinctement vos variables (en particulier utilisez
syst\'{e}-matiquement au moins 3 lettres par identificateur). N'h\'{e}sitez pas \`{a} commenter sans toutefois
d\'{e}passer un commentaire toutes les 8 lignes en moyenne (sauf pour l'en-t\^{e}te).
\newpage
Vous n'\^{e}tes pas oblig\'{e}(e) de tout tester dans tous les sens. Affectuez donc des test
\'{e}l\'{e}mentaires (positivit\'{e} par exemple). L'affichage des r\'{e}sultats \`{a} l'\'{e}cran devra \^{e}tre
tr\`{e}s propre et tr\`{e}s soign\'{e}. Ainsi en cas d'affichage num\'{e}rique multi-lignes, on mettra bien les unit\'{e}s
sous les unit\'{e}s, les dizaines sous les dizaines \textit{etc.}. Soignez aussi la r\'{e}daction, l'orthographe.
Une erreur est pardonnable, sauf si un correcteur orthographique et grammatical la d\'{e}tecte...

\end{document}
