algorithmes.tex

% !TEX encoding = IsoLatin9

%%%%%%%%%%%%%%%%%%%%% SECTION 1
\section{Les algorithmes}\label{section:1}
\begin{frame}
  \begin{columns}
    \column{4.8cm}
    \tableofcontents[currentsection,hideothersubsections]
    \column{7cm}
    \centering{
      \includegraphics[width=7cm]{fig/Algorithm-sheldon.png}
      
      \textit{``I believe I've isolated the algorithm for making friends.''}\\
      \small{
        \hfill Sheldon Cooper, 
        
        \hfill in \textit{The Big Band Theory}, Season 2, Episode 13
      }
    }
  \end{columns}
  
\end{frame}

%%%%%%%%%%%%%%%%%%%%% 

\subsection{Introduction}
\begin{frame}
  \frametitle{Pourquoi faire appel à des algorithmes ?}
  Pour automatiser des tâches
  
  Exemples :
  \begin{itemize}
  \item Métier à tisser\\
  \item Méthode de calcul à la main d'une division\\
  \item Recette de cuisine\\
  \item ...\\
  \end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%% 

\begin{frame}
  \frametitle{Qu'est-ce qu'un algorithme ?}
  \begin{alertblock}{Définition}
    Un algorithme est un ensemble 
    ordonné d'instructions simples
    permettant de résoudre un problème.
  \end{alertblock}
\end{frame}

%%%%%%%%%%%%%%%%%% 

\begin{frame}
\frametitle{Remarques}
  \begin{block}{Un algorithme nécessite :}
    \begin{itemize}
    \item Des objets sur lesquels travailler,\\
    \item Un langage non ambigu,\\
    \item Des spécifications (description de l'algorithme).\\
    \end{itemize}
  \end{block}
  
  \begin{block}{}
    Il n'existe généralement pas un unique algorithme pour traiter un problème.
  \end{block}
\end{frame}

%%%%%%%%%%%%%%%%%

\begin{frame}
  \frametitle{Historique}
  \begin{description}
\item[3ème siècle avant JC] \textit{Livre VII des Eléments d'Euclide}
 \begin{columns}[T]
    \column{8cm}
Détermination du plus grand diviseur commun entre deux nombres :
PGCD(12,8)=4\\

 \column{4cm}
    \centering{
      \includegraphics[width=4cm]{fig/Euclide.jpg}
}
\end{columns}
\item[8ème siècle après JC] \textbf{\textit{Al-Khawarizmi}} : Méthodes de résolution d'équations.
Son nom est à l'origine du mot "algorithme".
\end{description}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Construction d'un algorithme}

\begin{frame}
  \begin{columns}
    \column{4.8cm}
    \tableofcontents[currentsection,hideothersubsections,currentsubsection]
    \column{7cm}
    \centering{
      \includegraphics[width=4cm]{fig/construction.png}
     % \textit{``I believe I've isolated the algorithm for making friends.''}
     % \small{
     %   \hfill Sheldon Cooper, 
     %   \hfill in \textit{The Big Band Theory}, Season 2, Episode 13
%     }
    }
  \end{columns}
\end{frame}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
  \frametitle{Construction d'un algorithme}
\begin{block}{Pour chaque problème, il vous est demandé de définir clairement :}
\begin{itemize}
\item Les éventuelles \red{données d'entrée du problème} en précisant leurs types et leur rôle,\\
\item les éventuelles \red{données de sortie du problème} en précisant leurs types, \\
\item les différentes \red{instructions} permettant d'obtenir les données de sorties à partir
des données d'entrée.\\
\end{itemize}
\end{block}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[fragile]
\frametitle{Exemple}
Algorithme qui détermine le prix d'entrée dans un musée (les mineurs payent moitié prix)
\pause
\begin{columns}[t]
\column{6 cm}
\begin{exampleblock}{Données}
\begin{algorithmic}[1]
\REQUIRE{age (entier)}\\
\COMMENT{age du client}
\ENSURE{tarif (décimal)}\\
\COMMENT{prix de l'entrée}
\end{algorithmic}
\end{exampleblock}
\column{5 cm}
\pause

\begin{exampleblock}{Instructions}
\begin{algorithmic}[0]
\IF{age < 18}
\STATE tarif $\leftarrow$ 4
\ELSE
\STATE tarif $\leftarrow$ 8
\ENDIF
\RETURN{tarif}
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}

%%%%%%%%%%%%%

\subsection{Structures de base d'un algorithme}

\begin{frame}
  \begin{columns}
    \column{4.8cm}
    \tableofcontents[currentsection,hideothersubsections,currentsubsection]
    \column{7cm}
    \centering{
      \includegraphics[width=7cm]{fig/lego.jpg}
     % \textit{``I believe I've isolated the algorithm for making friends.''}
     % \small{
     %   \hfill Sheldon Cooper, 
     %   \hfill in \textit{The Big Band Theory}, Season 2, Episode 13
%     }
    }
  \end{columns}
\end{frame}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Instructions élémentaires}
\begin{itemize}
\item \textbf{Opérations arithmétiques de base ($+$, $-$, $\times$, $/$, mod, ...)}\\
\item \textbf{Affectation de valeurs (ex : $x \leftarrow 2$)}\\
\item \textbf{Afficher, lire}\\
\item Structures conditionnelles\\
\item Structures répétitives\\
\end{itemize}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures conditionnelles 1/2}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=1.5cm, text badly centered,
                        rounded corners, aspect=2 },
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=1.5cm, text centered,
                        rounded corners, minimum height=2em },
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=1.5cm,
  ]
  \node (rac) {} ;
  \node (condition) [decision, below of=rac] {\red{condition}} ; 
  \node (center) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,below of =condition]{};
  \node (false) [block, left of=center,xshift=-3mm] {Action F};
  \node (true) [block, right of=center,xshift=3mm] {Action V};
   \node (end) [below of=center]{};
  % Define nodes in a matrix
  %\matrix [column sep=5mm, row sep=10mm] {
  %& \node (rac) {}; & \\
  %& \node [decision] (condition) {condition}; & \\
  %\node [block] (true) {Action V}; & & \node [block] (true) {Action V} ; \\
 % & \node (end) {}; \\
  %};
  
  % connect nodes
  \begin{scope}[every path/.style=line]
  \path (rac) -- (condition);
  \path (condition) -| node [near start, above] {vraie} (true);
  \path (condition) -| node [near start, above] {fausse} (false);
  \path (center) -- (end) ;
  %\path (false) -| (end);
  \end{scope}
  \draw[-, thick] (true) -- (center) ;
    \draw[-, thick] (false) -- (center) ;

\end{tikzpicture}
\end{figure}
%\end{block}
\column{5cm}

\begin{block}{}
\begin{algorithmic}[0]
\IF{\red{condition}}
\STATE Action V
\ELSE
\STATE Action F
\ENDIF
\end{algorithmic}
\end{block}

\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\IF{\red{age < 18}}
\STATE tarif $\leftarrow$ 4
\ELSE
\STATE tarif $\leftarrow$ 8
\ENDIF
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures conditionnelles 2/2}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=1.5cm, text badly centered,
                        rounded corners, aspect=2 },
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=1.5cm, text centered,
                        rounded corners, minimum height=2em },
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=1.5cm,
  ]
  \node (rac) {} ;
  \node (condition) [decision, below of=rac] {\red{condition}} ; 
  \node (center) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,below of =condition]{};
  %\node (false) [block, left of=center,xshift=-3mm] {Action F};
  \node (true) [block, right of=center,xshift=3mm] {Action V};
   \node (end) [below of=center]{};
  % Define nodes in a matrix
  %\matrix [column sep=5mm, row sep=10mm] {
  %& \node (rac) {}; & \\
  %& \node [decision] (condition) {condition}; & \\
  %\node [block] (true) {Action V}; & & \node [block] (true) {Action V} ; \\
 % & \node (end) {}; \\
  %};
  
  % connect nodes
  \begin{scope}[every path/.style=line]
  \path (rac) -- (condition);
  \path (condition) -| node [near start, above] {vraie} (true);
 % \path (condition) -| node [near start, above] {fausse} (false);
  \path (center) -- (end) ;
  %\path (false) -| (end);
  \end{scope}
  \draw[-, thick] (true) -- (center) ;
  \draw[-, thick] (condition) -- node [near start, left] {fausse}  (center) ;

