%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Tronc commun info X                        %
%         pc 2  (Java)                          %
%   version du 13 novembre 98                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}
\newcommand{\titre}[1]{\begin{center}{\huge \bf #1}\end{center}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 22-4-91
%
%            FIGURES
%            (LaTeX)
%
% -------------------------------------------------------
%\Lafig{nom}{largeur}{hauteur}{echelle}{legende}
% -------------------------------------------------------
% Exemple  \Lafig{elle}{94mm}{58mm}{400}{ Le {\sl Diagramme} de $N^2$}
% Elle a largeur 94mm, hauteur 58mm, une reduction a 40 %,
% le nom symbolique "elle", par lequel est peut etre refencee dans le texte
% et la legende "Le diagramme..."
%
% -------------------------------------------------------
\def\FiguresParSection{\@addtoreset{figure}{section}
\def\thefigure{\arabic{section}.\arabic{figure}}}
%
\def\FiguresParChapitre{\@addtoreset{figure}{chapter}
\def\thefigure{\thechapter.\arabic{figure}}}
%
\def\FiguresParChapitreEtSection{\@addtoreset{figure}{section}
\def\thefigure{\thesection.\arabic{figure}}}
%
% Auxiliares
%
% de "pic example" :
\def\mapicture #1 by #2 (#3){
  \vbox {\hbox {\lower #2 \hbox
    {\special{picture #3}}} % this is the low-level interface
    \hrule width #1 height 0pt depth 0pt
    \vfill
    }
  }
%
\def\scaledpicture #1 by #2 (#3 scaled #4){{
  \dimen0=#1 \dimen1=#2
  \divide\dimen0 by 1000 \multiply\dimen0 by #4
  \divide\dimen1 by 1000 \multiply\dimen1 by #4
  \mapicture \dimen0 by \dimen1 (#3 scaled #4)}
  }
%
% De mon cru ...Lafig
% arg 1 = nom de l'image
% arg 2 = largeur, telle que vue dans fenetre
% arg 3 = hauteur, telle que vue dans fenetre
% arg 4 = facteur d'echelle (sur 1000) : 600 ok
% arg 5 = l\'egende
\newskip\avantfigureskip\avantfigureskip=\bigskipamount
\newskip\apresfigureskip\apresfigureskip=\medskipamount
% La nouvelle version des figures
\newcommand{\Lafig}[5]{
\begin {figure}[hbt]
  \vskip\avantfigureskip       %    Un peu de place avant
  $$\hbox{\scaledpicture #2 by #3 (#1 scaled #4)}$$  % L'image centree
  \centerline{\small Figure \refstepcounter{figure}\thefigure.\ \ \sl #5
\label{#1}}  % Legende
  \par\vskip\apresfigureskip  %    Un peu de place apres

\addcontentsline{lof}{figure}{\protect\numberline{\thefigure}{\ignorespaces
#5}}
\end {figure}}
% Fin de la definition
%
% Variante : sans numero
%
\newcommand{\LafigSansNumero}[5]{
\begin {figure}[hbt]
  \vskip\avantfigureskip       %    Un peu de place avant
  $$\hbox{\scaledpicture #2 by #3 (#1 scaled #4)}$$  % L'image centree
  \centerline{\small \sl #5 }  % Legende
  \par\vskip\apresfigureskip  %    Un peu de place apres
\end {figure}}
%
%             Fin Figures
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagestyle{headings}
\markright{pc 2 : tri et recherche}
\begin{document}
\LARGE



{\huge \bf
\begin{center}
PC 2\\
 Algorithmes de tri et de recherche
\end{center}}

\vspace{10mm}

  \begin{itemize}
\item Complexit\'e des algorithmes

\item Algorithmes de tri


\item Algorithmes de recherche
		\begin{itemize}
\item Recherche s\'{e}quentielle
		\item Recherche dichotomique
		\item Hachage
		\end{itemize}

\end{itemize}
\pagebreak
\begin{center}
{\huge \bf Complexit\'{e} des algorithmes}
\end{center}
\vspace{10mm}
Donn\'{e}e de taille $n$
\begin{itemize}
\item Temps de calcul $T(n)$
\item Espace m\'{e}moire utilis\'{e} $E(n)$
\end{itemize}
Evaluation: \begin{itemize}
	\item En moyenne
	\item Au pire des cas
	\end{itemize}
Calcul \`a une constante multiplicative pr\`es: pas d'unit\'{e} de
temps ou d'espace.


Pour deux fonctions r\'{e}elles positives $f$ et $g$, on \'{e}crit
\[f=O(g)\]
si $f$ ne croit pas plus vite que $g$~:
\[\exists C,N\geq 0,\ \forall n\geq N,\ 
 f(n)\leq Cg(n)
\]
On \'ecrit aussi \[f=\Omega(g)\mbox{ pour }g=O(f)\]
 et
\[f=\Theta(g)\mbox{ pour }f=O(g)\mbox{ et }g=O(f).\]


\pagebreak



\begin{center}
{\huge \bf Algorithmes de tri}
\end{center}

\noindent {\em Donn\'{e}e} : $N$ nombres entiers $$a[0],a[1],
\ldots ,a[N-1]$$


\noindent {\em R\'{e}sultat} : R\'{e}arrangement croissant \linebreak
$b[0],b[1],
\ldots ,b[N-1]$ des nombres $a[i]$.

\vspace{5mm}

\noindent {\em Autre formulation} : Recherche de la per\-mutation $\pi$
de $\{0,1,\ldots ,N-1\}$ telle que 
\[a[\pi[i]]=b[i]\]
L'entier $\pi(i)$ est la place dans $a$ du $i$-\`eme \'el\'ement de $b$.

\noindent {\em Exemple}:
\begin{eqnarray*} 
a&=&\begin{tabular}{|c|c|c|c|c|}
\hline 24 &5 &81 &2 &45\\ \hline
\end{tabular}\\
b&=&\begin{tabular}{|c|c|c|c|c|}
\hline 2 &5 &24 &45 &81\\ \hline
\end{tabular}\\
\pi&=&\begin{tabular}{|c|c|c|c|c|}
\hline 4 &2 &\ 1  &\ 5 \, &\ 3  \\ \hline
\end{tabular}
\end{eqnarray*} 
{\em Complexit\'e}~: $O(n^2)$ pour les sch\'emas simples et
$O(n\log n)$ pour les plus \'elabor\'es. 

\pagebreak

\begin{center}
{\huge \bf Tri par insertion}
\end{center}

\noindent {\em Principe}: A la $i$-\`eme \'{e}tape, ins\'{e}rer $a[i]$
parmi $a[0],a[1],\ldots ,a[i-1]$.


\vspace{5mm}




\begin{verbatim}
static void triInsertion() {
  int i,j,v;

  for (i=1; i< N; ++i) {
    v = a[i]; j = i;
    while (j>0 && a[j-1] > v) {
      a[j] = a[j-1];
      --j;
    }
    a[j] = v;
  }
}
\end{verbatim}

\noindent {\em Temps de calcul}: $\Theta(n^2)$ au pire des cas
et en moyenne.
\pagebreak

\titre{Programme complet}
\begin{verbatim}
class TriInsertion {
  final static int N = 10;
  static int[] a = new int[N];
  static void initialisation() {
    for (int i= 0; i< N; i++)
      a[i] = (int) (Math.random() * 128);
  }
  static void impression() {
    for (int i= 0; i< N; i++)
      System.out.print(a[i]+ " ");
      System.out.println();
  }
  static void triInsertion() {...}
  public static void main(String[] args) {
    initialisation();
    impression();
    triInsertion();
    impression();
  }
}
\end{verbatim}
\pagebreak

\begin{center}
{\huge \bf Tri de la bulle}
\end{center}
\noindent {\em Principe}: Faire venir en $a[i]$ l'\'{e}l\'{e}ment
minimum de $a[i],a[i+1],\ldots ,a[N-1]$ par \'{e}change d'\'{e}l\'{e}ments
adjacents ({\it les \'{e}l\'{e}\-ments l\'{e}gers montent}).


\[\begin{tabular}{|c|} \hline 5\\ \hline 2\\ \hline 1\\ \hline 3\\ \hline 4\\ \hline \end{tabular}\:\:
\begin{tabular}{|c|} \hline 1\\ \hline 5\\ \hline 2\\ \hline 3\\ \hline 4\\ \hline \end{tabular}\:\:
\begin{tabular}{|c|} \hline 1\\ \hline 2\\ \hline 5\\ \hline 3\\ \hline 4\\ \hline \end{tabular}\:\:
\begin{tabular}{|c|} \hline 1\\ \hline 2\\ \hline 3\\ \hline 5\\ \hline 4\\ \hline \end{tabular}\:\:
\begin{tabular}{|c|} \hline 1\\ \hline 2\\ \hline 3\\ \hline 4\\ \hline 5\\ \hline \end{tabular}
\]
\begin{verbatim}
static void triBulle() {
  int i, j, t;
  for (i= 0; i< N; ++i)
    for (j= N-1; j> i; --j)
      if (a[j-1] > a[j]) {
        t= a[j-1]; a[j-1]= a[j]; a[j]= t;
      }
}
\end{verbatim}
\noindent {\em Complexit\'{e}}: $\Theta(n^2)$ au pire des cas et en moyenne.
\pagebreak

\begin{center}
{\huge \bf Analyse en moyenne}
\end{center}

On raisonne sur la permutation $\pi$ don\-nant la place du $i$-\`eme
\'{e}l\'{e}ment. 
Une {\em inver\-sion} de $\pi$ est une paire $(i,j)$ d'indi\-ces telle
que $i<j$ et $\pi[i]>\pi[j]$. 
Chaque \'{e}change de deux \'{e}l\'{e}ments de $a$ par l'al\-gorithme supprime
exactement une inversion de $\pi$.
Le nombre d'\'{e}changes est donc \'{e}gal au nombre d'inversions de $\pi$.

Or le nombre moyen d'inversions d'une permu\-ta\-tion\footnote{\large le nombre
total d'inversions de $\pi$ et de la  permutation $\tilde{\pi}$ image
miroir de $\pi$ est $N(N-1)/2$} est
\[\frac{N(N-1)}{4}\]
d'o\`u une complexit\'{e} moyenne en $\Theta(N^2)$
\pagebreak
 
\titre{Algorithmes de recherche}
But : consultation et mise \`a jour d'un ensemble de donn\'ees
avec les fonctions de
\begin{itemize}
\item Recherche
\item Insertion
\item Suppression
\end{itemize}
On s'int\'eresse \`a des ensembles de $N$ \'el\'ements
avec $N$ \'eventuellement tr\`es grand ($N\approx$ 1Gigabit)


\pagebreak
\begin{center}
{\huge \bf Recherche s\'{e}quentielle}
\end{center}

Recherche d'un entier $v$ dans la table $$a[0],a[1],\ldots ,a[N-1]$$


\begin{verbatim}
static int Recherche(int v) {
  for (int i=0; i < N; i++)
    if (v == a[i]) return i;
  return -1;
}
\end{verbatim}


\noindent {\em Complexit\'{e}}: $\Theta(N)$ (avec $N/2$
op\'{e}rations en moyenne).

 En pratique: environ 1mn pour
1 Giga \'{e}l\'{e}ments (si on fait $10^7$ comparaisons/s).
\pagebreak

\begin{center}
{\huge \bf Recherche dichotomique}
\end{center}

\noindent{\em Hypoth\`ese}: La table est {\em ordonn\'{e}e}:
$$a[0]<a[1]<\ldots <a[N-1]$$

\begin{verbatim}
static int Dicho (int v) {
  int i, g, d;
  g= 0; d= N-1;
  while (g <= d) {
    i=(g+d)/2;
    if (v == a[i]) return i;
    if (v < a[i]) d= i-1;
    else g= i+1;
  }
  return -1;
}
\end{verbatim}



\noindent {\em Complexit\'{e}}: $\Theta(\log N)$. Pour $N=10^4$,
on a 14 comparaisons environ au lieu de 5000 pour la recherche
s\'{e}quentielle.
\pagebreak
\titre{Dichotomies}
Si, pour $n\geq 1$
\[T(n)\leq T(n/2)+a\]
alors


\[\begin{array}{|c|} \hline
T(n)=O(\log n)\\ \hline
\end{array}
\]
D\'emonstration~: il suffit de v\'erifier par r{\'e}cur\-ren\-ce sur $n$ que
\[T(n)\leq a\log n + b\]
avec $b=T(0)$.
\pagebreak

\begin{center}
{\huge \bf Hachage}
\end{center}

{\em Principe}: on utilise une fonction
\[h:E\rightarrow [0..N-1]\]
telle que $a[h(x)]=x$. La recherche devient imm\'{e}diate.

\Lafig{hachage}{81mm}{82mm}{700}{}

{\em Probl\`emes}:
\begin{itemize}
\item Choix de la fonction de hachage. Par exemple, 
\[h(x)=x \bmod N\]
\item Gestion des {\em collisions}:
$x\neq x'$ avec $h(x)=h(x')$. Deux solutions:
\begin{enumerate}
\item hachage ouvert: on g{\`e}re des listes d'\'{e}l\'{e}ments de
m\^eme cl\'{e}.
\item hachage ferm\'{e}: on utilise des valeurs de {\em remplacement}.
\end{enumerate}
\end{itemize}


\begin{center}
{\huge \bf Hachage ferm{\'{e}}}
\end{center}

{\em Principe}: On utilise une suite de fonctions
de hachage $h_1(x),h_2(x),\ldots $ pour ranger $x$.
Par exemple:
\[h_i(x)=h(x)+i\bmod N\]
(hachage lin\'{e}aire) ou encore
\[h_i(k)=h(k)+ih'(k)\bmod N\]
(hachage double).

 On choisit $h'$ de fa\c{c}on que $N$ et $h'(k)$ soient
toujours premiers entre eux (par exemple $N$ est une puissance de 2 et
$h'(k)$ est impair).


\pagebreak
Programmes pour la recherche et l'insertion avec un hachage lin\'eaire :

Recherche d'un \'el\'ement~:
\begin{verbatim}
static int Recherche (int x) {
  int i;
  i= h(x);
  while (a[i] != VIDE) {
    if (a[i] == x) return i;
    i= (i+1) % N;
  }
  return -1;
}
\end{verbatim}

Insertion d'un {\'e}l\'ement~:
\begin{verbatim}
static int Inserer(int x) {
  int i;
  i= h(x);
  while (a[i] != VIDE && x != a[i])
     i= (i+1) % N;
  a[i] = x;
  return i;
}
\end{verbatim}
\pagebreak

\begin{center}
{\huge \bf Analyse en moyenne du hachage ferm\'{e}}
\end{center}

{\em Hypoth\`ese}: Le rehachage est {\em uniforme}: Les
valeurs $h_1(x),h_2(x),\ldots$ sont successivement ind\'{e}pendantes
et ont chacune une distribution uniforme.
 
Taux de remplissage: $\alpha=\mbox{card}(E)/N$. 

\Lafig{evalhach}{114mm}{111mm}{500}{} 

Nombre moyen
d'essais pour ins\'{e}rer un \'{e}l\'{e}ment:
\[1+\alpha+\alpha^2+\ldots=\frac{1}{1-\alpha}\]

%Nombre moyen d'essais pour rechercher un \'{e}l\'{e}ment: co\^ut moyen
%des insertions d\'{e}ja faites:
%\[\frac{1}{\alpha}\int_0^\alpha \frac{dx}{1-x}=
%\frac{-1}{\alpha} \log (1-\alpha)\]


\pagebreak

\end{document}


\begin{center}
{\huge \bf Tri par s\'{e}lection}
\end{center}

\noindent {\em Principe}: A la $i$-\`eme {\'{e}}tape, on cherche le
minimum de $a[i],a[i+1],\ldots ,a[N-1]$ et on l'{\'{e}}change avec
$a[i]$.
\vspace{5mm}

\begin{verbatim}
public static void Triselection() {
  int i, j, min, t;

  for (i= 0; i< N-1; ++i) {
    min= i;
    for (j= i+1; j< N; ++j)
      if (a[j]< a[min])
        min= j;
      t= a[min]; a[min]= a[i]; a[i]= t;
  }
}
    
\end{verbatim}
\noindent {\em Complexit\'{e}}: $\Theta(N^2)$ mais seulement \linebreak
$O(N)$ \'{e}changes.
\pagebreak


\begin{center}
{\huge \bf Heapsort}
\end{center}
On va maintenant montrer une m\'{e}thode de tri plus
efficace : le {\em tri sur un arbre}. C'est une
m\'{e}thode de tri sur place de complexit\'{e} $O(n\log n)$.

On op\`ere en deux \'etapes :
\begin{enumerate}
\item On fabrique un tas (heap), i.e. un tableau tel que $a[ (i-1)/2]\geq a[i]$
pour $0\leq i< N$. Pour cela, on tamise successivement $a[N-1],\ldots,a[0]$.
\item On extrait successivement le maximum $a[0]$ en l'\'echangeant avec $a[M]$
pour $M=N-1,N-2,\ldots,0$ et
en tamisant le nouveau $a[0]$.
\end{enumerate}
Le tamisage de $a[k]$ consiste \`a \'echanger it\'era\-tivement $a[k]$ avec le maximum
de $a[2k]$ et $a[2k+1]$ jusqu'\`{a} ce que la condition des tas soit satisfaite.
\pagebreak

\titre{Le tamisage}

La m\'ethode \verb+Tamiser(k)+ ins\`ere $a[k]$ parmi $a[k]\ldots a[M]$ :
\begin{verbatim}
static void tamiser(int k, int M) {

 int j, v;

  v = a[k];
  while (2*k< M) {
    j = 2*k+1;
    if (j<M && a[j+1] > a[j]) 
      ++j;
    if (v >= a[j]) break;
    a[k] = a[j]; k = j;
  }
  a[k] = v;
}
\end{verbatim}
\pagebreak

\begin{verbatim}
static void heapsort() {
  int k, t;

  M= N-1;
  for (k = N/ 2-1; k>=0; --k)
    tamiser(k, M);
  do {
    t = a[0]; a[0]= a[M]; a[M]= t;
    M= M-1; tamiser(0, M);
  }
  while ( M>= 1);
}
\end{verbatim}

Exemple :
\begin{center}
\begin{tabular}{|c|c|c|c|c|}\hline
24&5&81&2&45\\ \hline
24&{\bf 45}&81&2&{\bf 5}\\ \hline
{\bf 81}&45&{\bf 24}&2&5\\ \hline\hline
{\bf 5}&45&24&2&{\bf 81}\\ \hline
{\bf 45}&{\bf 5}&24&2& 81\\ \hline
{\bf 2}&5&24&{\bf 45}&81\\ \hline
{\bf 24}&5&{\bf 2}& 45&81\\ \hline
{\bf 2}&5&{\bf 24}&45&81\\ \hline
{\bf 5}&{\bf 2}& 24&45&81\\ \hline
{\bf 2}&{\bf 5}&24&45&81\\ \hline
\end{tabular}
\end{center}
\pagebreak