Énoncé donné
On considère un alphabet $\Sigma$, une partie $A \subseteq \Sigma^{n} \times \Sigma^{n}$ et $(x, y) \in \Sigma^{n} \times \Sigma^{n}$. Deux normaliens, Alice et Bob, doivent déterminer si la paire $(x, y) $ appartient ou non à $A$, en sachant qu'Alice ne connaît que $x$, et que Bob ne connaît que $y$ (ils ne connaissent pas le mot de l'autre). Pour ce faire, ils ont au préalable pris connaissance de l'ensemble $A$, et se sont mis d'accord sur un protocole $P$, leur permettant de communiquer par l'intermédiaire de bits suivant le schéma suivant :
Leur communication est une suite de tours. À chaque tour, on a l'alternative :
- Soit Alice émet $\gamma \in \{0,1\}$ et Bob reçoit.
- Soit Bob émet $\gamma \in \{0, 1\}$ et Alice recoit.
La communication prend fin quand Alice et Bob peuvent affirmer si la paire est ou non dans $A$.
(Notez en particulier qu'ils doivent se mettre d'accord à l'avance pour savoir qui émet lors du premier tour.)
On appelle alors historique de (x, y) la suite H(x, y) à valeurs dans $\{Alice, Bob\} $ dont l'élément d'indice $k$ indique qui a émis au tour $k$, et transcription la liste $T(x, y)$ à valeurs dans $\{0,1 \} $ dont le terme d'indice $k$ représente le bit transmit au tour $k$. On note enfin la complexité d'une partie A :
$D(A) = \min_P \max_{(x, y) \in A} |T(x, y)|$.
1. Montrer que $\forall A \subseteq \Sigma^{n} \times \Sigma^{n}, D(A) \leq n+1$
On note $|x|_a$ le nombre d'occurrences de la lettre $a$ dans le mot $x$.
2. Soit $A = \{ (x,y) / |xy|_a >= n\}$. Donner une borne inférieure pour $D(A)$.
3. Montrer que si $T(x_1 , y_1 ) =T(x_2, y_2)$ alors on a aussi $H(x_1 , y_1 ) = H(x_2, y_2)$.
4. Montrer que si $T(x_1, y_1)$ est un préfixe de $T(x_2, y_2)$, alors $T(x_1,y_1) = T(x_2, y_2) $
5. Soit $A = \{(x,y) / x=y\}$. Montrer que dans ce cas, $D(A) = n+1$.
6. On appelle une suite trompeuse une partie $\{(x_1, y_1)... (x_k, y_k) \} \subseteq A$ telle que
$\forall (i < j) \in \{1...k\}^{2}, (x_i, y_j) \notin A$.
Montrer que si $A$ contient une suite trompeuse, alors $D(A) = \Omega (\log_2(k))$ (ie au moins de l'ordre de $\log_2(k)$ ).
Indication(s) fournie(s) par l'examinateur pendant l'épreuve
NA
Commentaires divers
L'énoncé contenait en tout 12 questions.
Aucun commentaire posté pour le moment