%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x]{preambuleTrm}



\usepackage{iwona}


\mode<presentation>
{
  %\usetheme{Bergen}%Montpellier
  % or ...Frankfurt, 
  \usetheme[secheader]{Madrid}

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
  \useoutertheme{progressbar}
  %\useinnertheme{progressbar}
  \progressbaroptions{% titlepage=normal,
    imagename=/home/moi/Photos/Maths/typewriter
}
}

\usepackage{elephantbird}


%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap,shadows,patterns}
%\newcommand{\myunit}{1.1cm}
%\usepackage{tkz-graph}
%\usepackage{circuitikz}
\usepackage{tikz-qtree}
\usepackage{tikz-uml}
\usepackage{tikz-cd}
\hypersetup{pdfpagemode=FullScreen}

\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

\usepackage{scalefnt}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




\setcounter{tocdepth}{2} %\setcounter{page}{0}


\newcommand{\triangleup}{\Delta}













\begin{document}


\title[]% (optional, use only with long paper titles)
{Structures linéaires}

\subtitle{Informatique pour tou(te)s - semaines 37 à 40}

\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{Lycée Clemenceau - MP / MP$^{\star}$}% (optional, but mostly needed)

%\logo{\includegraphics[width=0.1\textwidth]{logo_iut}}

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

