% Document Type: LaTeX
% Master File: TP98_8.tex
% FILE. . . . . /users/formel/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199899/TP98_8.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Localhost
% STARTED ON. . Fri Jan  8 22:57:14 1999



\documentclass{article}
\usepackage[francais]{babel}
\usepackage{a4}
\usepackage{alltt}
\usepackage{graphicx}
% *****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

\centerline {TP num\'ero 7}
\centerline {semaine du 11 janvier 1999}
\bigskip
\centerline{\bf Programmation en binome: de LCS/SES \`a Diff}
\stepcounter{section}

Nous allons  continuer notre  experience de  programmation  \`a plusieurs en  nous
attaquant \`a un autre probl\`eme  qui peut \^etre ais\'ement  decompos\'e. Il s'agira ici
de re\'ecrire (une   version   simplifi\'ee) de   l'utilitaire  Unix qui   s'appelle
\verb|diff|.

\subsection*{Le probl\`eme}
%
Il s'agit de comparer deux fichiers A et  B et d'afficher les diff\'erences: cette
op\'eration  est  bien pratique pour  garder une  trace  des modifications sur des
fichiers, pour transmettre seulement les modifications (\emph|patches|) quand on
change de   version des sources,  pour  garder de fa\c{c}on  compacte l'ensemble des
diff\'erentes versions d'un document  (voyez la page  de manuel de  \verb|rcs| par
exemple), etc. \\

Les diff\'erences peuvent \^etre affich\'ees de diff\'erentes fa\c{c}ons, mais la plus
utile est sous la forme d'un ``edit script'', i.e.\ une s\'equence de commandes
d'\'editions ayant la forme suivante
  \begin{itemize}
    \item {\Large $n$a$i,k$} Cela indique que \`a la ligne $n$ du fichier A
          il faut rajouter les lignes $i$ \`a $k$ du ficher B qui sont donn\'ees
          apr\`es la commande (on omet $,k$ si $k=i$)
    \item {\Large $n,m$c$i,k$} Cela indique qu'il faut changer les lignes
          $n$ \`a $m$ du fichier A par les lignes $i$ \`a $k$ du fichier B, et
          apr\`es la commande on donne les lignes du fichier A, suivies d'une
          ligne de 3 tirets, suivies des lignes du fichier B (on omet $,m$ si $n=m$ et $,k$ si $k=i$)
    \item {\Large $n,m$d$i$} Cela indique qu'il faut effacer du fichier A
          les lignes $n$ \`a $m$ pour se retrouver align\'es \`a la ligne $i$ du
          fichier B (on omet $,m$ si $n=m$)
  \end{itemize}

Une  s\'equence d'instructions d'\'editions pour   transformer le fichier A dans  le
fichier B  comme   celles-ci  a la   tr\`es agr\'eable  propri\'et\'e  de pouvoir   \^etre
facilement  convertie en une sequence  d'instruction pour convertir le fichier B
dans le fichier A: il suffit de  transformer $n$a$i,k$ en $i,k$d$n$ et viceversa
et d'inverser $n,m$c$i,k$ en $i,k$c$n,m$ (en pr\'enant soin aussi d'inverser les
blocs avant et apres la ligne de 3 tirets).

Par exemple, sur les deux fichiers contenant les lignes montrees ici dans
le dessin
  \begin{center}
    \includegraphics[width=28em]{DIFF.eps}
  \end{center}
\verb|diff| rendra la s\'equence d'instructions d'\'edition suivante:

\begin{alltt}
2d1
< B
3a3
> H
5c5
< E
---
> G
\end{alltt}

\subsection*{Utiliser LCS/SES}

Le probl\`eme de  produire un plus court ``edit   script'' (SES) est isomorphe  au
probl\`eme  de calculer une  plus   longue sous-s\'equence  commune (LCS): si   vous
calculez la plus longue  sous-s\'equence commune en pr\'enant  soin de  garder trace
des indices dans les  deux s\'equences \`a comparer,   il est facile de  produire le
script.\\

Mais dans les cas d'un fichier, les  ``\'el\'ements'' d'une s\'equence sont des lignes
enti\'eres, et il serait peu pratique (et bien couteux) de calculer la LCS sur des
vecteurs contenant  les fichiers ligne  par ligne: cela necessiterait d'utiliser
une fonction de  comparaison de ligne, dont  le cout n'est  pas  $O(1)$.\\

On peut simplifier la t\^ache de la fa\c{c}on suivante:

\begin{itemize}
  \item on construit \`a partir des deux vecteurs de lignes (obtenus en lisant chaque
        fichier) un dictionnaire associant une clef entiere diff\'erente \`a chaque ligne
        diff\'erente (et le m\^eme entier \`a toutes les lignes \'egales). \\
        Pour cela, on peut utiliser une fonction d'hachage.
  \item En m\^eme temps, on construit deux vecteurs d'entiers contenant les cl\'es
        et non pas les lignes.
  \item On appelle SES sur les vecteurs des clefs.
  \item On transforme l'``edit script'' sur les clefs rendu par SES en ``edit script''
        sur les lignes.
\end{itemize}

\subsection*{L'interface}

Nous assumons que la  fonction  SES rendra le script sous la forme d'un vecteur
de commandes d'edition simplifi\`ees, sans les lignes \`a rajouter ou changer, i.e.\ 
dans l'exemple d'en haut:
\begin{alltt}
2d1
3a3
5c5
\end{alltt}

Et nous separons maintenant le programme en deux modules: un qui calcule la SES,
et l'autre qui g\^ere la lecture des fichiers, la g\'en\'eration des vecteurs de clefs
et l'impression du script d'edition complet.

Comme interface, on pourra utiliser par exmple  un fichier \verb|ses.h| comme le
suivant:

\begin{verbatim}
/* une structure pour les commandes d'edition*/
typedef struct {
		char action; /* a,d ou c */
                int rangea_1; /* n */
                int rangea_2; /* m */
                int rangeb_1; /* i */
                int rangeb_2; /* k */
		} e_cmd;

/* la fonction SES */

int SES(int *vect1, int l1, int *vect2, int l2, e_cmd **script);

\end{verbatim}

\newpage

\subsection{T\^aches du programmeur A}

\begin{exercise}[Programmation  de  {\tt diff}]  \'Ecrivez une  fonction 
\verb|int  diff(char *fn1, char *fn2)|  qui utilise la  fonction \verb|SES| pour
calculer la diff\'erence entre deux fichiers.
\end{exercise}

\begin{exercise}[Am\'eliorations] Modifier votre fonction pour permettre de ne pas
tenir compte des diff\'erences produites  par des s\'equences d'espaces de  longuers
diff\'erentes.
\end{exercise}

\subsection{T\^aches  du programmeur   B} \begin{exercise}[Programmation de   SES]
Programmez la fonction SES (il peut \^etre utile, pour la tester, de pr\'evoir aussi
l'impression de la sousequence commune). Quel est sa complexit\'e, en espace et en
temps?
\end{exercise}

\begin{exercise}[Am\'eliorations] Cherchez "An O(ND)  Difference Algorithm and its
Variations",  par Eugene Myers,  qui se trouve dans Algorithmica  Vol. 1 No.  2,
1986, pp. 251-266  (il  est \`a   la  bibliotheque). Implementez la   variante qui
utilise espace lin\'eaire pour calculer le r\'esultat.
\end{exercise}

\subsection{T\^aches communes \`a A et B}
\begin{exercise}
Compilez ensembe vos deux modules et \ldots{} comparez avec \verb|diff|.
\end{exercise}


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


