\begin{frame}{Propagation Paralèlle \emph{à la} Margolus}
  {Le problème de la dépendance aux cellules voisines}
  \vfill

  \centering
  \begin{tikzpicture}
    \clip (-17mm,-17mm) rectangle (17mm,17mm);
    \draw[xshift=5mm,yshift=5mm] ( -3cm, -3cm) grid ( 3cm, 3cm);
    \node (x) at (0,0) {$x_i$};
    \foreach[count=\n] \p in {(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)} {
      \node (v\n) at \p {$v_{\n_i}$};
    }
    \begin{scope}[on background layer]
    \clip (-17mm,-17mm) rectangle (17mm,17mm);
    \only<1>{%
      \fill[black!10] (v6.south west) rectangle (v2.north east);
      \fill[white] (v6.north east) rectangle (v2.south west);
      \fill[red!60] (x) circle (3mm);
    }
    \only<2>{%
      \fill[black!10] (v3.north east) rectangle ($(v7.south east)+(-10cm,0)$);
      \fill[white] (v3.south west) rectangle ($(v7.north east)+(-10cm,0)$);
      \fill[red!60] (v5) circle (3mm);
    }
    \end{scope}
  \end{tikzpicture}

  \alt<1>{%
    $$ x_{i,1} = f(x_i , v_{1_i} , v_{2_i} , \ldots , v_{8_i}) $$
  }{%
    $$ v_{5_{i,1}} = f(v_{5_i} , x_i , v_{3_i}, v_{4_i} ,
      \alert{? , ? , ?} , v_{6_i} , v_{7_i}) $$
  }
  \vfill~
  \uncover<2>{Une partie du \structure{contexte} est manquant.}
\end{frame}

