% Document Type: LaTeX
% Master File: TP3.tex
% FILE. . . . . /users/formel2/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199798/TP3.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Verveine.Ens.Fr
% STARTED ON. . Mon Nov 17 13:57:22 1997
\documentstyle[a4]{article}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip
\bigskip

\centerline {TP num\'ero 3}
\centerline {semaine du 17 novembre 1997}
\bigskip
\bigskip
\bigskip
\centerline{\bf Manipulation de Fichiers et de Cha\^{\i}nes de Caract\`eres (Anagrammes)}


\section{Manipulation de fichiers}

Nous  souhaitons nous  constituer  ici une  librairie  de fonctions  utiles pour
travailler sur  des  fichiers   \emph{de taille  arbitraire}   que nous  voulons
consid\'erer comme vecteurs de \emph{lignes}, ce qui est une suite de caract\`eres
ne contenant pas le caract\`ere sp\'ecial \verb|'\n'| (fin de ligne) et termin\'ee
par \verb|'\n'|.\\

Nous allons repr\'esenter en m\'emoire des lignes par des cha\^{\i}nes de caract\`eres.\\


\subsection{Les cha\^{\i}nes de caract\`eres}

En C une cha\^{\i}ne de caract\`eres est \`a son tour un vecteur d'\'el\'ements
de type \verb|char|, donc on peut d\'eclarer ces objets de differentes fa\c{c}ons:

\begin{verbatim}
char *s; /* pointeur sur le debut de la chaine, sans allocation */

char *s = "majoliechaine"; /* pointeur sur le debut de la chaine,    */
                           /* allocation implicite et initialisation */

char s[100]; /* pointeur sur le debut de la chaine, allocation de 100 cases */

char s[100] = "monjolivecteur"; /* pointeur sur le debut de la chaine, */
                                /* allocation de 100 cases et initialisation */
\end{verbatim}

{\bf Attention:} certains compilateurs, dont \verb|gcc| consid\`erent la deuxi\`eme
declaration comme une declaration de \emph{constante}, donc vous ne pourrez pas
\'ecrire ensuite dans la cha\^{\i}ne \verb|"majoliechaine"|, \`a moins de compiler
votre programme avec des options cryptiques telles \verb|-fwritable-strings| 
(\`a temps perdu, faire man gcc pour plus d'infos).\\

Il  y a un  caract\`ere sp\'ecial,  \verb|'\0'| qui  indique la fin  d'une cha\^{\i}ne de
caract\`eres, et il faut bien s'assurer que toutes nos cha\^{\i}nes sont bien termin\'ees
ainsi dans nos programmes.\\


\subsection{Les fichiers}

Un fichier est une  structure de donn\'ee  persistente  qui contient une suite  de
octets.   Pour  manipuler un  fichier, on  doit  savoir  au moins  l'ouvrir,  le
refermer, le creer, le detruire et lire et \'ecrire son contenu.\\

En C, toute  ces op\`erations se  font en utilisant  des pointeurs sur  le type de
donn\'ee pred\'efini \verb|FILE|. Par exemple, le fragment de  code suivant ouvre le
fichier \verb|t|,  lit le  premier caract\`ere et  referme   le fichier (notez  le
traitement des erreurs).\\

\begin{verbatim}

FILE *pf;
char c;

    if ((pf=fopen("t","r"))==NULL) {printf("Erreur en ouvrant t.\n"); exit(1);};

    if ((c=getc(pf))==EOF) {printf("Fichier trop court\n");exit(2);}; 

    fclose(pf);

    /* reste du programme */

\end{verbatim}


\begin{exercise}[readline]
\'Ecrivez une fonction  \verb|int readline(FILE *fp, char **res)| qui lit sur le
fichier (d\'ej\`a ouvert) point\'e par \verb|fp| une \emph{ligne} termin\'ee par un \verb|'\n'|
et la m\'emorise dans un vecteur de charact\`eres termin\'e par \verb|'\0'|. Le r\'esultat
sera 1 si le fichier n'est pas fini, et 0 si on est arriv\'e \`a la fin du fichier.\\
Par contre, le pointeur sur la ligne lue sera renvoy\'e \`a l'appellant dans le deuxi\`eme
param\`etre, (et donc on est oblig\'e \`a demander que \verb|res| soit l'adresse du pointeur
de l'appellant, vu que C passe les param\`etres par valeur).\\
Tout \c{c}a est fait de fa\c{c}on \`a pouvoir \'ecrire une boucle comme
\begin{verbatim}
char *buf;

while (readline(fp,&buf)!= 0)
  {
	/* fait qque chose avec buf */
};

\end{verbatim}
{\bf Attention:} comme nous sommes des programmeurs s\'erieux, notre fonction doit
\^etre capable de g\'erer des lignes de taille arbitraire. Utilisez donc la m\'ethode
d'allocation dynamique vue en cours (dont le co\^ut amorti est lin\'eaire).\\
\end{exercise}

\begin{exercise}[readfile]
\'Ecrivez maintenant une fonction qui lit tout un fichier sous forme de vecteur de lignes.
On veut donc \verb|int readfile(char *filename, char ***lignes)| qui renvoie un code
d'erreur entier (succ\'es, erreur de lecture etc.) et qui ouvre le fichier de nom \verb|filename|
et rende dans \verb|*lignes| le pointeur a un vecteur de lignes (i.e.\ \`a un \verb|char **|).\\
Encore une fois, faites de l'allocation dynamique.\\
\end{exercise}

\begin{exercise}[optionnel] 
Modifiez  la fonction  \verb|readfile| de  fa\c{c}on que  si  le nom  de fichier est
\verb| - | l'op\'eration soit effectu\'ee sur l'entr\'ee standard.\\
\end{exercise}

\begin{exercise}[Comparez deux lignes]  \'Ecrivez une fonction de  comparaisons de
cha\^{\i}nes de caract\`eres \verb|int comparelines(char **a, char **b)| qui prend deux
pointeurs sur des cha\^{\i}nes de  caract\`eres et les compare lexicographiquement.  Le
r\'esultat doit \^etre un entier positif, 0 o\`u un entier n\'egatif selon que la cha\^{\i}ne
\verb|*a| soit plus grande, \'egale ou plus petite que \verb|*b|.\\
\end{exercise}

\begin{exercise}[Trier un fichier] \'Ecrivez  un programme \verb|trie| qui trie en
ordre croissant un fichier dont le nom est pass\'e sur la ligne de commande. (Oui,
c'est  vrai, on ne sait pas  encore \'ecrire une fonction de  tri, mais cela n'est
pas  grave:  faites  \verb|man  qsort|  et utilisez   la  fonction de  librairie
\verb|qsort|).
\end{exercise}

\section{Anagrammes}

En utilisant les  fonctions  de la  section  pr\'ec\'edante, \'ecrivez  maintenant  un
programme qui  lit un fichier  contenant  une liste  de mots  un  par ligne  (un
dictionnaire), et  donne sur la  sortie standard  tous  et seuls les  anagrammes
contenus dans ce dictionnaire. Par exemple, si le dictionnaire est

\begin{verbatim}
inse'parabilite' 
malle'abilite' 
alte'rabilite'
bilate'ralite' 
radiote'le'graphie 
te'le'radiographie 
\end{verbatim}

on veut en sortie seulement les anagrammes

\begin{verbatim}
alte'rabilite' bilate'ralite' 
radiote'le'graphie te'le'radiographie 
\end{verbatim}

Bien entendu,  on vous demande de faire  cela en temps  moyen $O(n  log(n))$, en
sachant que $qsort$ d\'emande  en moyenne un  temps  $O(n log(n))$.\\ Vous  pouvez
tester votre programme sur  le petit dictionnaire fran\c{c}ais  qui se trouve sur la
machine    \verb|clipper|        dans   \verb|~dicosmo/MiniDico|      (ou  aussi
\verb|~dicosmo/MiniDicoAccents| pour la version avec lettres accentu\'ees).

\section{Occurrence de mots dans un texte.}

Un de vos copains de lettres  vous demande si  vous pouvez l'aider \`a trouver les
100  mots les plus   utilis\'es par Racine dans ses   oeuvres, qui viennent d'\^etre
digitalis\'ees sur un CD-Rom.  Expliquez comment r\'esoudre efficacement ce probl\`eme
en temps $O(n log(n))$,  et en effet, pour  un $k$ quelconque, non pas seulement
100.\\  Ensuite,  r\'ealisez  votre  algorithme    \`a  l'aide  des  commandes  Unix
\verb|sort| \verb|head| et \verb|uniq|.\\


{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
\end{document}
