\documentclass[xcolor=hyperref,hyperef={naturalnames,pdfpagelabels},french,envcountsect]{beamer}
\usepackage{etex}
\usepackage[beamer]{preambule}
\usepackage{algo}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark}
%\usepackage{movie15}
%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}


\setlength{\columnseprule}{0pt}

\graphicspath{{/home/moi/Lycee/2nde/2009_10/}{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Figures/figuresTS/}{/home/moi/Lycee/TDmaple/2007_8/}{/home/moi/IREM/IREM10_06_09/}}



\newcommand\Pasc{\lstset{numbers=none,language=Pascal,xleftmargin=10pt,%
keywordstyle =\small\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white}\small,commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\caml{
\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\color{blue!30}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


% \newcommand\caml{
% \lstset{numbers=none,language=Caml,xleftmargin=10pt,%
% keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
% }
%\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}

\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[Option informatique] % (optional, use only with long paper titles)
{Méthodes de programmation}

\subtitle{ }

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN  }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{MPSI - Lycée Saint-Stanislas}% (optional, but mostly needed)

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{\today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}







\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}
\Pasc




\section{Algorithme, algorithmique, programmation}


\begin{frame}

\begin{itemize}
\item Algorithme d'Euclide.

\item

Algorithme d'addition posée.

\item

Recette de cuisine.

\item

Rechercher un mot dans le dictionnaire.

\end{itemize}
\end{frame}




\begin{frame}
\begin{itemize}

\item Machine abstraite.

\item

Langage algorithmique.


\item 

L'algorithme est-il correct? Peut-on le prouver? 

\item 

L'algorithme est-il efficace? Quel est son \og coût\fg{}?

\item

Programmer dans un certain langage: le PASCAL.

\item Syntaxe et sémantique: \og \textit{Le lapin mange le chasseur}\fg{}.

\end{itemize}
\end{frame}


\section{Spécification}

\begin{frame}

\begin{itemize}

\item   \textit{On doit porter un casque sur une moto.}


\item 

\textit{On doit porter les animaux sur les escaliers mécaniques.}

\item

Langage naturel / langage formel.


\item 

Spécification / implantation \pause Énoncé / démonstration.

\item 

Spécifier, ce n'est pas dire  comment sont effectués les calculs mais ce
qu'ils calculent.


\end{itemize}
\end{frame}


\begin{frame}
\begin{itemize}
\item   Un exemple:  spécifions une fonction qui  a pour données  un nombre en
  base dix et qui a pour résultat son écriture en base deux. \pause

Précisons un peu. 
\item La donnée  est un nombre entier positif écrit en
  base dix. 
\item Le résultat  est une liste d'entiers appartenant  à $\{0;1\}$ dans
  l'ordre décroissant  des puissances de deux associées.  On convient de
  commencer par  la plus  grande puissance dont  le coefficient  est non
  nul.
\item Par exemple, si on entre 11 on obtiendra... $[1,0,1,1]$.
\item En effet, $11=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0$.
\end{itemize}
\end{frame}

\begin{frame}
  On ne  sait pas encore  \textit{comment} calculer le résultat  mais on
  sait  déjà \textsc{ce  que calcule}  cette  fonction et  on peut  donc
  l'intégrer dans des calculs plus complexes.
\end{frame}



\section{Est-ce le résultat qui compte?}


\subsection{Spécifions le problème}

\begin{frame}
Prenons  un exemple  simple: étant  donné un  entier relatif  $a$  et un
entier naturel $n$, on voudrait obtenir $a^n$ qui sera un entier relatif.
\end{frame}

\begin{frame}[fragile]
  Spécifions notre problème de manière plus formelle:

\pause

  \begin{center}
    \verb+puissance(a:entier;n:entier positif):entier+

\verb+puissance(a,n) renvoie a à la puissance n+
  \end{center}
\end{frame}


\subsection{Premier algorithme : fonction récursive}

\begin{frame}[fragile]
\begin{algo}
\FUNC{puissance}{%
\pfarg{a,n}{entier}}{entier}
\BEGIN
\IF{n=0}
\STATE{1}
\ELSE
\STATE{a*puissance(a,n-1)}
\ENDIF
\END 
\end{algo}

