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

%% 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

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

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

Travaux dirigés, 14 et 15 décembre 1998

Louis Granboulan
\end{center}

\section{Ensembles}
  \begin{intro}
  Nous voulons réaliser efficacement les opérations
  de manipulation d'ensembles, à l'aide de tableaux
  où de structures chaînées.
  \par
  Nous devons d'abord distinguer le cas où les éléments
  des ensembles manipulés sont choisis parmi un même ensemble de
  taille raisonnable ou s'ils sont choisis dans un ensemble
  presque infini.
  Nous appellerons univers cet ensemble de tous les éléments considérés.
  Nous devons aussi distinguer le cas où il existe une relation
  d'ordre sur les éléments de l'univers, ce qui est nécessaire
  pour certaines opérations.
  \begin{enumerate}\parsep=0pt\itemsep=0pt
  \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 formant
        une partition de l'univers, lequel contient un élément donné.
  \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}
  On appelle {\bf dictionnaire} une structure de données permettant
  les opérations APPARTENANCE, INSERTION et SUPPRESSION.
  Une {\bf file de priorité} doit permettre INSERTION, SUPPRESSION et
  MINIMUM.
  \par
  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.
  \end{intro}
\begin{enumerate}
\item{Remarques générales}
  \begin{enumerate}
    \item Que pouvez-vous faire comme remarques sur les définitions de
          ces opérations ?
    \item Quelles sont celles qu'on peut réaliser avec une ou plusieurs autres ?
          Quelle est la complexité de ceci ?
  \end{enumerate}
\item{Exemples}
  \begin{enumerate}
    \item Existe-t-il une structure de données pour faire
          les opérations ELEMENT, APPARTENANCE, INSERTION et SUPPRESSION en
          temps constant ?
    \item Peut-on faire INSERTION et MINIMUM 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 ?
  \end{enumerate}
\end{enumerate}
\section{Structures de données élémentaires}
\begin{enumerate}
\item{Liste chaînée}
  \begin{intro}
  Chaque ensemble est représenté par une liste chaînée de ses éléments.
  \end{intro}
  \begin{enumerate}
    \item Quelles sont les limitations de cette représentation ?
    \item Quelles sont les opérations qu'on peut réaliser efficacement avec
          cette représentation ? Leur complexité ?
    \item Qu'y gagne-t-on à utiliser une liste doublement chaînée ?
  \end{enumerate}
\item{Vecteur de bits}
  \begin{intro}
  Les éléments de l'univers sont numérotés et on représente un ensemble
  par sa fonction caractéristique, sous la forme d'un vecteur de bits.
  \end{intro}
  \begin{enumerate}
    \item Quelles sont les limitations de cette représentation ?
    \item Quelles sont les opérations qu'on peut réaliser efficacement avec
          cette représentation ? Leur complexité ?
  \end{enumerate}
\end{enumerate}
\section{Hachage}
\begin{enumerate}
\item[]
  \begin{intro}
  On se donne fonction $h$ de l'univers dans l'intervalle $\{1,...,n\}$.
  Cela permet de représenter dans une table indicée par $\{1,...,n\}$
  tous les ensembles pour lesquels $h$ n'a pas de collision.
  \end{intro}
  \begin{enumerate}
    \item Quelles sont les opérations qu'on peut réaliser efficacement ainsi,
          et quelle est leur complexité ?
    \item Comment gérer les collisions ? Quelle est la complexité dans ce cas ?
  \end{enumerate}
\end{enumerate}

\newpage
\section{Arbres}
\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.
  \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{Manipulation d'une partition de l'univers}
  \begin{intro}
  On s'intéresse à un univers de taille $n$ 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.
  \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}(n)$.
    \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 n)$.
    \item 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(n)=\min\{k\mbox{ tq }F(k)\geq n\}$.
          \par
          On s'intéresse à l'exécution d'une séquence de $\alpha n$
          opérations d'UNION et LOCALISATION à partir d'une partition de
          l'univers en singletons.
          \par
          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.
          \begin{enumerate}
          \item Montrer qu'il y a au plus $n/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.
                \par
                Montrer que le coût attribué directement à chaque opération de
                LOCALISATION est au maximum $G(n)$ et que le coût attribué à
                l'ensemble des éléments d'un même groupe est au plus $n$.
          \item En déduire que l'ensemble des opérations de LOCALISATION
                se fait en temps ${\cal O}((1+\alpha)nG(n))$.
          \end{enumerate}
  \end{enumerate}
\end{enumerate}
\section{Application}
\begin{intro}
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{intro}
\begin{enumerate}
\item Montrer que cet algorithme est correct
\item Évaluer sa complexité.
\end{enumerate}

\newpage
La taille de l'univers est $u$, la taille de l'ensemble est $n$.
\def\On{${\cal O}(n)$}
\def\Ol{${\cal O}(\log n)$}
\def\OG{${\cal O}(G(u))$}
\def\On{$n$}
\def\Ol{$\log n$}
\def\OG{$G(u)$}

\begin{tabular}{|l|c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c@{ }c|}
\cline{2-11} \multicolumn{1}{c|}{}
    & \tiny ELEMENT & \tiny APPARTENANCE & \tiny INSERTION & \tiny SUPPRESSION
    & \tiny INTERS. & \tiny UNION & \tiny LOCALIS. & \tiny MINIMUM
    & \tiny PARTAGE & \tiny CONCAT \cr \hline
Liste chaînée
    & 1   & $n$ & 1   & $n$ & \On & \On &     & -   & -   & - \cr
Liste triée
    & 1   & $n$ & $n$ & $n$ & \On & \On &     & 1   & $n$ & 1 \cr
Tas
    & 1   & $n$ & \Ol & \Ol &     &     &     & 1   &     &     \cr
Arbre AVL
    & 1   & \Ol & \Ol & \Ol &     &     &     & \Ol &     &     \cr
Arbre 2-3 \footnotemark \global\edef\xxx{\thefootnote}
    & 1   & $n$ & \Ol & \Ol &     & \Ol & \Ol & 1   &     &     \cr
Arbre 2-3 trié \footnotemark
    & 1   & \Ol & \Ol & \Ol &     &     & \Ol & \Ol & \Ol & \Ol \cr
\hline
Vecteur de bits
    & $u$ & 1   & 1   & 1   & $u$ & $u$ &     & $u$ & $u$ & $u$ \cr
Forêt comprimée
    & 1   & \OG & \OG & \OG &     & \OG & \OG &     &     &     \cr
\hline
\end{tabular}
\footnotetext[\xxx]{Les feuilles sont en ordre quelconque et
chaque n{\oe}ud est étiqueté par la valeur minimum de son sous-arbre.}
\footnotetext{Les feuilles sont en ordre croissant et
chaque n{\oe}ud est étiqueté par la valeur minimum de
chacun de ses sous-arbres.}

\end{document}
