\documentclass[12pt]{article} \usepackage{fullpage,amsmath,amssymb,epsfig} \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 -- Examen de rattrapage Juin 2016 \end{center} Les documents distribués dans le cadre du cours et les notes personnelles sont autorisés. \section{Famille de fonctions de hashage 2-universelle} Soit ${\cal H}_p$ une famille de fonctions de hashage de $\{1,\ldots,p-1\}$ vers $\{1,\ldots,p-1\}$, où $p\geq 3$ est un nombre premier. ${\cal H}_p$ est constituée de toutes les $p-1$ fonctions $h_a$ de la forme \[ h_a(x)=x\cdot a \pmod p, \] où $a$ est un entier de ${1,\ldots,p-1}$ et $\cdot$ est la multiplication habituelle des entiers, ici modulo $p$. Par exemple pour $p=5$, ${\cal H}_k$ est composée des $4$ fonctions dont les images sont les suivantes (l'entrée en ligne $a$ et colonne $x$ est $h_a(x)$) \[ \begin{array}{c|cccc} a\backslash x & 1 & 2 & 3 & 4 \\ \hline 1 & 1 & 2 & 3 & 4 \\ 2 & 2 & 4 & 1 & 3 \\ 3 & 3 & 1 & 4 & 2 \\ 4 & 4 & 3 & 2 & 1 \\ \end{array} \] Est-ce que cette famille est 2-universelle~? \section{Entrées-sorties d'un musée} Un portique d'un musée relève toutes les entrées et sorties des visiteurs. Il génère un flux de couples $(d,x)$ avec $d\in\{\textrm{IN}, \textrm{OUT}\}$ et $x$ un identifiant dans $\{1,\ldots,N\}$. Chaque visiteur a un identifiant unique $x$ et quand il entre dans le musée le couple $(\textrm{IN},x)$ est généré, quand il quitte le musée le couple $(\textrm{OUT},x)$ est généré. Vous recevez un flux de taille $2n-1$, correspondant à l'entrée et la sortie de $n$ visiteurs distincts, mais il y a un visiteur d'identifiant $x_0$ qui est seulement entré dans le musée sans en être sorti. Le flux donné est tel que pour chaque $x\neq x_0$, si $(\textrm{IN},x)$ apparaît dans le flux, le couple correspondant $(\textrm{OUT},x)$ apparaît aussi dans le flux à une position ultérieure. \begin{enumerate} \item Proposez un algorithme qui lit ce flux et retourne $x_0$. Cet algorithme devrait lire le flux en une seule passe, et utiliser une mémoire de taille $O(\log N)$. \item Le portique vient de se casser et désormais ne peut plus distinguer les entrées des sorties. Il génère alors un flux d'entiers correspondant aux identifiants des visiteurs sans distinguer s'il s'agit d'une entrée ou d'une sortie. Vous recevez un flux de taille $2n-1$ avec la propriété que chaque entier $x$ y apparaît soit 0 soit 2 fois, sauf un entier $x_0$ qui y apparaît 1 fois. Proposez un algorithme qui lit ce flux et qui détermine $x_0$. Sa complexité en mémoire doit être $O(\log N)$. \end{enumerate} \section{Échantillonnage proportionnel} On vous donne un flot de $n>0$ triplets de la forme $(a,t,d)$ où $a$ est une adresse IP sur 32 bits (par exemple 129.4.15.1) et $t,d>0$ des entiers avec $t+d