\begin{itemize}
\item Que fait cet algorithme?
\item Peut-on le prouver?
\item Comment caractériser son efficacité?
\end{itemize}

\end{frame}


\begin{frame}
  Il  s'agit  d'un  algorithme  \textit{récursif} car  la  fonction  est
  définie en fonction d'elle-même.
\end{frame}


\begin{frame}[fragile]

Traduction possible en Pascal:


\begin{lstlisting}[caption={}]
FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
 BEGIN
  IF n=0
  THEN Puissance:=1
  ELSE Puissance:=a*Puissance(a,n-1);
 END;
\end{lstlisting}

\pause

Mais Pascal ne  fonctionne pas en mode interactif.  Il faut donc inclure
cette fonction dans un programme.

\end{frame}


\begin{frame}[fragile]

Programme \verb+Puissance_rec+ utilisant la fonction \verb+Puissance+

\begin{lstlisting}[caption={puissance(a,n) : version récursive 1 en Pascal}]
PROGRAM Puissance_rec;
VAR a:INTEGER; n:INTEGER;

 FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
  BEGIN
   IF n=0
   THEN Puissance:=1
   ELSE Puissance:=a*Puissance(a,n-1);
  END;

BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  WRITE(a,'^',n,' = ',Puissance(a,n));
  READLN;
END.                     
\end{lstlisting}
  
\end{frame}


\begin{frame}[fragile]
et cela donne:

\begin{boxedverbatim}
  Entrer a : 2
  Entrer n : 5

  2^5 = 32
\end{boxedverbatim}

\end{frame}


\begin{frame}[fragile]
Dans un autre langage comme Caml,  l'idée est la même mais la manière de
l'implanter et de l'utiliser diffèrent:
\caml
\begin{lstlisting}[caption={}]
# let rec puissance(a,n)=
      if n==0 
      then 1
      else a*puissance(a,n-1);; 
      val puissance : int * int -> int = <fun>
# puissance(2,5);;
- : int = 32
\end{lstlisting}
\Pasc
\end{frame}


\subsection{Deuxième algorithme : boucle \og pour\fg{}}


\begin{frame}[fragile]

\begin{algo}
\FUNC{puissance}{%
\pfarg{a,n}{entier}}{entier}
\VAR
\DECLVAR{res,k}{entier}
\ENDVAR
\BEGIN
\STATE{res \recoit{} 1}
\FOR{k}{1}{n}
\STATE{res \recoit{} res*a}
\ENDFOR
\RETURN{res}
\END 
\end{algo}
\begin{itemize}
\item Que fait cet algorithme?
\item Peut-on le prouver?
\item Comment caractériser son efficacité?
\end{itemize}

\end{frame}


\begin{frame}[fragile]
  En Pascal:

  \begin{lstlisting}[caption={}]
FUNCTION Puiss(a:INTEGER;n:INTEGER):INTEGER;
VAR res:INTEGER; k:INTEGER;
 BEGIN
  res:=1;
  FOR k:=1 TO n DO res:=res*a;
  Puiss:=res;
 END;          
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]

Et si on l'introduit dans un programme:

\begin{lstlisting}[caption={}]
PROGRAM Puissance_it;
VAR a:INTEGER; n:INTEGER;

FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
VAR res:INTEGER; k:INTEGER;
 BEGIN
  res:=1;
  FOR k:=1 TO n DO res:=res*a;
  Puiss:=res;
 END;

BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  WRITE(a,'^',n,' = ',Puissance(a,n));
  READLN;
END.              
\end{lstlisting}

\end{frame}


\begin{frame}
Que  la fonction de  calcul de la  puissance soit
récursive  ou itérative,  la  manière de  l'utiliser  dans le  programme
principal est la même.
\end{frame}









\subsection{Troisième algorithme : boucle \og tant que\fg{}}