\end{tikzpicture}
\end{figure}
%\end{block}
\column{5cm}

\begin{block}{}
\begin{algorithmic}[0]
\IF{\red{condition}}
\STATE Action V
\ENDIF
\end{algorithmic}
\end{block}

\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\IF{\red{age < 18}}
\PRINT "Réduction de 50\%"
\ENDIF
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures à choix multiple}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=1.5cm, text badly centered,
                        rounded corners, aspect=2.2, scale=0.7 },
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=2cm, text centered,
                        rounded corners, minimum height=2em , scale=0.8},
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=1.8cm,
  ]
  \node (rac) {} ;
  \node (selon) [block, below of=rac, yshift=7mm] {Selon \red{le cas}} ;
  \node (cas1) [decision, below of=selon] {Cas 1} ;
  \node (cas2) [decision, below of=cas1]  {Cas 2} ;
  \node (casn) [decision, below of=cas2, yshift=-3mm] {Cas n} ;
  \node (def)  [decision, below of=casn] {défaut} ;
  \node (ac1) [block, right of = cas1, xshift= 11mm] {Action 1} ;
  \node (ac2) [block, right of = cas2, xshift= 11mm] {Action 2} ;
  \node (acn) [block, right of = casn, xshift= 11mm] {Action n} ;
  \node (acd) [block, right of = def, xshift =11mm] {Action par défaut} ;
  \node (ce1) [draw, circle, thick, inner sep=2pt, minimum size =0pt, radius = 2pt, right of = ac1, xshift=-3mm]{};
  \node (ce2) [draw, circle, thick, inner sep=2pt, minimum size =0pt, radius = 2pt, right of = ac2, xshift=-3mm]{};
  \node (cen) [draw, circle, thick, inner sep=2pt, minimum size =0pt, radius = 2pt, right of = acn, xshift=-3mm]{};
  \node (ced) [draw, circle, thick, inner sep=2pt, minimum size =0pt, radius = 2pt, right of = acd, xshift=-3mm]{};
  \node (center)  [draw, circle, thick, inner sep=2pt, minimum size =0pt, radius = 2pt, below of = def, yshift=11mm]{};
  \node (out) [below of= center, yshift = 12mm]{};
