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

\usepackage{hevea}
\usepackage{comment}
\excludecomment{solution}
\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

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

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

Travaux dirigés, 23 et 24 janvier 2003

\textbf{Graphes, flots et algèbre linéaire.}
\end{center}
\vspace*{1cm}

\section{Multiplication de matrices et plus court chemin}

  \begin{intro}
  On rappelle que l'algorithme de Strassen permet la multiplication
  de matrices carrées de dimension $n$ en ${\cal O}(n^{\log_2 7})$
  opérations élémentaires, si les éléments sont dans un anneau.
\begin{solution}
  \begin{eqnarray*}
  m_1 & = & (a_{12}-a_{22})(b_{21}+b_{22}) \\
  m_2 & = & (a_{11}+a_{22})(b_{11}+b_{22}) \\
  m_3 & = & (a_{11}-a_{21})(b_{11}+b_{12}) \\
  m_4 & = & (a_{11}+a_{12})b_{22} \\
  m_5 & = & a_{11}(b_{12}-b_{22}) \\
  m_6 & = & a_{22}(b_{21}-b_{11}) \\
  m_7 & = & (a_{21}+a_{22})b_{11} \\
  c_{11} & = & m_1 + m_2 - m_4 + m_6 \\
  c_{12} & = & m_4 + m_5 \\
  c_{21} & = & m_6 + m_7 \\
  c_{22} & = & m_2 - m_3 + m_5 - m_7
  \end{eqnarray*}
  NB: Coppersmith et Winograd : ${\cal O}(n^{2.495364})$ ce qui
  est mieux que ${\cal O}(n^{2.807355})$.
\end{solution}

  On rappelle aussi que la recherche des chemins les plus courts
  d'un graphe peut se faire avec l'exponentiation de la matrice
  d'adjacence dans le semi-anneau $(\min,+)$.
  \end{intro}
  \begin{enumerate}
    \item Peut-on appliquer l'algorithme de Strassen ?
    \item Si $a$ et $b$ sont entiers strictement positifs,
          montrez qu'on peut calculer
          $\min(a,b)$ à partir de $\log(x^a+x^b)/\log x$ pour un petit $x$.
\begin{solution}
          On remarque que $\lim_{x\to0}\frac{x^a+x^b}{x^{\min(a,b)}} = 1$
\end{solution}
    \item En déduire comment passer du semi-anneau
          $(\mathbb{N}_0\cup\{\infty\},\min,+)$
          à l'anneau $(\mathbb{R},+,\times)$.
    \item Proposer une multiplication de matrices dans le semi-anneau $(\min,+)$
          qui utilise l'algorithme de Strassen.
    \item Évaluer sa complexité en terme d'opérations arithmétiques,
          puis d'opérations sur les bits.
  \end{enumerate}
\begin{solution}
On pose $m = \ceil{1+\log n}$ et on remplace les $a_{ij}$ par
$2^{-ma_{ij}}$. On fait la multiplication de Strassen.
On revient en arrière avec $\ceil{-(1/m)\log c_{ij}}$.

Si les entiers de départ sont majorés par $M$ et que la multiplication
d'entiers de $M$ bits se fait en temps ${\cal O}(M)$, cet algorithme
est plus lent que ${\cal O}(n^3)$ dès que $M > {\cal O}(n^{3-\log 7})$
NB: $3-\log 7 \simeq 0.19$.
\end{solution}


\section{Couplages et mariages}
\begin{enumerate}
\item{Graphes bipartites}
  \begin{intro}
  Un graphe non-orienté est dit bipartite si $V$ se découpe en
  deux parties telles que toute arête relie un sommet dans
  chaque partie.
  On appelle {\em couplage} une partie $M\subset E$ telle que chaque
  sommet du graphe appartient à au plus une arête de $M$. Un couplage
  est dit maximal si son cardinal l'est. Un couplage est parfait si
  tous les sommets en font partie.
  Pour toute partie $X\subset V$, on note $V(X)$ l'ensemble des sommets
  adjacents à au moins un sommet de $X$.
  \end{intro}
  \begin{enumerate}
    \item Proposer un algorithme pour décider si un graphe est bipartite.
    \item Proposer un algorithme pour trouver un couplage maximal.
    \item Montrer le théorème de Hall : un graphe admet un couplage
          parfait si, et seulement si
          $\forall X\subset V, \quad |X| \leq |V(X)|$.
  \end{enumerate}
\item{Mariages stables}
  \begin{enumerate}
    \item On se place dans le cas d'un graphe bipartite complet,
          où à chaque arête est associée un poids.
          Trouver un algorithme qui calcule un couplage parfait
          maximisant la somme des poids des arêtes du couplage.
    \item Une variante du problème des mariages stables s'exprime
          en assignant à chaque sommet de $V_1$ un ordre de préférence
          parmi les sommets de $V_2$ et réciproquement.
          Proposer un algorithme qui trouve un couplage stable
          (i.e. aucun échange n'augmente la satisfaction).
  \end{enumerate}
\end{enumerate}

\section{Petit exercice de programmation}
\textbf{Énumération des permutations}

Écrire un programme qui affiche les permutations de $n$ éléments
dans l'ordre lexicographique, en un temps ${\cal O}(n.n!)$
et utilisant un tableau de taille $n$ plus quelques variables entières.
\begin{solution}
\begin{verbatim}
#include <stdio.h>
#define swap(v,i,j) max = v[i]; v[i] = v[j]; v[j] = max
int main(int argc,char**argv) {
  int n, i, max, piv, *v;
  scanf("%d",&n);
  v = (int*)malloc(n*sizeof(int));
  /* Init */
  for(i=0;i<n;i++) v[i]=i+1;
  for(;;) {
    /* Affichage */
    for(i=0;i<n;i++) printf("%d ",v[i]);printf("\n");
    /* Recherche de la première position qui change */
    piv = n-1;
    do { max = v[piv]; piv--; if (piv<0) return 0; }
    while (v[piv] >= max);
    /* Modification */
    for (i=0;i<(n-piv)/2;i++) { swap(v,n-1-i,piv+1+i); }
    for (i=piv+1;i<n;i++)
      if (v[i]>v[piv]) { swap(v,i,piv); break; }
  }
  return 1;
}
\end{verbatim}
\end{solution}

\end{document}