\begin{frame}[fragile]
\begin{algo}
\FUNC{puissance}{%
\pfarg{a,n}{entier}}{entier}
\VAR
\DECLVAR{res,k}{entier}
\ENDVAR
\BEGIN
\STATE{res \recoit{} 1}
\STATE{k \recoit{} n}
\WHILE{k>0}
\STATE{k \recoit{} k-1}
\STATE{res \recoit{} a*res}
\ENDWHILE
\RETURN{res}
\END 
\end{algo}
\end{frame}


\begin{frame}[fragile]

\footnotesize

\begin{lstlisting}[caption={}]
PROGRAM Puissance_tq;
VAR a:INTEGER; n:INTEGER;

FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
VAR res:INTEGER; k:INTEGER;
 BEGIN
  res:=1;
  k:=n;
  WHILE k>0  DO
    BEGIN
    k:=k-1;
    res:=res*a;
    END;
  Puiss:=res;
 END;

BEGIN {programme principal habituel}
END.                  
\end{lstlisting}

\end{frame}

\normalsize

\subsection{Exponentiation logarithmique}

\begin{frame}
Le principe est simple:

\[
\left\{
\begin{array}{lcll}
a^0&=&1&\\
a^n&=&\left(a^2\right)^{\frac{n}{2}}&,\text{si  }  n  \text{  est  pair
  et }n>0\\
a^n&=&a\times\left(a^2\right)^{\frac{n-1}{2}}&,\text{si  }  n  \text{  est  impair}
\end{array}
\right.
\]


Écrivez  un  algorithme  utilisant  ces relations  de  récurrence.  Qu'y
gagne-t-on?

\end{frame}


\begin{frame}[fragile]
\begin{algo}
\FUNC{puissance\_log}{%
\pfarg{a,n}{entier}}{entier}
\BEGIN
\IF{n=0}
\STATE{1}
\ELSE
\IF{reste(n,2)=0}
\STATE{puissance\_log(a*a,n/2)}
\ELSE
\STATE{a*puissance(a*a,(n-1)/2)}
\ENDIF
\ENDIF
\END 
\end{algo}
\end{frame}



\begin{frame}[fragile] \frametitle{Avec Pascal}
  \begin{lstlisting}[caption={}]
PROGRAM puissance_log;
VAR a:INTEGER; n:INTEGER;
FUNCTION Puiss_log(a:INTEGER;n:INTEGER):INTEGER;
BEGIN
 IF n=0 THEN
     Puiss_log:=1
   ELSE IF n MOD 2 = 0 THEN
            Puiss_log:=Puiss_log(a*a,n DIV 2)
        ELSE  Puiss_log:=a*Puiss_log(a*a,(n-1) DIV 2);
END;
BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  WRITE(a,'^',n,' = ',Puiss_log(a,n));
  READLN;
END.                  
  \end{lstlisting}
\end{frame}


\begin{frame}[fragile] \frametitle{Avec CAML}
\caml
\begin{lstlisting}[caption={}]
# let rec puissance_log(a,n)=
      if n==0 then 1
      else if n mod 2 == 0 then puissance_log(a*a,n/2)
           else a*puissance_log(a*a,(n-1)/2);; 
\end{lstlisting}
\pause
Non, on ne rigole pas...
\Pasc
\end{frame}


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

% Les bases avec petits exos

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


\section{L'affectation}


\begin{frame}[fragile]
L'instruction représentée par:


\begin{algo}
\STATE{a \recoit{} 2}
\end{algo}

qui se lit \og a reçoit  2\fg{} réserve (affecte) une zone de la mémoire
de l'ordinateur qui portera l'étiquette a et qui contiendra 2.


\end{frame}



\begin{frame}[fragile]
  
Donnez le contenu de a et b après la suite d'affectations suivante:

\begin{algo}
\STATE{a \recoit{} 1}
\STATE{b \recoit{} 2}
\STATE{a \recoit{} a+b}
\STATE{b \recoit{} a-b}
\STATE{a \recoit{} a-b}
\end{algo}

\end{frame}



\begin{frame}[fragile]
  Que contiennent x et y à la fin de cet enchaînement d'affectations:
  \begin{algo}
\STATE{x \recoit{} -5}
\STATE{x \recoit{} carre(x)}
\STATE{y \recoit{} -x-3}
\STATE{z \recoit{} carre(-x-y)}
\STATE{x \recoit{} -carre(x-y)+z}
\STATE{y \recoit{} puissance(z,x)*y}
\STATE{y \recoit{} -(z+y)}
\STATE{y \recoit{} x+y-z}
\STATE{y \recoit{} x+z}
\STATE{x \recoit{} carre(y-z)}
\STATE{y \recoit{} x-y}
\STATE{x \recoit{} (x+y)/(x/10)}
\STATE{y \recoit{} ((x*z)/y)*9}
  \end{algo}
\end{frame}


\begin{frame}
Écrire un algorithme qui calcule très rapidement $x^{16}$.

\medskip

\pause

\begin{algo}
\FUNC{puissance\_16}{%
\pfarg{x}{entier}}{entier}
\VAR
\DECLVAR{res}{entier}
\ENDVAR
\BEGIN
\STATE{res \recoit{} x}
\STATE{res \recoit{} res*res}
\STATE{res \recoit{} res*res}
\STATE{res \recoit{} res*res}
\STATE{res \recoit{} res*res}
\RETURN{res}
\END 
\end{algo}
\end{frame}



\begin{frame}
Déterminez un algorithme qui reçoit  un nombre entier de secondes et qui
renvoie quatre  entiers correspondant à sa conversion  en jours, heures,
minutes et  secondes. On pourra  utiliser une fonction \og  quo\fg{} qui
renvoie le quotient entier de la division de deux entiers.
\end{frame}

\begin{frame}[fragile]
  \begin{algo}
\FUNC{conversion\_sec}{%
\pfarg{x}{entier}}{liste de quatre entiers}
\VAR
\DECLVAR{j,h,m,s,temps}{entier}
\ENDVAR
\BEGIN
\STATE{temps \recoit{} x}
\STATE{j \recoit{} quo(temps,24*60*60)}
\STATE{temps \recoit{} temps-j*(24*60*60)}
\STATE{h \recoit{} quo(temps,60*60)}
\STATE{temps \recoit{} temps-h*(60*60)}
\STATE{m \recoit{} quo(temps,60)}
\STATE{temps \recoit{} temps -m*60}
\STATE{s \recoit{} temps}
\RETURN{j,h,m,s}
\END    
  \end{algo}
\end{frame}


\begin{frame}[fragile] \frametitle{En Pascal}
  \begin{lstlisting}[caption={}]
PROGRAM conversion_sec;
VAR x,temps,h,j,m,s:INTEGER;
BEGIN
WRITE('Entrez le temps en secondes :');
READLN(x);
temps:=x;
j:=temps DIV (24*60*60);
temps:=temps-(j*24*60*60);
h:=temps DIV (60*60);
temps:=temps-(h*60*60);
m:=temps DIV 60;
temps:=temps-(m*60);
s:=temps;
WRITELN(x,' secondes = ',j,' jours, ',h,' heures, ',m,' minutes et ',s,'secondes');
READLN;
END.  
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile] \frametitle{Réponse de Pascal}
{\footnotesize
  \begin{boxedverbatim}
  Entrez le temps en secondes :360254758
  360254758 secondes = 4169 jours, 14 heures, 45 minutes et 58secondes
  \end{boxedverbatim}
}
\end{frame}


\section{Le type booléen}


\begin{frame}
Avant  d'étudier  les  structures  conditionnelles, il  nous  faut  nous
habituer aux tests, aux booléens et  à leurs opérateurs, qui ne sont pas
d'un usage aussi naturel que les types réels et entiers.
\end{frame}

\begin{frame}[fragile]
  \begin{itemize}
    \item Une variable de type booléen n'a que deux valeurs possibles: VRAI ou
FAUX.
\item Ces  booléens sont en  particulier les valeurs retournées  par les
  opérateurs  de comparaison:  \verb+=+, \verb+<+,  \verb+<=+, \verb+>+,
  \verb+>=+, \verb+<>+.
\item  Ils   ont  en   général  4  opérateurs:   \verb+ET+,  \verb+OU+,
  \verb+OUEX+, \verb+NON+.
  \end{itemize}
\end{frame}


\begin{frame}[fragile]
Par exemple, quelle sera la réponse à:

\begin{itemize}
\item $3>2$ ET $2>2$?
\item $3>2$ ET $2 \geqslant 2$?
\item $3>2$ OU $2>2$?
\item $3>2$ OU $2 \geqslant 2$?
\item $3>2$ OUEX $2 \geqslant 2$?
\item $3>2$ OUEX $2>2$?
\item NON $2>2$?
\item NON $3>2$?
\end{itemize}
\end{frame}



\begin{frame}
Par  exemple,  sans  utiliser  de structure  conditionnelle,
écrivez un algorithme, qui, lorsqu'on lui fournit les trois coefficients
d'un trinôme du second degré, renvoie VRAI si ce trinôme admet 2 racines
distinctes et FAUX sinon.
\end{frame}






\begin{frame}[fragile]
\FUNC{deux\_racines}{%
\pfarg{a,b,c}{réels}}{booléen}
\VAR
\DECLVAR{résultat}{booléen}
\DECLVAR{delta}{réel}
\ENDVAR
\BEGIN
\STATE{delta \recoit{} b*b-4*a*c}
\STATE{résultat \recoit{} delta>0}
\RETURN{résultat}
\END    
\end{frame}




\begin{frame}
  Donnez  un
algorithme qui,  deux nombres étant  donnés, affiche VRAI s'ils  sont de
même signe et FAUX sinon. 
\end{frame}

\begin{frame}[fragile]
\FUNC{meme\_signe}{%
\pfarg{x,y}{réels}}{booléen}
\VAR
\DECLVAR{résultat}{booléen}
\ENDVAR
\BEGIN
\STATE{résultat \recoit{} ((x<0) ET (y<0)) OU ((x>0) ET (y>0))}
\RETURN{résultat}
\END    
\end{frame}

\begin{frame}[fragile] \frametitle{En Pascal}
  \begin{lstlisting}[caption={}]
 PROGRAM meme_signe;
 VAR
   x,y:REAL;
   resultat:BOOLEAN;

 BEGIN
   READLN(x,y);
   resultat:= ((x<0) AND (y<0)) OR ((x>0) AND (y>0));
   WRITELN(resultat);
   READLN;
 END.              
  \end{lstlisting}
\end{frame}



\caml

\begin{frame}[fragile] \frametitle{En Caml}

Caml est un langage plus moderne...

  \begin{lstlisting}[caption={}]
#  let meme_signe(x,y)=
      ((x<0.) && (y<0.)) || ((x>0.) && (y>0.));;
  \end{lstlisting}

Il nous répond:

\begin{lstlisting}[caption={}]
#  let meme_signe(x,y)=
      ((x<0.) && (y<0.)) || ((x>0.) && (y>0.));;
  val meme_signe : float * float -> bool = <fun>

# meme_signe(5.,-3.);;
- : bool = false
\end{lstlisting}



\end{frame}


\Pasc



\section{Les structures conditionnelles}


\begin{frame}
C'est le fameux SI...ALORS...SINON...
\end{frame}


\begin{frame}[fragile]
%Voici un bel algorithme:

\begin{algo}
\FUNC{zorg}{%
\pfarg{a,b,c}{entier}}{caractère}
\BEGIN
\IF{a<>b}
\IF{a+1=b}
\RETURN{'aarrgh'}
\ELSE
\IF{c<>7}
\RETURN{'glurp'}
\ELSE
\RETURN{'pas glop'}
\ENDIF
\ENDIF
\ELSE
\RETURN{'eviv bulgroz'}
\END 
\end{algo}


\end{frame}






\begin{frame}[fragile]
Que répond 
\begin{itemize}
  \item \verb+zorg(4,5,7)+?
\item \verb+zorg(4,5,8)+?
\item \verb+zorg(4,6,7)+?
\end{itemize}


 

\end{frame}



\begin{frame}
Créez un algorithme qui à une note de Bac renvoie la mention correspondante.
\end{frame}




\begin{frame}
Nous sommes à présent prêts pour aborder la récursion...
\end{frame}


\section{Récursion}

\end{document}

%%% Local Variables: 
%%% TeX-master: t
%%% End: 