%  \node (center) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,below of =condition]{};
 

  % connect nodes
  \begin{scope}[every path/.style=line]
  \path (rac) -- (selon);
  \path (selon) -- (cas1);
  \path (cas1) -- (cas2);
  \path (casn) -- (def);
  \path (cas1) -- (ac1) ;
  \path (cas2) -- (ac2) ;
  \path (casn) -- (acn) ;
  \path (def) -- (acd) ;
  \path (ced) |- (center);
  \path (center) -- (out) ;

  \end{scope}
  \draw[-, thick] (ac1) -- (ce1) ;
  \draw[-, thick] (ac2) -- (ce2) ;
  \draw[-, thick] (acn) -- (cen) ;
  \draw[-, thick] (acd) -- (ced) ;
  \draw[-, thick] (ce1) -- (ce2) ;
  \draw[-, thick] (ce2) -- (cen) ;
  \draw[-, thick] (cen) -- (ced) ;
  
  \draw[-, thick] (def) -- (center) ;

  
\draw[dotted, -, thick] (cas2) -- (casn) ;
\end{tikzpicture}
\end{figure}
%\end{block}
\column{5.1cm}

\begin{block}{}
\begin{algorithmic}[0]
\STATE{\textbf{Selon} \red{le cas}}
\STATE \hspace{0.8em} Cas 1 : Action 1 
\STATE \hspace{0.8em} Cas 2 : Action 2 
\STATE \hspace{0.8em} ... 
\STATE \hspace{0.8em} Cas n : Action n
\STATE \hspace{0.8em} Défaut : Action par défaut
\STATE{\textbf{Fin Selon}}
\end{algorithmic}
\end{block}

