\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}

\usepackage{hevea}
\ifhevea
\def\linewidth{}
\def\mathbb#1{\textbf{#1}}
\newenvironment{introduction}{\quotation\footnotesize}{\endquotation}
\newenvironment{intro}{\\\footnotesize}{}

\else

%% Parametres de mise en page
\topmargin -1.04cm
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  -1.04cm
\evensidemargin -1.04cm
\textwidth 18cm
\textheight 25.7cm
\advance\textheight by \topskip
\parindent 0pt

\tolerance1000

\def\ceil#1{\left\lceil #1\right\rceil}
\def\floor#1{\left\lfloor #1\right\rfloor}
\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\newenvironment{introduction}{\intro}{\endintro}
\newenvironment{intro}
  {\begin{center}\begin{minipage}{.9\linewidth}\footnotesize}
  {\end{minipage}\end{center}}

\fi

\begin{document}
\small
\twocolumn[
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 24 novembre 2000

Louis Granboulan
\end{center}\bigskip]

\section{Manipulation d'ensembles}
  \begin{introduction}
  Nous voulons réaliser efficacement des opérations
  de manipulation d'ensembles, telles celles énumérées ci-dessous :
  \begin{enumerate}\ifhevea\else\parsep=0pt\itemsep=0pt\fi
  \item {\bf ELEMENT} : donne un élément de l'ensemble.
        Cette opération permet de savoir si l'ensemble est vide.
  \item {\bf APPARTENANCE} : savoir si un élément est membre de l'ensemble.
  \item {\bf INSERTION} : ajout d'un élément sachant qu'il n'est pas membre.
  \item {\bf SUPPRESSION} : enlèvement d'un élément sachant qu'il est membre.
  \item {\bf INTERSECTION} : intersection de deux ensembles.
  \item {\bf UNION} : réunion de deux ensembles disjoints.
  \item {\bf LOCALISATION} : trouver, parmi une collection d'ensembles
        disjoints, lequel contient un élément donné.
  \par \textit{Les opérations ci-dessous supposent qu'il existe une relation
    d'ordre total sur les éléments.}
  \item {\bf MINIMUM} : extrait le plus petit élément de l'ensemble.
  \item {\bf PARTAGE} : un pivot sert à séparer l'ensemble en deux parties :
        les éléments plus petits et les éléments plus grands que le pivot.
  \item {\bf CONCAT} : réunion de deux ensembles tels que tous les éléments
        de l'un soient inférieurs à tous les éléments de l'autre.
  \end{enumerate}
  Nous appellerons univers l'ensemble de tous les éléments possibles.
  Nous devons distinguer le cas où l'univers est fini, de
  taille raisonnable ou s'il est (presque) infini.
  On s'intéresse à la complexité d'une opération, ou bien d'une séquence
  d'opérations, dans le cas le pire ou en moyenne, en fonction de la
  taille de l'ensemble ou bien de la taille de l'univers.
  \end{introduction}
\begin{enumerate}
\item{Exemples}
  \begin{enumerate}
    \item On appelle {\bf dictionnaire} une structure de données permettant
          les opérations APPARTENANCE, INSERTION et SUPPRESSION.
    \\    Existe-t-il une structure de données pour faire
          les opérations ELEMENT, APPARTENANCE, INSERTION et SUPPRESSION en
          temps constant ?
    \item Existe-t-il une structure de données pour faire une ou plusieurs
          des opérations INTERSECTION, UNION et LOCALISATION en temps constant ?
    \item Une {\bf file de priorité} doit permettre INSERTION, SUPPRESSION et
          MINIMUM.
    \\    Peut-on faire plusieurs parmi INSERTION, SUPPRESSION, MINIMUM
          et PARTAGE en temps constant ?
  \end{enumerate}
\item{Remarques générales}
  \begin{enumerate}
    \item Montrer quelques exemples d'opérations définies ci-dessus
          qu'on peut réaliser en utilisant une ou plusieurs autres.
          Quelle est la complexité de ceci ?
    \item Proposer une liste d'opérations qu'il suffit de savoir faire
          pour faire toute les autres.
  \end{enumerate}
\item{Structures de données élémentaires}
  \begin{intro}
  Les deux représentations les plus simples sont les suivantes :
  \begin{itemize}
  \item si l'univers est petit, tous les éléments sont numérotés
        et on représente un ensemble par sa fonction caractéristique,
        sous la forme d'un vecteur de bits ;
  \item dans tous les cas, on peut représenter un ensemble fini
        par une liste chaînée de ses éléments.
  \end{itemize}
  On va étudier ces deux structures :
  \end{intro}
  \begin{enumerate}
  \item \underline{Liste chaînée.}
     Quelles sont les limitations de cette représentation ?
     Quelles sont les opérations qu'on peut réaliser efficacement avec
     cette représentation ? Leur complexité ?
     Qu'y gagne-t-on à utiliser une liste doublement chaînée ?
  \item \underline{Vecteur de bits.}
     Quelles sont les limitations de cette représentation ?
     Quelles sont les opérations qu'on peut réaliser efficacement avec
     cette représentation ? Leur complexité ?
  \end{enumerate}
\end{enumerate}

\section{Hachage}
  \begin{introduction}
  Le hachage permet d'utiliser une représentation de type "vecteur
  de bits" avec un univers a priori infini.
  \\
  On se donne fonction $h$ de l'univers dans l'intervalle $\{1,...,u\}$.
  On représente un ensemble $E$ par à l'aide de son image par $h$.
  Cela permet de représenter dans une table indicée par $\{1,...,u\}$
  tous les ensembles pour lesquels $h$ n'a pas de collision.
  On peut généraliser ceci aux cas où $h$ a peu de collisions.
  On note $n$ le cardinal de l'ensemble et on appelle $r = n/u$
  le taux de remplissage.
  \end{introduction}
\begin{enumerate}
  \item{S'il n'y a pas de collisions}
  \begin{enumerate}
    \item Quelles sont les opérations qu'on peut réaliser efficacement ?
    \item Quelle est leur complexité en fonction de $n$ ou $u$.
  \end{enumerate}
  \item{Résolution des collisions}
  \begin{intro}
    Il s'agit de représenter l'ensemble $h^{-1}(i) \cap E$,
    lorsque celui-ci n'est pas un singleton.
    \\ Étudiez les cas suivants (complexité en temps, en mémoire) :
  \end{intro}
  \begin{enumerate}
    \item Résolution par chainage : chaque case de la table de hachage
          contient la liste chaînée des préimages.
    \item Hachage à adressage ouvert : chaque case de la table de hachage
          contient un unique élément. On suppose que $n \leq u$ et l'insertion
          d'un élément $c$ se fait comme suit :
          si la case $h(c)$ est remplie, on stocke $c$ dans la première case
          libre après $h(c)$ (i.e. on regarde $h(c)+1$, $h(c)+2$, ...
  \end{enumerate}
  \item{Améliorations du hachage à adressage ouvert}
  \begin{intro}
    Il s'agit d'éviter les phénomènes de regroupement : si $h(c)$ est
    distribuée uniformément et si plusieurs case consécutives sont
    remplies, la case libre qui les suit aura une grande probabilité
    d'être la prochaine case à remplir.
    \\ Les solutions classiques modifient la gestion des collisions :
  \end{intro}
  \begin{enumerate}
    \item Double hachage : on a une seconde fonction $h'$ à image dans
          $\{1,...,r\}$ et on regarde les cases $h(c)$, $h(c)+h'(c)$,
          $h(c)+2 h'(c)$, ...
    \item Hachage quadratique :
          on regarde les cases $h(c)$, $h(c)+1$, $h(c)+4$, $h(c)+9$, ...
  \end{enumerate}
\end{enumerate}

\ifhevea\else\newpage\fi
\section{Arbres}
  \begin{introduction}
  Les structures chainées les plus efficaces pour manipuler des ensembles
  ne sont pas des listes mais des arbres. De nombreuses variantes existent.
  \end{introduction}
\begin{enumerate}
\item{Tas}
  \begin{intro}
  Dans un univers ordonné,
  on représente un ensemble par un arbre binaire dont les n{\oe}uds internes
  et les feuilles contiennent les valeurs des éléments et tel que la valeur
  des fils soit supérieure à la valeur du père.
  On veut aussi que l'arbre soit quasi-complet (les feuilles sont de hauteur
  $h$ ou $h-1$ et celles de hauteur $h-1$ sont à droite).
  \end{intro}
  \begin{enumerate}
    \item Montrer qu'un tas permet de gérer les opérations d'une file de
          priorité en ${\cal O}(\log n)$ instructions.
    \item Que dire des autres opérations ?
  \end{enumerate}
\item{Arbre binaire de recherche}
  \begin{intro}
  Dans un univers ordonné,
  on représente un ensemble par un arbre binaire
  dont les n{\oe}uds sont étiquetés de telle sorte qu'un parcours infixe
  donne une suite croissante.
  On dit que l'arbre est équilibré
  (on parle d'arbre AVL, d'après Adel'son, Vel'skii et Landis)
  si pour tout n{\oe}ud la différence entre son sous-arbre gauche
  et son sous-arbre droit n'excède pas 1.
  \end{intro}
  \begin{enumerate}
    \item Quelle est la complexité des opérations
          APPARTENANCE, INSERTION, SUPPRESSION et MINIMUM
          avec une représentation des ensembles par des arbres de recherche
          non nécessairement équilibrés.
    \item Encadrer le nombre de n{\oe}uds d'un arbre AVL de hauteur $h$.
    \item Montrer que pour une représentation d'un ensemble de taille $n$
          par un arbre AVL, les quatre opérations ci-dessus peuvent être
          effectuées en ${\cal O}(\log n)$ instructions.
    \item Que dire des autres opérations ?
    \item Comment construire un arbre binaire de recherche pour un ensemble
          donné, tel que le coût moyen de l'opération APPARTENANCE soit minimal,
          connaissant une distribution de probabilité sur l'univers ?
  \end{enumerate}
\item{Arbre 2-3}
  \begin{intro}
  On représente un ensemble par un arbre dont les n{\oe}uds internes ont
  deux ou trois fils et dont toutes les feuilles sont à la même hauteur.
  Les feuilles contiennent les valeurs des éléments.
  \\
  Si l'univers est ordonné,
  on propose deux façons d'étiqueter les n{\oe}uds internes :
  1. Les feuilles sont en ordre quelconque et
  chaque n{\oe}ud est étiqueté par la valeur minimum de son sous-arbre.
  2. Les feuilles sont en ordre croissant et
  chaque n{\oe}ud est étiqueté par la valeur minimum de
  chacun de ses sous-arbres.
  \end{intro}
  \begin{enumerate}
    \item Encadrer le nombre de n{\oe}uds d'un arbre 2-3 de hauteur $h$.
    \item Quelles sont les opérations qu'on peut effectuer
          en ${\cal O}(\log n)$ instructions ?
  \end{enumerate}
\item{Forêt}
  \begin{intro}
  On s'intéresse à un univers de taille $u$ et aux
  opérations d'UNION et LOCALISATION.
  On représente chaque ensemble par un arbre
  dont les n{\oe}uds sont étiquetés par les éléments de l'ensemble.
  On aimerait réaliser ces opérations en temps presque constant.
  \end{intro}
  \begin{enumerate}
    \item L'opération d'UNION se réalise naturellement en temps constant,
          en ajoutant l'un des deux arbres comme fils supplémentaire
          de la racine de l'autre.
          Montrer qu'en l'absence de rééquilibrage de l'arbre,
          une opération de LOCALISATION peut prendre un temps ${\cal O}(u)$.
    \item Montrer que si pour une UNION, on choisit de rajouter le plus petit
          des deux ensembles comme fils supplémentaire de la racine du plus
          grand (en nombre de n{\oe}uds),
          une opération de LOCALISATION prend
          un temps ${\cal O}(\log u)$.
  \end{enumerate}
\item{Compression d'une forêt}
  \begin{intro}
  On suppose qu'à chaque LOCALISATION, on modifie l'ensemble trouvé
  de telle sorte que tous les ancêtres de l'élément cherché deviennent
  des fils directs de la racine.
  On définit $F(0)=1$ et $F(i+1)=2^{F(i)}$,
  puis $G(u)=\min\{k\mbox{ tq }F(k)\geq u\}$.
  \\
  Pour $\alpha\in\mathbb{R}$,
  on s'intéresse à l'exécution d'une séquence de $\alpha u$
  opérations d'UNION et LOCALISATION à partir d'une partition de
  l'univers en singletons.
  \\
  On définit le {\em rang} d'un élément $v$ comme
  sa hauteur dans la forêt résultant de la séquence des
  opérations d'UNION seules.
  On partitionne les éléments en groupes, selon l'image par $G$
  de leur rang.
  \end{intro}
  \begin{enumerate}
    \item Montrer que la fonction $G$ est quasi constante.
    \item Montrer qu'il y a au plus $u/F(g)$ éléments de groupe $g$.
    \item On sait que pour chaque opération de LOCALISATION,
          le coût est le nombre d'ancêtres de l'élément cherché.
          On va répartir le coût comme suit :
          si $v$ est la racine, ou bien si $v$ et son père sont dans
          des groupes distincts,
          le coût attribué directement aux opérations de LOCALISATION
          est incrémenté de 1.
          Sinon, c'est le coût attribué à l'élément $v$ qui
          est incrémenté de 1.
          \\
          Montrer que le coût attribué directement à chaque opération de
          LOCALISATION est au maximum $G(u)$ et que le coût attribué à
          l'ensemble des éléments d'un même groupe est au plus $u$.
    \item En déduire que l'ensemble des opérations de LOCALISATION
          se fait en temps ${\cal O}((1+\alpha)u G(u))$.
  \end{enumerate}
\end{enumerate}

\section{Application}
  \begin{introduction}
  Soit un graphe non orienté connexe $(V,E)$ dont les arêtes ont un poids réel.
  On cherche une arborescence recouvrante de poids minimal.
  Voici un algorithme qui va construire l'ensemble $T$ des arêtes de
  l'arborescence recouvrante.
  Le principe de l'algorithme est de partir d'une forêt recouvrante
  de poids minimal et de la rendre connexe.
  \\
  On manipule l'ensemble $VS$ dont les éléments sont l'ensemble des
  sommets pour chaque arborescence de la forêt. C'est donc une partition de $V$.
  On initialise $T$ à l'ensemble vide et $VS$ à la partition en singletons.
  \\
  À chaque étape, on choisit l'arête de poids minimal. On la suprime de $E$.
  si ses deux extrémités sont dans des éléments de $VS$ distincts, on rajoute
  cette arête à $T$ et on réunit les deux éléments de $VS$ correspondants.
  On s'arrête quand $VS$ est un singleton.
  \end{introduction}
\begin{enumerate}
\item Montrer que cet algorithme est correct
\item Évaluer sa complexité.
\end{enumerate}

\section{Partage d'informations}
  \begin{introduction}
  Si on suppose qu'on sait faire certaines opérations sur les éléments,
  la représentation d'un ensemble peut être encore plus efficace.
  \end{introduction}
\begin{enumerate}
\item Évaluer ainsi la représentation d'un «dictionnaire» comme
      on l'a vu dans le TP4 : on optimise la représentation d'un
      ensemble de chaînes de caractères en partageant des sous-chaînes
      communes.
\item Trouver l'équivalent pour les ensembles d'arbres
      \ifhevea
      (cf. \url{http://www.di.ens.fr/\%7Emauborgn/publi/these.html}{thèse de
      Laurent Mauborgne}).
      \else
      \\ (cf. thèse de Laurent Mauborgne \\
      {\tt http://www.di.ens.fr/\string~mauborgn/publi/these.html}).
      \fi
\end{enumerate}

\end{document}