\begin{frame}{Propagation Paralèlle \emph{à la} Margolus}
  {Le voisinage de margolus}
  \vfill

  \centering
  \begin{tikzpicture}
    \clip (-27mm,-27mm) rectangle (27mm,27mm);
    \draw[xshift=5mm,yshift=5mm] ( -5cm, -5cm) grid ( 5cm, 5cm);
    \fill[red] (0,0) circle (3mm);
    \only<1>{\draw[xshift=5mm,yshift=5mm, step=2cm, very thick]%
      ( -5cm, -5cm) grid ( 5cm, 5cm);}
    \only<2>{\draw[xshift=-5mm,yshift=-5mm, step=2cm, very thick]%
      ( -5cm, -5cm) grid ( 5cm, 5cm);}
    \begin{scope}[on background layer]
      \only<1>{%
        \fill[red!50,shift={(-5mm,-5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);}
      \only<2>{%
        \fill[red!50,shift={(5mm,5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);}
    \end{scope}
  \end{tikzpicture}

  \vfill~
\end{frame}

\begin{frame}{Propagation Paralèlle \emph{à la} Margolus}
  {Mise à jour \emph{indépendante} d'un bloc}
  \vfill

  \centering
  \begin{tikzpicture}[
    cell/.style={black,size=1.5mm,circle,inner sep=0pt,font=\TINY},
    neighbor cell/.style={black,size=1.5mm,circle,inner sep=0pt,font=\small},
    center cell/.style={cell,white,fill=black},
    spy using outlines={circle,red,size=58mm,magnification=4,connect spies}]
    \begin{scope}[scale=.5]
      \clip (-27mm,-27mm) rectangle (27mm,27mm);

      % Background
      \only<1-3>{%
        \fill[blue!50,shift={(5mm,5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);
        \fill[red!50,shift={(-5mm,-5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);
      }
      \only<4->{%
        \fill[red!50,shift={(-5mm,-5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);
        \fill[blue!50,shift={(5mm,5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);
      }

      \begin{scope}
        \clip (-3mm,-3mm) rectangle (3mm,3mm);
        \draw[very thin] (-5mm,-5mm) grid (5mm,5mm);
      \end{scope}
      \only<1-3>{
        \begin{scope}[shift={(-1cm,0)}]
          \clip (-3mm,-3mm) rectangle (3mm,3mm);
          \draw[very thin] (-5mm,-5mm) grid (5mm,5mm);
        \end{scope}
        \begin{scope}[shift={(-1cm,-1cm)}]
          \clip (-3mm,-3mm) rectangle (3mm,3mm);
          \draw[very thin] (-5mm,-5mm) grid (5mm,5mm);
        \end{scope}
        \begin{scope}[shift={(0cm,-1cm)}]
          \clip (-3mm,-3mm) rectangle (3mm,3mm);
          \draw[very thin] (-5mm,-5mm) grid (5mm,5mm);
        \end{scope}
      }

      \only<1>{
      % Voisins
        \node[neighbor cell] at ( 1cm, 0cm) {$v_{A,1}$};
        \node[neighbor cell] at ( 1cm, 1cm) {$v_{A,2}$};
        \node[neighbor cell] at ( 0cm, 1cm) {$v_{A,3}$};
        \node[neighbor cell] at (-1cm, 1cm) {$v_{B,1}$};
        \node[neighbor cell] at (-2cm, 1cm) {$v_{B,2}$};
        \node[neighbor cell] at (-2cm, 0cm) {$v_{B,3}$};
        \node[neighbor cell] at (-2cm,-1cm) {$v_{C,1}$};
        \node[neighbor cell] at (-2cm,-2cm) {$v_{C,2}$};
        \node[neighbor cell] at (-1cm,-2cm) {$v_{C,3}$};
        \node[neighbor cell] at ( 0cm,-2cm) {$v_{D,1}$};
        \node[neighbor cell] at ( 1cm,-2cm) {$v_{D,2}$};
        \node[neighbor cell] at ( 1cm,-1cm) {$v_{D,3}$};

        \begin{scope}[scale=0.5,shift={(-5mm,-5mm)}]
          \node[center cell] at ( -0mm, -0mm) {$A$};
          \node[cell]        at (-10mm, -0mm) {$B$};
          \node[cell]        at (-10mm,-10mm) {$C$};
          \node[cell]        at ( -0mm,-10mm) {$D$};

          \node[cell] at ( 1cm, 0cm) {$v_{A,1}$};
          \node[cell] at ( 1cm, 1cm) {$v_{A,2}$};
          \node[cell] at ( 0cm, 1cm) {$v_{A,3}$};
          \node[cell] at (-1cm, 1cm) {$v_{B,1}$};
          \node[cell] at (-2cm, 1cm) {$v_{B,2}$};
          \node[cell] at (-2cm, 0cm) {$v_{B,3}$};
          \node[cell] at (-2cm,-1cm) {$v_{C,1}$};
          \node[cell] at (-2cm,-2cm) {$v_{C,2}$};
          \node[cell] at (-1cm,-2cm) {$v_{C,3}$};
          \node[cell] at ( 0cm,-2cm) {$v_{D,1}$};
          \node[cell] at ( 1cm,-2cm) {$v_{D,2}$};
          \node[cell] at ( 1cm,-1cm) {$v_{D,3}$};
        \end{scope}
      }
      \only<2>{
        \begin{scope}[scale=0.5,shift={(-5mm,-5mm)}]
          \node[center cell] at ( -0mm, -0mm) {$A'$};
          \node[cell]        at (-10mm, -0mm) {$B'$};
          \node[cell]        at (-10mm,-10mm) {$C'$};
          \node[cell]        at ( -0mm,-10mm) {$D'$};
        \end{scope}
      }
      \only<3>{
        \begin{scope}[scale=0.5,shift={(5mm,5mm)}]
          \node[center cell] at ( -0mm, -0mm) {$A'$};
          \node[cell]        at (-10mm, -0mm) {$B'$};
          \node[cell]        at (-10mm,-10mm) {$C'$};
          \node[cell]        at ( -0mm,-10mm) {$D'$};
        \end{scope}
        \begin{scope}[scale=0.5,shift={(-15mm,5mm)}]
          \node[cell] at ( -0mm, -0mm) {$A'$};
          \node[cell] at (-10mm, -0mm) {$B'$};
          \node[cell] at (-10mm,-10mm) {$C'$};
          \node[cell] at ( -0mm,-10mm) {$D'$};
        \end{scope}
        \begin{scope}[scale=0.5,shift={(-15mm,-15mm)}]
          \node[cell] at ( -0mm, -0mm) {$A'$};
          \node[cell] at (-10mm, -0mm) {$B'$};
          \node[cell] at (-10mm,-10mm) {$C'$};
          \node[cell] at ( -0mm,-10mm) {$D'$};
        \end{scope}
        \begin{scope}[scale=0.5,shift={(5mm,-15mm)}]
          \node[cell] at ( -0mm, -0mm) {$A'$};
          \node[cell] at (-10mm, -0mm) {$B'$};
          \node[cell] at (-10mm,-10mm) {$C'$};
          \node[cell] at ( -0mm,-10mm) {$D'$};
        \end{scope}
      }
      \only<4>{
        \begin{scope}[scale=0.5,shift={(5mm,5mm)}]
          \node[center cell] at ( -0mm, -0mm) {$A'$};
          \node[cell]        at (-10mm, -0mm) {$B'$};
          \node[cell]        at (-10mm,-10mm) {$C'$};
          \node[cell]        at ( -0mm,-10mm) {$D'$};
        \end{scope}
      }

      % Grilles:
      \draw[xshift=5mm,yshift=5mm,thin] ( -5cm, -5cm) grid ( 5cm, 5cm);
      \only<1-3>{\draw[xshift=5mm,yshift=5mm, step=2cm, thick]%
      ( -5cm, -5cm) grid ( 5cm, 5cm);}
      \only<4>{\draw[xshift=-5mm,yshift=-5mm, step=2cm, thick]%
      ( -5cm, -5cm) grid ( 5cm, 5cm);}

      \only<1-3>{
        \coordinate (spyhook) at (-5mm,-5mm);
      }
      \only<4>{
        \coordinate (spyhook) at (5mm,5mm);
      }
    \end{scope}

    \spy on (spyhook) in node (zoom) at (5cm,0);
  \end{tikzpicture}

  %\only<1-2>{
  %Toute l'information \emph{nécessaire} est disponible pour mettre à jour $A$.
  %$$ A' = f( A, v_{A_1}, v_{A_2}, v_{A_3}, v_{B_1}, B, C, D, v_{D_3} ) $$
  %ainsi que $B$, $C$ et $D$, symétriquement.
  %}
  %\only<3>{
  %Le bloc $(A',B',C',D')$ est répliqué 4 fois.}
  %\only<4>{
  %Au décalage de la grille, le nouveau bloc est prêt pour une mise à jour.
  %}


  \vfill~
\end{frame}

%\begin{frame}{Propagation Paralèlle \emph{à la} Margolus}
%  {Mise à jour \emph{indépendante} d'un bloc}
%  \vfill
%
%  \begin{columns}[c]
%    \column{.4\textwidth}\centering
%    \begin{tikzpicture}[scale=.5]
%      \clip (-27mm,-27mm) rectangle (27mm,27mm);
%      \draw[xshift=5mm,yshift=5mm] ( -5cm, -5cm) grid ( 5cm, 5cm);
%      \fill[red] (0,0) circle (3mm);
%      \only<1-3>{\draw[xshift=5mm,yshift=5mm, step=2cm, very thick]%
%        ( -5cm, -5cm) grid ( 5cm, 5cm);}
%      \only<4->{\draw[xshift=-5mm,yshift=-5mm, step=2cm, very thick]%
%        ( -5cm, -5cm) grid ( 5cm, 5cm);}
%      \begin{scope}[on background layer]
%        \only<1-3>{%
%        \fill[blue!50,shift={(5mm,5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);
%        \fill[red!50,shift={(-5mm,-5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);}
%        \only<4->{%
%        \fill[red!50,shift={(5mm,5mm)}] (-1cm,-1cm) rectangle (1cm,1cm);}
%      \end{scope}
%    \end{tikzpicture}
%    \column{.6\textwidth}\centering
%    \begin{tikzpicture}
%      \only<1-2,4>{%
%      \fill[red!50] (-1cm,-1cm) rectangle (1cm,1cm);}
%      \only<3>{%
%      \fill[red!50, shift={(1cm,1cm)}] (0cm,0cm) rectangle (1cm,1cm);
%      \fill[red!50, shift={(1cm,-2cm)}] (0cm,0cm) rectangle (1cm,1cm);
%      \fill[red!50, shift={(-2cm,1cm)}] (0cm,0cm) rectangle (1cm,1cm);
%      \fill[red!50, shift={(-2cm,-2cm)}] (0cm,0cm) rectangle (1cm,1cm);}
%      \only<1>{%
%      \fill[blue!50] (0cm,1cm) -- (0cm,2cm) -- (2cm,2cm) -- (2cm,0cm) -- (1cm,0cm) -- (1cm,1cm) -- cycle;}
%      \draw[very thin,dashed] (-2,-2) grid (2,2);
%      \draw[step=2cm] (-2,-2) grid (2,2);
%      \draw[step=4cm, very thick, shift={(-2cm,-2cm)}] (-4mm,-4mm) grid (44mm,44mm);
%      \only<1>{%
%      \node [fill=red, minimum size=6mm, inner sep=0, circle] (A) at (5mm,5mm) {A};%
%      \node [draw=red, thick, dashed, minimum size=6mm, inner sep=0, circle] (B) at (-5mm,5mm) {B};%
%      \node [draw=red, thick, dashed, minimum size=6mm, inner sep=0, circle] (C) at (-5mm,-5mm) {C};%
%      \node [draw=red, thick, dashed, minimum size=6mm, inner sep=0, circle] (D) at (5mm,-5mm) {D};%
%      \node (va1) at (15mm,5mm) {$v_{A_1}$};%
%      \node (va2) at (15mm,15mm) {$v_{A_2}$};%
%      \node (va3) at (5mm,15mm) {$v_{A_3}$};%
%      \node (vb1) at (-5mm,15mm) {$v_{B_1}$};%
%      \node (vd3) at (15mm,-5mm) {$v_{D_3}$};%
%      }
%      \only<2>{%
%      \node [fill=red, minimum size=6mm, inner sep=0, circle] (A') at (5mm,5mm) {A'};%
%      \node                                                   (B') at (-5mm,5mm) {B'};%
%      \node                                                   (C') at (-5mm,-5mm) {C'};%
%      \node                                                   (D') at (5mm,-5mm) {D'};%
%      }
%      \only<3>{%
%      \node [fill=red, minimum size=6mm, inner sep=0, circle] (A') at (15mm,15mm) {A'};%
%      \node                                                   (B') at ( 5mm,15mm) {B'};%
%      \node                                                   (C') at ( 5mm, 5mm) {C'};%
%      \node                                                   (D') at (15mm, 5mm) {D'};%
%      \begin{scope}[shift={(-15mm,5mm)}]
%      \node (A') at (10mm,10mm) {A'};%
%      \node (B') at ( 0mm,10mm) {B'};%
%      \node (C') at ( 0mm, 0mm) {C'};%
%      \node (D') at (10mm, 0mm) {D'};%
%      \end{scope}
%      \begin{scope}[shift={(5mm,-15mm)}]
%      \node (A') at (10mm,10mm) {A'};%
%      \node (B') at ( 0mm,10mm) {B'};%
%      \node (C') at ( 0mm, 0mm) {C'};%
%      \node (D') at (10mm, 0mm) {D'};%
%      \end{scope}
%      \begin{scope}[shift={(-15mm,-15mm)}]
%      \node (A') at (10mm,10mm) {A'};%
%      \node (B') at ( 0mm,10mm) {B'};%
%      \node (C') at ( 0mm, 0mm) {C'};%
%      \node (D') at (10mm, 0mm) {D'};%
%      \end{scope}
%      }
%      \only<4>{
%      \begin{scope}[shift={(-15mm,-15mm)}]
%      \node [fill=red, minimum size=6mm, inner sep=0, circle] (A') at (10mm,10mm) {A};%
%      \node                                                   (B') at ( 0mm,10mm) {B};%
%      \node                                                   (C') at ( 0mm, 0mm) {C};%
%      \node                                                   (D') at (10mm, 0mm) {D};%
%      \end{scope}
%      }
%    \end{tikzpicture}
%  \end{columns}
%
%  \centering
%  \only<1-2>{
%  Toute l'information \emph{nécessaire} est disponible pour mettre à jour $A$.
%  $$ A' = f( A, v_{A_1}, v_{A_2}, v_{A_3}, v_{B_1}, B, C, D, v_{D_3} ) $$
%  ainsi que $B$, $C$ et $D$, symétriquement.
%  }
%  \only<3>{
%  Le bloc $(A',B',C',D')$ est répliqué 4 fois.}
%  \only<4>{
%  Au décalage de la grille, le nouveau bloc est prêt pour une mise à jour.
%  }
%
%
%  \vfill~
%\end{frame}