\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\STATE{\textbf{Selon} \red{valeur de age}}
\STATE \hspace{0.8em} 0..6 : tarif $\leftarrow$ 0
\STATE \hspace{0.8em} 7..18 : tarif $\leftarrow$ 4
\STATE \hspace{0.8em} Défaut : tarif $\leftarrow$ 8
\STATE{\textbf{Fin Selon}}
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures répétitives 1/2}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=3cm, inner sep = 1pt,text badly centered,
                        rounded corners, aspect=2, scale=0.9},
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=1.5cm, text centered,
                        rounded corners, minimum height=2em },
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=2cm,
  ]
  \node (rac) {} ;
  %\node (bet) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,yshift=10mm, below of =rac]{};
  \node (condition) [decision, below of=rac, yshift=-3mm] {Répéter tant que \red{condition}} ; 
  \node (action) [block, below of = condition, yshift = -3mm] {Actions} ;
  \node (right) [right of = condition, xshift = 6mm] {} ;
   \node (left) [left of = condition, xshift = -7mm] {} ;

  \node (center) [below of =action, yshift=12mm]{};
  \node (end) [below of=center,yshift = 10mm]{};
  
  
  % connect nodes
  \begin{scope}[every path/.style=line]
%  \path (rac) -- (bet);
  \path (rac) -- (condition);
  \path (condition) -- node [near start, right] {vraie} (action);
 % \path (right.center) |- (center);
  \path (center.center) -- (end) ;
  \path (left.center) -- (condition) ;
  %\path (false) -| (end);
  \end{scope}
 % \draw[-, thick] (true) -- (center) ;
   % \draw[-, thick] (false) -- (center) ;
\draw[-, thick] (condition) -- node [near start, above] {fausse} (right.center);
\draw[-, thick] (action) -| (left.center);
\draw [-, thick] (right.center) |- (center.center);

\end{tikzpicture}
\end{figure}
%\end{block}
\column{5cm}

\begin{block}{}
\begin{algorithmic}[0]
\WHILE{\red{condition}}
\STATE Actions
\ENDWHILE
\end{algorithmic}
\end{block}

\begin{alertblock}{}
Les actions peuvent ne \textbf{pas} être exécutées
si la condition est fausse au départ.
\end{alertblock}
\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\WHILE{\red{tickets>0}}
\STATE vendre un ticket
\ENDWHILE
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures répétitives 2/2}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=3cm, inner sep = 1pt,text badly centered,
                        rounded corners, aspect=2, scale=0.9},
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=1.5cm, text centered,
                        rounded corners, minimum height=2em },
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=2cm,
  ]
  \node (rac) {} ;
%  \node (bet) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,yshift=10mm, below of =rac]{};
 \node (action) [block, below of = rac, yshift = 10mm] {Actions} ;
  \node (condition) [decision, below of=action, yshift=-3mm] {Répéter tant que \red{condition}} ; 
 
%  \node (right) [right of = condition, xshift = 6mm] {} ;
   \node (left) [left of = condition, xshift = -5mm] {} ;

  \node (center) [below of =condition, yshift=12mm]{};
  \node (end) [below of=center,yshift = 5mm]{};
  
  
  % connect nodes
  \begin{scope}[every path/.style=line]
%  \path (rac) -- (bet);
  \path (rac) -- (action);
  \path (left.center) |- node [near start, right] {vraie} (action);
  \path (action) -- (condition);
  \path (condition) -- node [near start, right] {fausse} (end) ;
  %\path (left.center) -- (bet) ;
  %\path (false) -| (end);
  \end{scope}
 % \draw[-, thick] (true) -- (center) ;
 \draw[-, thick] (condition) -- (left.center) ;
%\draw[-, thick] (condition) -- node [near start, above] {fausse} (right.center);
%\draw[-, thick] (action) -| (left.center);
%\draw [-, thick] (right.center) |- (center.center);