\date[] % (optional, should be abbreviation of conference name)
{septembre 2015}
% - 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[]
% {\scriptsize
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\tiny
% \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{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
%\ThisCenterWallPaper{1}{logoiremBigInv}
 \Large \titlepage 
\end{frame}

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

 
%  \end{frame}



\section{Mémoire}

\begin{frame}
  Hiérarchie de la mémoire
\end{frame}


\begin{frame}
  Tableau (array, vector) \pause statique
\end{frame}


\begin{frame}
  Liste chaînée \pause dynamique \pause pointeur
\end{frame}

\begin{frame}
  Liste Python...\pause un peu des deux.

\end{frame}


\begin{frame}
Python...\pause c'est du C!

\end{frame}

\begin{frame}[fragile]
  \begin{ccode}
typedef struct {
        PyObject_VAR_HEAD
        /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
        PyObject **ob_item;
    
        /* ob_item contains space for 'allocated' elements.  The number
         * currently in use is ob_size.
         * Invariants:
         *     0 <= ob_size <= allocated
         *     len(list) == ob_size
         *     ob_item == NULL implies ob_size == allocated == 0
         * list.sort() temporarily sets allocated to -1 to detect mutations.
         *
         * Items must normally not be NULL, except during construction when
         * the list is not yet visible outside the function that builds it.
         */
        Py_ssize_t allocated;
    } PyListObject;    
  \end{ccode}
\end{frame}


\begin{frame}[fragile]\frametitle{Obtenir un élément}
  

  \begin{ccode}
static PyObject *
list_item(PyListObject *a, int i)
{
	if (i < 0 || i >= a->ob_size) {
		if (indexerr == NULL)
			indexerr = PyString_FromString(
				"list index out of range");
		PyErr_SetObject(PyExc_IndexError, indexerr);
		return NULL;
	}
	Py_INCREF(a->ob_item[i]);
	return a->ob_item[i];
}
    
  \end{ccode}
\end{frame}



\begin{frame}[fragile]\frametitle{Test d'appartenance}
  \begin{ccode}
static int
list_contains(PyListObject *a, PyObject *el)
{
	int i;

	for (i = 0; i < a->ob_size; ++i) {
		int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
						   Py_EQ);
		if (cmp > 0)
			return 1;
		else if (cmp < 0)
			return -1;
	}
	return 0;
}    
  \end{ccode}
\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{argh}
\end{center}
%\end{figure}
  
\end{frame}






\begin{frame}
  Linguiste $\neq$ locuteur natif

\pause

Objectif $\neq$ connaître Python
\end{frame}



\begin{frame}
  Abstraction

\pause

Bug de l'an 2000

\pause

Préparer celui de l'an \numprint{10000}
\end{frame}


\begin{frame}
  \frametitle{Extrait de l'épreuve X-ENS (MP option SI et PC) 2015}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{CaptureX}
\end{center}
%\end{figure}
  
\end{frame}




\section{Types abstraits de données}


\begin{frame}
  \begin{itemize}
  \item  Séparation représentation / utilisation
  \item  Un type  : ensemble  de valeurs  et ensemble  d'opérations pour  créer,
    modifier, manipuler ces valeurs \pause (magma, monoïde,...)\pause
  \item Barrière d'abstraction
  \item  Séparer   la  programmation  de   la  représentation  du  type   et  la
    programmation des algorithmes qui utilisent ce type
  \end{itemize}

 \end{frame}


\subsection{Les Booléens}

 \begin{frame}
   \frametitle{Les Booléens}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{boolean}
\end{center}
%\end{figure}
   
 \end{frame}





 \begin{frame}\frametitle{Une spécification des booléens}
   \begin{itemize}
   \item \textbf{Sorte:} Boul
     \item \textbf{Opérations:}
       \begin{itemize}
       \item Vrai :: Boul \pause \{ constructeur \}\pause
       \item Faux :: Boul \pause \{ constructeur \}\pause
       \item $¬$ :: Boul $⟶$ Boul
       \item $∧$ :: Boul Boul $⟶$ Boul
       \end{itemize}
     \item \textbf{Axiomes}
       \begin{itemize}
       \item \textbf{Variable:} b :: Boul
       \item \textbf{Équations:}
       \begin{itemize}
       \item $¬$ Vrai = Faux
       \item $¬$ Faux = Vrai
       \item Vrai $∧$ b = b
       \item Faux $∧$ b = Faux
       \end{itemize}
     \end{itemize}
   \end{itemize}
 \end{frame}




 \begin{frame}
   Et les autres opérations? ($∨$, $⟹$, $⟺$ et $⊕$)

\pause

\begin{itemize}
\item $b ∨ c = ¬((¬b) ∧ (¬c))$
\item $b ⟹ c = (¬b) ∨ c$
\item $b ⟺ c = (b ⟹ c) ∧ (c ⟹ b)$
\item $b ⊕ c = ¬ (b ⟺ c)$
\end{itemize}
\end{frame}



\subsection{Les listes chaînées}

\begin{frame}
  \frametitle{Une spécification des listes chaînées}
  

\begin{definition}[Liste]
Une liste sur un ensemble E est soit le \textit{Vide}
soit un élément de E suivi d'une liste.
\end{definition}

\pause

(\textit{Comparez avec  cette définition d'un  mot: c'est le  mot vide
  ou une lettre suivie d'un mot}...).


\end{frame}

\begin{frame}[fragile]

\begin{center}
\begin{tikzpicture}[sibling distance=50pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.$\bullet$ 0
         [.$\bullet$ 1
             [.$\bullet$ 2
                 [.$\bullet$ 3
                    [.$\bullet$ 4
                    Vide ] ] ] ] ];
\end{tikzpicture}
\end{center}
  
\end{frame}










\begin{frame}
  
  \begin{itemize}
  \item Il nous faut disposer d'une liste vide.  
\item Il faut pouvoir  ajouter un
élément en tête
\item sélectionner la tête
\item sélectionner la liste privée de la tête
\item tester si une liste est vide
\item on ne pourra pas demander la tête ou la queue d'une liste vide. 
 \item une liste ayant une tête n'est pas vide 
\item si on a ajouté  un élément à une liste, sa tête est  cet élément et la
queue est la liste initiale
\end{itemize}
\end{frame}



\begin{frame}
  \begin{itemize}
  \item \textbf{Sorte:} Liste (liste d'objets de sorte E)
\item \textbf{Opérations:}
\begin{itemize}
\item vide :: Liste \pause (constructeur) \pause
\item liste :: E Liste $→$ Liste \pause (constructeur) \pause
\item tête :: Liste $→$ E \pause (sélecteur) \pause
\item queue :: Liste $→$ Liste \pause (sélecteur) \pause
\item est\_vide :: Liste $→$ Bool \pause (testeur) \pause
\end{itemize}
\item \textbf{Préconditions:}
\begin{itemize}
\item \textbf{pré} tête( xs ) = $ \neg$ est\_vide(xs)
\item \textbf{pré} queue( xs ) = $ \neg$ est\_vide(xs)
\end{itemize}
\item \textbf{Axiomes:}
\begin{itemize}
\item est\_vide( vide ) = Vrai
\item est\_vide( liste(x, xs) ) = Faux
\item tête( liste(x, xs) ) = x
\item queue( liste(x, xs) ) = xs
\end{itemize}
\end{itemize}
\end{frame}



\begin{frame}[fragile]
  \frametitle{Un premier essai sur Python avec des tuples}
\begin{pythoncode}
vide = None

def liste( x, xs ) :
    return ( x, xs )

def est_vide( xs ) :
    return xs == None # ou pythonerie : return not xs

def tete( xs ) :
    if est_vide( xs ) :
        raise ValueError( "Une liste vide n'a pas de tête" )
    ( tete, _ ) = xs
    return tete       # ou pythonerie : xs[0]

def queue( xs ) :
    if est_vide( xs ) :
        raise ValueError( "Une liste vide n'a pas de queue" )
    ( _, queue ) = xs
    return queue      # ou pythonerie : xs[1:]
\end{pythoncode}  
\end{frame}



\begin{frame}[fragile]
  \frametitle{Un deuxième essai sur Python avec des tableaux}
\begin{pythoncode}
vide = []

def liste( x, xs ) :
    return [x] + xs

def est_vide( xs ) :
    return xs == []

def tete( xs ) :
    return xs[0]

def queue( xs ) :
    return xs[1:]  
\end{pythoncode}
\end{frame}



\subsection{De l'autre côté de la barrière d'abstraction}


\begin{frame}
  \frametitle{Longueur d'une liste}
  \begin{exercice}
En  utilisant  uniquement  \mintinline{python}{liste,  est_vide,  tete,  queue},
quelque   soit  le   moteur  qui   les  implémente,   déterminez  une   fonction
\mintinline{python}{longueur(xs)}   qui  calcule   la  longueur   de  la   liste
\mintinline{python}{xs}  donnée en argument. 
  \end{exercice}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Longueur d'une liste}
\begin{pythoncode}
from liste_implem_list import *
#from liste_implem_tuple import *

####################################################
#                                                  #
#  B a r r i è r e    d ' a b s t r a c t i o n    #
#                                                  #
####################################################

l1 = liste(1, liste(2, liste(3, liste(4, vide))))

def longueur( xs ) :
    nb  = 0
    els = xs 
    while not est_vide( els ) :
        nb += 1
        els = queue( els )
    return nb  
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Longueur d'une liste}
\begin{pythoncode}
from liste_implem_list import *
#from liste_implem_tuple import *

####################################################
#                                                  #
#  B a r r i è r e    d ' a b s t r a c t i o n    #
#                                                  #
####################################################

l1 = liste(1, liste(2, liste(3, liste(4, vide))))


def longueur( xs ) :
    if est_vide( xs ) :
        return 0
    return 1 + longueur( queue( xs ) )
\end{pythoncode}

\end{frame}
 

\begin{frame}
  Bien sûr on peut faire bien mieux  avec un peu de programmation orientée objet
  mais cela dépasse le niveau de notre programme...
\end{frame}



\begin{frame}[fragile]\frametitle{Avec OCaml}
  \begin{ocamlcode}
type 'a liste =
  |Vide
  |L of ('a * 'a liste);;

let ajoute el els = L(el,els);;

exception ListeVide;;
  
let tete = function
  |Vide -> raise ListeVide
  |L(el,els) -> el;;

let queue = function
  |Vide -> raise ListeVide
  |L(el,els) -> els;;    
  \end{ocamlcode}
\end{frame}



\section{Exercices}


\begin{frame}
  Il s'agit  d'implémenter du  bon côté  de la  barrière les  fonctions définies
  ainsi dans la documentation d'un autre langage de programmation:
\end{frame}

\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
last :: [a] -> a	 
Extract the last element of a list      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
init :: [a] -> [a]	 
Return all the elements of a list except the last one      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
Append two lists, i.e.,
 [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
 [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]   
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
reverse :: [a] -> [a]	
reverse xs returns the elements of xs in reverse order.      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
sum :: Num a => [a] -> a	
The sum function computes the sum of a finite list of numbers.

product :: Num a => [a] -> a	
The product function computes the product of a finite list of numbers.      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
any :: (a -> Bool) -> [a] -> Bool	
Applied to a predicate and a list, any determines if any element of the list satisfies the predicate.

all :: (a -> Bool) -> [a] -> Bool	
Applied to a predicate and a list, all determines if all elements of the list satisfy the predicate.      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
maximum :: Ord a => [a] -> a	
maximum returns the maximum value from a list, which must be non-empty, finite, and of an ordered type.

minimum :: Ord a => [a] -> a	
minimum returns the minimum value from a list, which must be non-empty, finite, and of an ordered type. 
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
 takeWhile :: (a -> Bool) -> [a] -> [a]	
takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p:
 takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
 takeWhile (< 9) [1,2,3] == [1,2,3]
 takeWhile (< 0) [1,2,3] == []     
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
elem :: Eq a => a -> [a] -> Bool	
elem is the list membership predicate      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
find :: (a -> Bool) -> [a] -> Maybe a	
The find function takes a predicate and a list and returns the first element in the list matching the predicate, or Nothing if there is no such element.      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
filter :: (a -> Bool) -> [a] -> [a]	
filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,
 filter p xs = [ x | x <- xs, p x]      
    \end{haskellcode}
  \end{exercice}
\end{frame}



\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
partition :: (a -> Bool) -> [a] -> ([a], [a])	
The partition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively      
    \end{haskellcode}
  \end{exercice}
\end{frame}





\begin{frame}[fragile]
  \begin{exercice}
    \begin{haskellcode}
zip :: [a] -> [b] -> [(a, b)]	
zip takes two lists and returns a list of corresponding pairs. If one input list is short, excess elements of the longer list are discarded.       
    \end{haskellcode}
  \end{exercice}
\end{frame}





\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
