\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amssymb,epsfig,hyperref}
\usepackage[utf8]{inputenc}
\usepackage[boxed,french]{algorithm2e}
\usepackage[usenames]{xcolor}

\newcommand{\tower}[2]{$#1~\|~#2$}

\newenvironment{proof}
      {\noindent\textbf{Proof\ }}
      {\hspace*{\fill}$\Box$\medskip}

\newtheorem{lemma}{Lemma}
\newtheorem{theoreme}{Théorème}


\begin{document}

\begin{center}
  4I505 CPA -- Corrigé de l'examen de rattrapage Juin 2016
\end{center}



\section{Paire de points les plus proches}

C'est un algorithme classique, la page \href{https://fr.wikipedia.org/wiki/Recherche_des_deux_points_les_plus_rapproch%C3%A9s}{wikipédia} est un bon corrigé.

\section{La pêche}

Ce qu'il faut produire est une liste de points, débutant et terminant par le point bleu, et tel que l'angle entre trois points successifs est à droite.  L'algorithme de balayage de Graham produit justement cette liste. Mais au lieu de débuter sur un point de l'enveloppe convexe on débutera sur le point bleu.  Les points rouges sont ordonnées selon l'angle autour du point bleu.  Mais cet ordre est circulaire, sans début naturel.  Il y a alors $n$ choix possibles pour débuter le balayage de Graham et il faut les essayer tous, comme le montre l'exemple en Figure~\ref{fig:disque}.

\begin{figure}[hb]
    \centerline{\includegraphics[width=5cm]{disque.pdf}}
    \caption{Instance composée de points répartis uniformément sur un cercle centré au point bleu, exclu d'un point sur le cercle. Le balayage de Graham doit débuter sur le voisin droite du point exclu.}
    \label{fig:disque}
\end{figure}


\section{Famille de fonctions de hashage 2-universelle}

Il suffit de vérifier sur l'exemple donnée avec $p=5$ qu'il n'existe pas de $a$ tel que $h_a(1)=1$ et $h_a(2)=1$.  En utilisant la définition, on peut s'apercevoir que la famille n'est pas 2-universelle.

\section{Entrées-sorties d'un musée}

Maintenez un compteur, initalement à $S$. Pour chaque $(\textrm{IN},x)$ ajoutez $x$ à $S$ et pour chaque  $(\textrm{OUT},x)$ enlevez $x$ de $S$. La réponse sera l'élément recherché char tous les autres paires d'entrées sorties se sont annulées dans $S$.  La complexité en mémoire est $O(\log N)$, le nombre de bits pour stocker $S$.

Si on ajoute les éléments à $S$ par le ou-exclusif, on a le même comportement, sans avoir à distinguer les entrées des sorties.

\section{Échantillonnage proportionnel}

Soit $e$ l'élément échantilloné produit par l'algorithme.
On maintient une durée totale $T$, initalement à $0$. Sur chaque entrée $(a,t,d)$ on ajoute $d$ à $T$. Et on pose $e:=a$ avec probabilité $d/T$.

\end{document}