\end{tikzpicture}
\end{figure}
%\end{block}
\column{5cm}

\begin{block}{}
\begin{algorithmic}[0]
\REPEAT
\STATE Actions
\UNTIL{\red{condition}}
\end{algorithmic}
\end{block}

\begin{alertblock}{}
Les actions sont exécutées au moins une fois.
\end{alertblock}
\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\REPEAT
\STATE vendre un ticket
\UNTIL{ticket>0}
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]
\frametitle{Structures itératives}
\begin{columns}[t]
\column{6cm}
%\begin{block}

\begin{figure}
\begin{tikzpicture} [
    auto,
    decision/.style = { diamond, draw=blue, thick, fill=blue!20,
                        text width=3cm, inner sep = 1pt,text badly centered,
                        rounded corners, aspect=2, scale=0.9},
    block/.style    = { rectangle, draw=blue, thick, 
                        fill=blue!20, text width=1.5cm, text centered,
                        rounded corners, minimum height=2em },
    line/.style     = { draw, thick, ->, shorten >=2pt },
    node distance=2cm,
  ]
  \node (rac) {} ;
\node(condition)[decision, below of = rac]{Répéter \red{n} fois};
\node(action)[block, below of = condition]{Actions};
%  \node (bet) [draw,circle,  thick, inner sep=2pt,minimum size= 0pt, radius = 2pt,yshift=10mm, below of =rac]{};
% \node (action) [block, below of = rac, yshift = 10mm] {Actions} ;
 % \node (condition) [decision, below of=action, yshift=-3mm] {Répéter tant que \red{condition}} ; 
 
  \node (right) [right of = condition, xshift = 6mm] {} ;
  \node (left) [left of = condition, xshift = -6mm] {} ;

  \node (center) [below of =action,yshift=12mm]{};
  \node (end) [below of=center, yshift=9mm]{};
  
  
  % connect nodes
  \begin{scope}[every path/.style=line]
    \path (rac) -- (condition);
    \path (left.center) -- (condition);
  %  \path (right.center) -- (condition);
    \path (center.center) -- (end);
% \path (left.center) |- node [near start, right] {vraie} (action);
    \path (condition) -- (action);
    % \path (condition) -- node [near start, right] {fausse} (end) ;
    % \path (left.center) -- (bet) ;
    % \path (false) -| (end);
    
  \end{scope}
 % \draw[-, thick] (true) -- (center) ;
 \draw[-, thick] (action) -| (left.center) ;
 \draw[-, thick] (condition) --  node [midway, above, font = \scriptsize] {compteur>n} (right.center) ;
 \draw[-, thick] (right.center) |-(center.center) ;

%\draw[-, thick] (condition) -- node [near start, above] {fausse} (right.center);
%\draw[-, thick] (action) -| (left.center);
%\draw [-, thick] (right.center) |- (center.center);

\end{tikzpicture}
\end{figure}
%\end{block}
\column{6cm}

\begin{block}{}
\begin{algorithmic}[0]
\FOR {i = 1 à n}
\STATE Actions
\ENDFOR
\end{algorithmic}
\end{block}

\begin{alertblock}{}
On connaît le nombre d'itérations à l'avance.
\end{alertblock}
\begin{exampleblock}{Un exemple}
\begin{algorithmic}[0]
\FOR {i = 1 à nbre\_guide}
\IF {place pour guide i>0}
\PRINT {"Il reste des places pour le guide i"}
\ENDIF
\ENDFOR
\end{algorithmic}
\end{exampleblock}

\end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Tester un algorithme}

