\documentclass[11pt]{article}

\addtolength{\textheight}{1cm}
\usepackage{epic}
\usepackage{eepic}

\usepackage[francais]{babel}

\usepackage{moreverb}
\usepackage[latin1]{inputenc}

\usepackage{latexsym}
\usepackage{amssymb}

\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}

\def\ra{\rightarrow}

\def\cF{\cal F}

\begin{document}

\begin{center}
  \Large Université Paris 7\\
Ma\^{\i}trise d'Informatique -- Algorithmique\\
27 novembre 2002\\
Dur\'ee : 2 heures.
Documents autoris\'es : notes de cours/TD. Le bar\`eme est
indicatif. 
\end{center}

{\bf Question 1} (4 points)~:\\

Soit $G=(V,E)$ un graphe orient\'e. Pour deux sommets $i, j
\in V$ on note  $d_{\max}(i,j)$ la longueur maximale d'un
chemin de $i$ \`a $j$ ($d_{\max}(i,j)=\infty$, s'il existe un
chemin non-simple de $i$ \`a $j$ et $d_{\max}(i,j)=-\infty$,
s'il existe aucun chemin de $i$ \`a $j$).

Proposez un algorithme de temps au plus cubique pour calculer $d_{\max}(i,j)$ pour
toute paire de sommets $i,j \in V$. Justifier la validit\'e
de votre algorithme.

\bigskip

{\bf Question 2} (8 points)~:\\
Soit $G=(V,E,p)$ un graphe orient\'e  pond\'er\'e par la
fonction $p : E \ra \{1,\ldots,1000\}$. On fixe un
sommet source $s \in V$ et on veut
calculer pour tout sommet $v \in V$ le poids minimal d'un
chemin  de $s$ \`a $v$.

Le but de l'exercice est de proposer une impl\'ementation de
l'algorithme de Dijkstra avec un temps d'ex\'ecution
lin\'eaire (dans $O(|V|+|E|)$). L'algorithme de Dijkstra est
rappel\'e \`a la fin de l'exercice.

\begin{enumerate}
\item Vous devez g\'erer les
sommets $v$ \`a  tra\^{\i}ter dans un tableau
$T$. L'entr\'ee  $T[k]$ du tableau contient les sommets de
distance actuelle $D(v)=k$. 

Pr\'ecisez quels sont le type et la taille du tableau.
\item D\'ecrivez comment effectuer 
  Relax$(u,v,p)$ sur la structure de donn\'ees propos\'ee.
\item Pour choisir un sommet $v$ tel que
  $D(v)$ est minimal on garde comme information
  suppl\'ementaire le $k$ minimal tel que $\{v \mid D(v)
  =k\}$ est non-vide.

D\'ecrivez comment effectuer Delete-Min($T$) sur la
structure de donn\'ees propos\'ee. 
\item Justifier que Relax$(u,v,p)$ ne change pas la valeur
  $k$ de la question pr\'ec\'edente.
\item Justifier le temps d'ex\'ecution lin\'eaire.
\end{enumerate}

\newpage

\begin{tabbing}
  Dijkstra($G=(V,E),s \in V, p:E \ra \N$)\\
debut\=\\
\> $S \longleftarrow \emptyset$\\
\> $T \longleftarrow V$ // a detailler\\
\> Tant \= que ($T \not=\emptyset$) faire\\
\>\> $u \longleftarrow$ Delete-Min$(T)$\\
\>\> $S \longleftarrow S \cup \{u\}$\\
\>\> Pour \= tout $(u,v) \in E$ faire\\
\>\> \> // Relax($u,v,p$) :\\
\>\> \> $D(v) \longleftarrow \min (D(v), D(u)+p(u,v))$\\
\>\> FinPour\\
\> FinTantque\\
fin
\end{tabbing}


\bigskip

\noindent

{\bf Question 3} (8 points)~: \\
Soit $G=(V,E,p)$ un graphe non-orient\'e connexe pond\'er\'e, o\`u
$p : E \ra \Z$ est la fonction associant \`a chaque ar\^ete
$e \in E$ un poids entier $p(e) \in \Z$. {\em On suppose ici
  que les
poids sont tous diff\'erents :} $p(e) \not= p(e')$, pour
tous $e \not= e'$.

Le but de cet exercice est de montrer que l'algorithme
ci-dessous calcule un arbre recouvrant minimal (ARM) de
$G$. L'algorithme op\`ere sur une liste $\cF$ d'arbres $T_1,
\ldots,T_k$, qui sont deux \`a deux disjoints et qui
recouvrent $G$. Formellement, on a  $T_i=(V_i,E_i)$, o\`u $V$
est l'union disjointe des $V_i$ et chaque $E_i$ est un
sous-ensemble de $E$.

La liste $\cF$ est initialis\'ee avec les arbres-singletons
$(\{v\},\emptyset)$, $v \in V$. L'algorithme retourne un
ensemble d'ar\^etes $F \subseteq E$. 



\begin{tabbing}
  fonction  ARM ($G=(V,E,p)$) : retourne un ensemble d'ar\^etes;\\
debut \= \\
\> Trier les aretes selon le poids (ordre croissant);\\
\> $\cF = \emptyset$;\\
\> $F = \emptyset$;\\
\> Pour \= tout $v \in V$ faire \\
\>\> rajouter $(\{v\},\emptyset)$ a $\cF$;\\
\> Tant \= que $|{\cF}| >1$ faire\\
\>\> $X \longleftarrow \emptyset$;\\
\>\> Pour \= tout $T \in \cF$ faire\\
\>\>\> $uv \longleftarrow$ ar\^ete de poids minimal telle que
$u \in T$ et $v \notin T$; (*)\\
\>\>\> $X \longleftarrow X \cup \{uv\}$;\\
\>\>FinPour\\
\>\> Reorganiser $(\cF$, $F, X$);\\
\>\> $F \longleftarrow F \cup X$;\\
\> FinTantque\\
\> retourner$(F)$\\
fin
\end{tabbing}

On suppose que le graphe $G$ est donn\'e par des listes
d'adjacence. 

Apr\`es l'appel de la proc\'edure Reorganiser $(\cF$, $F,X$),
la liste $\cF$ contient les composantes connexes de $(V,F
\cup X)$ (avant l'appel, $\cF$ contient les composantes
connexes de $(V,F)$). On montrera que ces composantes
connexes sont toujours des arbres.

\begin{enumerate}
\item Montrer l'ex\'ecution de cet algorithme sur l'exemple
  suivant :
  \begin{center}
    

\setlength{\unitlength}{0.00063333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(3423,2305)(0,-10)
\put(212,2050){\ellipse{336}{336}}
\put(1712,2050){\ellipse{336}{336}}
\put(3212,2050){\ellipse{336}{336}}
\put(212,175){\ellipse{336}{336}}
\put(1712,175){\ellipse{336}{336}}
\put(3212,175){\ellipse{336}{336}}
\path(212,1900)(212,325)
\path(1712,1900)(1712,325)
\path(3212,1900)(3212,325)
\path(362,2050)(1562,2050)
\path(1862,2050)(3062,2050)
\path(362,175)(1562,175)
\path(1862,175)(3062,175)
\path(287,1900)(1562,250)
\path(1800,1910)(3075,260)
\put(212,1975){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}a}}}}}
\put(1712,1975){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}b}}}}}
\put(3212,1975){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}c}}}}}
\put(212,100){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}d}}}}}
\put(1712,100){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}e}}}}}
\put(3212,100){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}f}}}}}
\put(62,1000){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}1}}}}}
\put(3362,1000){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}2}}}}}
\put(1862,1000){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}3}}}}}
\put(962,2125){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}4}}}}}
\put(2537,2125){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}9}}}}}
\put(1112,1000){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}6}}}}}
\put(2687,1000){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}7}}}}}
\put(962,250){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}8}}}}}
\put(2537,250){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}5}}}}}
\end{picture}
}
  \end{center}

\item Montrer qu'apr\`es chaque it\'eration de la boucle
  Pour-tout, le graphe $(V,F)$ est acyclique. (Rappel : les
  poids des ar\^etes sont tous diff\'erents.)
\item Montrer l'invariant suivant : \`a chaque instant,
  l'ensemble des ar\^etes $F$ peut \^etre \'etendu par un ARM
  de $G$ : il existe un ARM $(V,F')$ tel que $F \subseteq
  F'$. 
\item Montrer qu'apr\`es $k$ it\'erations de la boucle
  Tantque, la liste $\cF$ contient au plus $\frac{|V|}{2^k}$
  arbres. 
\item D\'ecrire une structure de donn\'ees de type
  union-find pour g\'erer la liste
  $\cF$ et les arbres $T_i$. Cette structure de donn\'ees
  sera bas\'ee sur l'impl\'ementation de Union-Find par des
  listes cha\^{\i}n\'ees.
\item D\'ecrire la ligne (*) de l'algorithme ainsi que la
  proc\'edure Reorganiser $(\cF$, $F,X$) avec des
  op\'erations union-find.
\item Montrer qu'en utilisant  l'union par longueur on
  obtient un
  temps d'ex\'ecution de $O((|V|+|E|)\log(|V|))$. Justifier
  votre r\'eponse, en indiquant :
  \begin{itemize}
\item le nombre maximal de fois que chaque ar\^ete est
  consid\'er\'ee dans l'instruction (*),
  \item le temps total pour ex\'ecuter les  instructions
    (*),
\item le temps total pour ex\'ecuter les appels de
  Reorganiser $(\cF$, $F,X$).
  \end{itemize}
\end{enumerate}

% \newpage

% \noindent



% {\bf Question 3} (8 points)~: \\

% Soit $G=(V,E)$ un graphe non-orient\'e connexe. Une ar\^ete $e \in
% E$ est appell\'ee un {\em pont}, si le graphe obtenu de $G$
% en supprimant $e$ n'est plus connexe.

% Exemple : la seule ar\^ete pont dans le graphe ci-dessous
% est l'ar\^ete $bc$.

% \begin{center}
%   \setlength{\unitlength}{0.00063333in}
% %
% \begingroup\makeatletter\ifx\SetFigFont\undefined%
% \gdef\SetFigFont#1#2#3#4#5{%
%   \reset@font\fontsize{#1}{#2pt}%
%   \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
%   \selectfont}%
% \fi\endgroup%
% {\renewcommand{\dashlinestretch}{30}
% \begin{picture}(4315,1905)(0,-10)
% \path(804,1650)(54,300)(1404,300)(1554,300)
% \path(3504,1650)(2754,300)(4104,300)(4254,300)
% \path(804,1650)(1554,300)
% \path(3504,1650)(4254,300)
% \path(1554,300)(2754,300)
% \put(54,0){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}a}}}}}
% \put(1554,0){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}b}}}}}
% \put(2754,0){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}c}}}}}
% \put(4254,0){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}d}}}}}
% \put(804,1725){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}e}}}}}
% \put(3504,1725){\makebox(0,0)[b]{\smash{{{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}f}}}}}
% \end{picture}
% }
% \end{center}

% \begin{enumerate}
% \item Montrer l'ex\'ecution  de l'algorithme de recherche en
%   profondeur (DFS) sur l'exemple pr\'ec\'edent, en indiquant les
%   ar\^etes de l'arbre-DFS ainsi que les ar\^etes-retour.
% \item Justifier que pour un graphe non-orient\'e la
%   recherche en profondeur ne produit que 2 types d'ar\^etes
%   : les ar\^etes de l'arbre-DFS ($\{v,\mbox{Pred}(v)\}\}$) et
%     les ar\^etes-retour. 
% \item D\'ecrire comment  modifier l'algorithme DFS pour
%   calculer les ponts en temps lin\'eaire
%   $O(|V|+|E|)$. Justifier le temps de calcul (Attention : chaque
%   ar\^ete ne devra \^etre consid\'er\'ee qu'un nombre de
%   fois qui ne d\'epend pas de $|V|, |E|$).
% \end{enumerate}

%   \begin{tabbing}
%     DFS ($v$) // $v \in V$\\
% debut \=\\
% \> col$(v)$ $\longleftarrow$ gri;\\
% \> Pour \= tout  $vw \in E$ faire \\
% \>\> Si col($w$) = blanc alors \= Pred$(w) \longleftarrow v$;
% \\
% \>\>\> DFS($w$) Finsi \\
% \> FinPour\\
% \> col$(v)$ $\longleftarrow$ noir\\
% fin
%   \end{tabbing}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