\begin{frame}
  \begin{columns}
    \column{4.8cm}
    \tableofcontents[currentsection,hideothersubsections,currentsubsection]
    \column{7cm}
    \centering{
      \includegraphics[width=7cm]{fig/dominos.jpg}
     % \textit{``I believe I've isolated the algorithm for making friends.''}
     % \small{
     %   \hfill Sheldon Cooper, 
     %   \hfill in \textit{The Big Band Theory}, Season 2, Episode 13
%     }
    }
  \end{columns}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Jeu d'essais}
\begin{itemize}
\item Faire fonctionner l'algorithme avec des valeurs.
\item Traiter tous les cas possibles.
\item En particulier les cas pouvant nécessaiter à traitement spécifique.
\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[fragile]
\frametitle{Un exemple :}
\framesubtitle{Calcul de la valeur absolue d'un nombre}
\begin{exampleblock}{Données}
\begin{algorithmic}[1]
\REQUIRE{X (entier)}\\
\COMMENT{nombre dont on veut calculer la valeur absolue}
\ENSURE{Val\_abs (entier)}\\
\COMMENT{valeur absolue de X}
\end{algorithmic}
\end{exampleblock}
\begin{columns}
\column{0.45\textwidth}

\begin{exampleblock}{Instructions}
\begin{algorithmic}[0]
\IF{$X \geq 0$}
\STATE Val\_abs $\leftarrow$ X
\ELSE
\STATE  Val\_abs $\leftarrow$ -X
\ENDIF
\RETURN{ Val\_abs}
\end{algorithmic}
\end{exampleblock}

\column{0.45\textwidth}
\pause
\begin{exampleblock}{Jeu d'essais}
\begin{itemize}
\item X $\leftarrow$ un entier négatif
\item X $\leftarrow$ un entier positif
\item X $\leftarrow$ 0
\end{itemize}
\end{exampleblock}
\end{columns}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Exemples}

\begin{frame}
  \begin{columns}
    \column{4.8cm}
    \tableofcontents[currentsection,hideothersubsections,currentsubsection]
    \column{7cm}
    \centering{
      %\includegraphics[width=7cm]{fig/dominos.jpg}
     % \textit{``I believe I've isolated the algorithm for making friends.''}
     % \small{
     %   \hfill Sheldon Cooper, 
     %   \hfill in \textit{The Big Band Theory}, Season 2, Episode 13
%     }
    }
  \end{columns}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Exemple 1}
Un colis est conforme si ses trois dimensions
($L \times l \times h$ avec $h \leq l \leq L$) vérifient
les conditions suivantes : 
\begin{itemize}
\item Un rectangle de 10cm $\times$ 7cm doit pouvoir s'inscrire
dans une face du colis,\\
\item $L + l + h \leq 100$ cm,\\
\item $L \leq 60 cm.$\\
\end{itemize}

\begin{block}{Exercice}
Ecrire l'algorithme permettant de savoir si un colis est conforme ou non.
\end{block}
\end{frame}

\ifdefined\correction
\begin{frame}[fragile]
\frametitle{Exemple 1 -corrigé}
\begin{block}{}
\begin{algorithmic}[0]
\REQUIRE{~\\L (réel),l (réel),h (réel)}
\COMMENT{longeur,largeur,hauteur}
\ENSURE{Pas de sortie}

\IF {($L>10$ \textbf{et} $l>7$)\\ 
\textbf{et} $L+l+h \leq 100$\\
\textbf{et} $L \leq 60$
}
\PRINT "Colis conforme"
\ENDIF
\end{algorithmic}
\end{block}
\end{frame}
\fi

\begin{frame}[fragile]
\frametitle{Exemple 2}
\framesubtitle{Que fait cet algo ?}
\begin{algorithmic}[0]
\REQUIRE{~\\X, tableau à 2 dimension de n$\times$n réels,\\
v, vecteur de n réels}
\ENSURE{s, vecteur de n réels}
\FOR{i variant de 1 à n}
\STATE s(i) $\leftarrow$ 0
\FOR {j variant de 1 à n}
\STATE s(i) $\leftarrow$ s(i) + X(i,j).v(j)
\ENDFOR
\ENDFOR
\RETURN{s}
\end{algorithmic}
\end{frame}

\ifdefined\correction
\begin{frame}
\frametitle{Corrigé}
\begin{block}{Multiplication Matrice-vecteur}
\begin{equation*}
s = X.v
\end{equation*}

\begin{equation*}
s_i = \sum_{j=1}^n X_{ij}.v_j
\end{equation*}


\end{block}
\end{frame}
\fi