\chapterimage{lukasiewicz}
\chaptertext{
En   1920,   le   mathématicien-logicien-philosophe  polonais   Jan   \textsc{\L
  ukasiewicz} (1878-1956) invente  la  notation  préfixée   alors  qu'il  est  ministre  de
l'éducation (on a le droit de rêver...).

35 ans  plus tard, le philosophe  et informaticien (!) australien  (!!!) Charles
\textsc{Hamblin} (1922 - 1985) s'en inspire.

Il a en effet en sa possession  l'un des deux ordinateurs présents à l'époque en
Australie. Il  se rend compte  que la saisie de  calculs avec les  opérateurs en
notation  infixée  induit   de  nombreuses  erreurs  de  saisie   par  oubli  de
parenthèses.  Il pense  aussi  à la  (très petite)  mémoire  des ordinateurs  de
l'époque.

% \end{minipage}
% \setindent{0cm}

%\piccaption{Charles \textsc{Hamblin} \\ (1922-1985)}
%\parpic[r]{ \includegraphics[width=2.5cm]{hamblin}}



Il trouve alors  son inspiration dans le travail de  \textsc{\L ukasiewicz} pour
éviter les parenthèses et il
 pense à mettre les opérateurs en position préfixée:
ainsi  il   introduit  la   notion  de   \textit{pile}  (ou   \textit{stack}  ou
\textsc{Lifo}) qui économise le nombre d'adresses mémoire nécessaires.


C'est  la  naissance de  la  Notation  Polonaise  Inversée  (NPI ou  RPN).  Elle
économise également la taille des composants électroniques des portes logiques.

Son seul inconvénient:  les mauvaises habitudes prises  d'utiliser des notations
infixées...




Un autre grand avantage: il faut comprendre le calcul avant de l'exécuter :-)}

\pythonc
\chapter{Structures de données linéaires}
\section{Tableaux}

Jusqu'à maintenant,  nous avions à  disposition une seule  structure de
données: le tableau.

En Python,  les tableaux s'appellent malheureusement  des listes qu'il
ne faut pas  confondre avec la structure  appelée habituellement liste
en informatique!(Ah....Python...)



Commentez les résultats qui suivent:

%\begin{multicols}{2}
\begin{lstlisting}
def m0():
    return sum([i + 3 for i in range(1000)])

def m1():
    return np.sum(np.arange(1000) + 3)

def m2():
    return np.sum(map(lambda x: x + 3,range(1000)))
\end{lstlisting}

\begin{lstlisting}
In [142]: %timeit m0()
10000 loops, best of 3: 63 μs per loop

In [143]: %timeit m1()
100000 loops, best of 3: 17 μs per loop

In [144]: %timeit m2()
100000 loops, best of 3: 12.8 μs per loop
\end{lstlisting}
%\end{multicols}


\section{Création de listes linéaires non bornées}

\subsection{Version 1}

On voudrait construire  un objet qui ressemble à un  tableau mais dont
on n'aurait pas à donner la taille a priori. Il doit ressembler à un ensemble d'éléments de  \textit{même type} placés dans un \textit{ordre
  donné}.


Par exemple, on  sait calculer la moyenne de trois  notes mais comment
faire pour calculer la moyenne d'un nombre quelconque de notes?

On pourrait donner la définition mathématique suivante:


\begin{definition}[Liste linéaire]
Une  liste   linéaire  sur   un  ensemble  E   est  une   suite  finie
$x_0,x_1,...,x_n$ d'éléments de E.
\end{definition}

Cela n'est cependant pas suffisant pour manipuler ce genre d'objet.

On pourrait aussi donner cette définition:

\begin{definition}[Liste linéaire: version récursive]
Une liste linéaire sur un ensemble E est soit le \textit{Vide}
soit un élémentde E suivi d'une liste.
\end{definition}

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

Cette  notion de  liste est  si importante  en informatique  qu'un des
langages   les  plus   marquants  de   son  histoire   s'appelle  LISP
(\textit{LISt Processor} cf \cite{brygoo2004programmation}).

Nous allons en donner une \textit{spécification} beaucoup plus riche.

D'abord, on peut se représenter nos listes de manière plus précise. La
liste $ (0,1,2,3,4)$ ressemble en fait à ça:

\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}



Il nous  faut disposer d'une  liste vide.  Il faut pouvoir  ajouter un
élément en tête, sélectionner la tête, sélectionner la liste privée de
la tête, tester si une liste est vide, calculer sa longueur.


On ne pourra pas demander la tête ou la queue d'une liste vide. 

La longueur de la liste vide doit être nulle. Une liste ayant une tête
n'est pas  vide. La  longueur d'une  liste à laquelle  on a  ajouté un
élément en tête est incrémentée d'une unité. 

Si on a ajouté  un élément à une liste, sa tête est  cet élément et la
queue est la liste initiale.

On peut résumer ces spécifications dans  un langage un peu plus formel
(cf \cite{dufourd1995specifications}).

\begin{itemize}
\item \textbf{Sorte:}

Liste (liste d'objets de sorte E)

\item \textbf{Opérations:}

Vide :: Liste

ajoute :: Liste E -> Liste

tête :: Liste -> E

queue :: Liste -> Liste

estVide :: Liste -> Bool

taille :: Liste -> Nat

\item \textbf{Préconditions:}

\textbf{pré} tête(liste) = $ \neg$ estVide(liste)

\textbf{pré} queue(liste) = $ \neg$ estVide(liste)


\item \textbf{Axiomes:}

estVide(Vide) = Vrai

taille(Vide) = 0

estVide(ajoute(x,l)) = Faux

taille(ajoute(x,l)) = taille(l) + 1

tête(ajoute(x,l)) = x

queue(ajoute(x,l)) = l

\end{itemize}


Il ne reste plus qu'à traduire cela dans un langage de programmation.

Malheureusement, il va falloir le faire en Python ;-)


On peut construire une liste comme un couple en utilisant les n-uplets
de Python (ou \textit{tuple}).

\begin{lstlisting}
#! python3.4
#-*- coding: utf-8 -*-

###########################################################
#####
#####         IMPLÉMENTATION SPÉCIFIQUE (ICI AVEC TUPLES)
#####
###########################################################

vide = None

# testeur

def est_vide(lst):
    """
    teste si une liste est vide
    """
    return lst == vide

# sélecteurs

def tete(lst):
    """
    renvoie le premier élément d'une liste (sa tête)
    
    >>> tete((1,(2,(3,vide))))
    1
    """
    if est_vide(lst):
        raise ValueError("La liste vide n'a pas de tête") 
    else:
        return lst[0]

def queue(lst):
    """
    renvoie la liste privée de sa tête : c'est encore une liste
    
    >>> queue((1,(2,(3,vide))))
    (2, (3, vide))
    """
    if est_vide(lst):
        raise ValueError("La liste vide n'a pas de queue") 
    else:
        return lst[1]

# insertion
    
def insere(el,lst):
    """
    insere un élement en tête de liste
    
    >>> insere(12, (1,(2,(3,vide))))
    (12, (1, (2, (3, vide))))
    """
    return (el,lst)

#########################################################################
####
#### BARRIÈRE D'ABSTRACTION : NE DÉPEND PAS DE L'IMPLÉMENTATION DES LISTES
####
#########################################################################

def concat(lst1,lst2):
    """
    concatène deux listes

    >>> concat((0,(1,(2,(3,(4,None))))) ,(10,(11,(12,(13,(14,None))))) )
    (0, (1, (2, (3, (4, (10, (11, (12, (13, (14, None))))))))))
    """
    if est_vide(lst1):
        return lst2
    else:
        return insere(tete(lst1), concat(queue(lst1),lst2))

### Petits sucres pour faciliter l'écriture et la lecture

def print_liste(li):
    """
    joli affichage d'une liste :

    >>> print_liste(liste(1,liste(2,liste(3,vide))))
    '< 1 2 3 >'
    """
    lst = li
    c = '< '
    while lst != vide:
        c += repr(tete(lst)) + ' '
        lst = queue(lst)
    return c[:-1] + ' >'

def from_listp(lst_p):
    """
    Construit une liste à partir d'un iterable python
    
    >>> l = from_iter(range(10))
    >>> print_liste(l)
    '< 0 1 2 3 4 5 6 7 8 9 >'
    """
    l = vide
    for k in lst_p[::-1]:
        l = insere(k,l)
    return l
\end{lstlisting}



\begin{remarque}
\textbf{Dans ce cas}, pour être  plus efficace \textbf{sur Python} (on
divise par 3 le nombre d'appels), on
peut éviter de 
multiplier les appels aux fonctions intermédiaires:

\begin{lstlisting}
def applique(lst,f):
    if not lst:
        return None
    else:
        return (f(lst[0]),applique(lst[1],f))
\end{lstlisting}

\textbf{MAIS } on perd un peu le sens de la construction des listes qui est notre
propos  et surtout  la  \textit{barrière d'abstraction}  qui  nous permettra  de
conserver les  mêmes fonctions quelque  soit notre version  d'implémentation des
listes.
\end{remarque}



Certaines fonctions  sont commentées  car elles fonctionnent  toutes de  la même
manière.

Nous allons les unifier dans la \vref{exo::monoide}.


\subsection{Version 2}


Voici une deuxième méthode qui  construit une liste chaînée sous forme
d'une fonction:

\begin{lstlisting}
def cons(a, b):
    """
    construit une fonction qui renvoie a si son argument vaut '1' et b sinon
    cons :: (type1, type2) -> string -> type1
                           -> type3 -> type2 
    C'est une manière de construire une sorte de tuple

    >>> cons('bon','jour')('1')
    'bon'
    >>> cons(23,45)('1')
    23
    >>> cons(23,45)('Hasta la vista baby')
    45
    """
    return lambda x : a if x == '1' else b

def prem(consab):
    """
    construit la fonction qui retourne le premier élément d'une paire fonctionnelle

    >>> prem(cons('bon','jour'))
    'bon'
    """
    return consab('1')

def deuz(consab):
    """
    construit la fonction qui retourne le 2e élément d'une paire fonctionnelle

    >>> deuz(cons('bon','jour'))
    'jour'
    """
    return consab('2')

###########################################################
#####
##### IMPLÉMENTATION SPÉCIFIQUE (ICI AVEC LA FONCTION CONS)
#####
###########################################################


vide = lambda : "n'importe quoi"
"""vide est une fonction sans argument"""

def liste(element, list):
    """
    Une liste est une FONCTION construite à partir de cons

    >>> l = liste(1,liste(2,liste(3,vide)))
    """
    return cons(element, list)

def est_vide(lst):
    return lst == vide

def tete(lst):
    if est_vide(lst):
        raise ValueError("La liste vide n'a pas de tête") 
    else:
        return prem(lst)

def queue(lst):
    if est_vide(lst):
        raise ValueError("La liste vide n'a pas de queue") 
    else:
        return deuz(lst)

def insere(el,lst):
    return liste(el,lst)
\end{lstlisting}

\subsection{Version 3}

Je  vous livre  une  autre implémentation  qui va  nous  initier à  la
programmation objet:

\begin{lstlisting}
class Liste(object):
    def __init__(self, tete , queue = Vide):
        """
        Une liste est définie par:
        - son premier élément 
        - la liste des autres éléments.
        In [1]: l = Liste(1,Liste(2,Liste(3,Vide)))
        La liste doit avoir des éléments de même type
        """
        self.__tete  = tete
        self.__queue = queue
        if (self.__tete is None):
            raise SyntaxError("la liste doit avoir la forme Liste(el, Liste) ou être Vide")
        if not ((self is Vide)
                or (queue is Vide)
                or isinstance(tete, type(queue.__tete))):
            raise TypeError("La liste doit être de type homogène")

    def estVide(self):
        return (self is Vide)

    def queue(self):
        return self.__queue
    
    def tete(self):
        return self.__tete

    def insere(self,x):
        return Liste(x,self)

    def __str__(self):
        lst = self
        c = '< '
        while lst != Vide:
            c += repr(lst.__tete) + ' '
            lst = lst.__queue
        return c[:-1] + ' >'
\end{lstlisting}

Il faut également traiter le cas vide:

\begin{lstlisting}
class Vide(object):
    def __str__():
        return ""
    def tete():
        raise TypeError("La liste vide n'a pas de tête")
    def queue():
        raise TypeError("La liste vide n'a pas de queue")
    def insere(x):
        return Liste(x,Vide)
    def estVide():
        return True
\end{lstlisting}

Ouch! Il y a du boulot...

Pour les heureux inscrits en option  Info qui utilisent Ocaml, on peut
comparer avec ce que 
cela pourrait donner dans ce beau langage:

\caml

\begin{lstlisting}
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;;

let rec taille = function
  |Vide -> 0
  |L(el,els) -> 1 + (taille l);;
\end{lstlisting}

et c'est tout.
Par exemple:

\begin{lstlisting}
utop[11]> let l = L(1,Vide);;
val l : int liste = L (1, Vide)
utop[12]> let l1 = ajoute 2 l;;
val l1 : int liste = L (2, L (1, Vide))
utop[13]> taille l1;;
- : int = 2
utop[14]> tete Vide;;
Exception: ListeVide.
\end{lstlisting}

Mais revenons  à notre serpent... Il  cache dans son ventre  des notions
qui vont être abordées cette année. Par exemple:

\begin{itemize}
\item un style de programmation orienté objet;
\item de la récursion;
\item une étude de la complexité des fonctions que l'on va créer.
\end{itemize}

(\textit{Les  commentaires du  prof au  tableau viennent  ici éclairer
  l'étudiant perplexe.})

\pythonc

\subsection{Version 4}


\begin{lstlisting}
from copy import copy

class Noeud(object):
    """Un noeud a une valeur et pointe vers un autre noeud"""

    def __init__(self,elt = None, sui = None):
        self.__valeur  = elt
        self.__suivant = sui

    def get_valeur(self):
        """accesseur"""
        return self.__valeur
    
    def set_valeur(self,v):
        """mutateur"""
        self.__valeur = v

    def get_suivant(self):
        return self.__suivant

    def set_suivant(self,s):
        self.__suivant = s

    def  __str__(self):
        """ on affiche seulement la valeur du noeud """
        return str(self.get_valeur())
  
class Liste(object):
    
    def __init__(self):
        self.__tete = None
        
    def est_vide(self):
        return self.__tete is None

    def insere(self,elt):
        """La tête a pour valeur la valeur entrée et pointe vers l'ancienne tête"""
        n = Noeud(elt)
        n.set_suivant(self.__tete)
        self.__tete = n

    def val_tete(self):
        return self.__tete.get_valeur()
        
    def decapite(self):
        """On enlève la tête de la liste"""
        if self.__tete is None:
            raise TypeError("La liste vide n'a pas de queue")
        else:
            t = self.__tete
            self.__tete = t.get_suivant()
            t = None
            
    def queue(self):
        """on renvoie la queue sans modifier la liste"""
        l = copy(self)
        l.decapite()
        return l

    def __str__(self):
        s = ""
        t = self.__tete
        while not (t is None):
            s = s + str(t) + (', ' if t.get_suivant() is not None else '')
            t = t.get_suivant()
        return "<" + s + ">"
\end{lstlisting}


\section{NPI}

\subsection{Arbre de calcul}

Le rôle des parenthèses est le plus souvent primordial  sur machine:



\begin{lstlisting}
In [54]: 5 + 4 * 3
Out[54]: 17
\end{lstlisting}

et ce quelque soit le langage car des règles de priorité ont été établies.


Sinon, des parenthèses auraient dû être mises:

\begin{lstlisting}
In [55]: 9 / 2 + (-3) * 4 - (-5)
Out[55]: -2.5

In [56]: 9 / ((2 + (-3)) * (4 - (-5)))
Out[56]: -1.0
\end{lstlisting}


Or dans  un calcul plus compliqué,  ne pas se soucier  des parenthèses
peut entraîner de mauvaises surprises.

Il est sûrement plus clair de visualiser le calcul à l'aide d'un arbre

{\small 
\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
       child{node{$+$}
       child{node[fill=white]{$2$}}
       child{node{$-$}
            child{node[fill=white]{$3$}}}
       }
       child{node{$-$}
       child{node[fill=white]{$4$}}
       child{node{$-$}
            child{node[fill=white]{$5$}}}
       }
};
\end{tikzpicture}
\end{center}

}

L'usage  du $-$  est  ici ambigu:  cet opérateur  est  parfois binaire,  parfois
unaire.  Pour éviter  ce problème,  on peut  par exemple  utiliser des  symboles
différents:


{\small 

\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
       child{node{$+$}
       child{node[fill=white]{$2$}}
       child{node{$\lnot$}
            child{node[fill=white]{$3$}}}
       }
       child{node{$-$}
       child{node[fill=white]{$4$}}
       child{node{$\lnot$}
            child{node[fill=white]{$5$}}}
       }
};
\end{tikzpicture}
\end{center}

}

On réduit alors l'arbre en remontant des feuilles vers la racine:




{\small 

\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\times$}
      child{node{$\lnot$}
        child{node[fill=white]{$1$}}
      }
      child{node[fill=white]{$9$}
      }
    };
\end{tikzpicture}
\end{center}
}

puis


{\small 

\begin{center}
\begin{tikzpicture}
[edge from parent fork down,
every node/.style={fill=blue!30,rounded corners},
edge from parent/.style={blue,thick,draw},level 1/.style={sibling distance=4.5cm},
level 2/.style={sibling distance=2.5cm},
level 3/.style={sibling distance=1.4cm}]
\node{$/$}
    child{node[fill=white]{$9$}}
    child{node{$\lnot$}
      child{node[fill=white]{$9$}}
    };
\end{tikzpicture}
\end{center}
}


et finalement $\lnot 1$.


À  partir  de  l'arbre,  on   obtient  donc  une  \textit{séquence}  de  lecture
\textit{infixée} en \textit{profondeur}:

$$
9/((2+\lnot 3)\times (4- \lnot 5))
$$

L'emploi  des  parenthèses  agit  comme une  sorte  de  \textit{retardateur}  de
l'évaluation.


Comment une machine  évalue une telle expression? C'est en  fait assez compliqué
car il  faut disposer  de règles de  priorité, d'associativité,  d'une grammaire
qui procède donc\textit{ récursivement}...

Un autre  moyen est  de convertir  cette expression  en notation  post-fixée qui
utilise une \textit{pile}.


\subsection{Pile: découverte}


Une pile  (en anglais  \textit{stack}) est une  structure de  données permettant
l'insertion d'un élément et la suppression du dernier élément inséré.

L'acronyme anglais associé est LIFO (\textit{Last In First Out}).

Alan   \textsc{Turing}   proposa   dès   1945  les   termes   \textit{bury}   et
\textit{unbury} pour désigner les deux méthodes basiques de traitement des piles.

On utilise en français \textit{empiler} et \textit{dépiler} alors que les termes
anglais actuellement utilisés sont \textit{push} et \textit{pop}.

Imaginez une partie de cartes qui nécessite  une pioche. La seule carte qui nous
intéresse est celle du dessus. Piocher une  carte consiste à retirer la carte du
dessus  et  à la  lire  (dépiler)  ou rajouter  une  carte  \textit{sur} le  tas
(empiler).
 Toute information supplémentaire est superflue.

De nombreuses  situations sont similaires en  informatique et....\textit{dans la
  vraie vie}.

D.E. \textsc{Knuth} propose cette illustration (page 240 de \cite{knuth:vol1})





%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{trainKnuth}
\end{center}
%\end{figure}


qui  reprend l'article  fondateur de  E.W. \textit{Dijkstra}  (\cite{dij:shunt})
dont nous reparlerons bientôt:


%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{shuntingDijkstra}
\end{center}
%\end{figure}


Mais bon, on utilise le terme \textit{pile} en référence à un pile d'assiette: la
première que l'on saisira sera la dernière à avoir été empilée.


\subsection{Pile et NPI}

Reprenons notre expression $9/((2+\lnot 3)\times (4- \lnot 5))$. 

La plupart des compilateurs vont plutôt la lire ainsi: \verb|9 2 3 NEG + 4 5 NEG - * /|
en utilisant une pile.

Il faut juste  connaître l'\textit{arité} de chaque opérateur,  i.e. leur nombre
d'opérandes, qui  doit être fixe  (c'est pourquoi on doit  absolument distinguer
\verb+-+ de \verb+NEG+ et  éviter l'habituelle \textit{surcharge} de l'opérateur
\verb+-+).

\begin{enumerate}
\item On lit l'expression de gauche à droite;
\item On empile les opérandes;
\item   Dès qu'on
lit un  opérateur, on l'applique  aux opérandes présents  sur la pile  selon son
arité;
\item On s'arrête quand on n'a plus rien à lire;
\item on renvoie le dernier élément présent dans la pile.
\end{enumerate}

Voici  par  exemple les  différentes  étapes  du  calcul  effectué à  l'aide  du
\textit{calculator} d'Emacs:


\emacs

\begin{multicols}{3}
\begin{enumerate}
\item On entre \verb+9+ , \verb+2+ puis \verb+3+:

\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  2
1:  3
.
\end{lstlisting}

\item \verb+NEG+
\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  2
1:  -3
.
\end{lstlisting}

\item \verb|+|

\begin{lstlisting}
 Emacs Calculator Mode 
2:  9
1:  -1
.
.
\end{lstlisting}


\item \verb|4| puis \Enter


\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  -1
1:  4
.
\end{lstlisting}

\item \verb|5| puis \Enter


\begin{lstlisting}
 Emacs Calculator Mode 
4:  9
3:  -1
2:  4
1:  5
\end{lstlisting}


\item \verb|NEG|


\begin{lstlisting}
 Emacs Calculator Mode 
4:  9
3:  -1
2:  4
1:  -5
\end{lstlisting}


\item \verb|-|


\begin{lstlisting}
 Emacs Calculator Mode 
3:  9
2:  -1
1:  9
.
\end{lstlisting}

\item \verb|*|


\begin{lstlisting}
 Emacs Calculator Mode 
2:  9
1:  -9
.
.
\end{lstlisting}

\item \verb|/|


\begin{lstlisting}
 Emacs Calculator Mode 
1: -1
.
.
.
\end{lstlisting}

\end{enumerate}

\end{multicols}

\pythonc

Plusieurs avantages:

\begin{itemize}
\item pas besoin de parenthèses, de règles d'associativité, de priorité;
\item on voit au sommet de la pile les résultats intermédiaires;
\item le calcul est directement implémentable sur machine.
\end{itemize}


Au collège, $9/((2+\lnot 3)\times (4- \lnot 5))$ serait lu: 

\begin{center}

\og le \textit{rapport} entre
9   et   le   \textit{produit}   de  la   \textit{somme}   de   2   et
l'\textit{opposé}  de  3   et  la  \textit{différence}  de   4  et  de
l'\textit{opposé} de 5\fg{} 

\end{center}

ce qui peut se coder en:

\begin{center}
  \verb| / 9 * + 2 NEG 3 - 4 NEG 5|
\end{center}


C'est la méthode introduite en 1929 par Jan \textsc{\L ukasiewicz}. On a dénommé
\textit{notation polonaise}  cette méthode d'évaluation d'une  expression en son
honneur. On utilise également  la dénomination \textit{notation pré-fixée}. Cela
explique aussi l'appellation \textit{notation polonaise inversée} de la notation
post-fixée.


Ici aussi,  les opérateurs doivent être  d'arité fixe et l'évaluation  se fait à
l'aide d'une pile.


\begin{recherche}

Décomposez le calcul \verb| / 9 * + 2  NEG 3 - 4 NEG 5|. Comment l'organiser sur
machine?  Comparez avec  la  NPI.  Expliquez alors  le  choix  fait par  Charles
\textsc{Hamblin} d'utiliser plutôt la NPI sur machine.
\end{recherche}





\vfill

\eject



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}


\begin{exercice}[Adresse]
 Commentez! Quelles précautions prendre?

\begin{multicols}{2}
 \begin{lstlisting}
In [22]: t = [0,1,2,3]

In [23]: id(t)
Out[23]: 140162835709256

In [24]: tt = t

In [25]: id(tt)
Out[25]: 140162835709256

In [26]: t += [4]

In [27]: t
Out[27]: [0, 1, 2, 3, 4]

In [28]: id(t)
Out[28]: 140162835709256

In [29]: tt
Out[29]: [0, 1, 2, 3, 4]

In [30]: t = t + [5]

In [31]: t
Out[31]: [0, 1, 2, 3, 4, 5]

In [32]: tt
Out[32]: [0, 1, 2, 3, 4]

In [33]: id(t)
Out[33]: 140162734366856

In [34]: id(tt)
Out[34]: 140162835709256

In [35]: import copy as cp

In [39]: ttt = cp.copy(t)

In [40]: id (ttt)
Out[40]: 140162835291592

In [41]: t += [6]

In [42]: t
Out[42]: [0, 1, 2, 3, 4, 5, 6]

In [43]: tt
Out[43]: [0, 1, 2, 3, 4]

In [44]: ttt
Out[44]: [0, 1, 2, 3, 4, 5]
 \end{lstlisting}
\end{multicols}
\end{exercice}


\begin{exercice}[Performances]

Commentez:

\begin{multicols}{2}
\begin{lstlisting}
import numpy as np

def v1():
    l = [0,1,2]
    l += [3]
def v2():
    l = [0,1,2,None]
    l[3] = 3
def v3():
    l = [0,1,2]
    l.append(3)
def v4():
    l1 = np.array([0,1,2])
    l2 = np.array([3])
    np.concatenate((l1,l2))
def v5():
    l = np.array([0,1,2,None])
    l[3] = 2
def v6():
    l = np.arange(4)
    l[3] = 12
def v7():
    l = it.chain([0,1,2],[3])
\end{lstlisting}
\begin{lstlisting}
In [45]: %timeit v1()
1000000 loops, best of 3: 320 ns per loop

In [46]: %timeit v2()
10000000 loops, best of 3: 179 ns per loop

In [47]: %timeit v3()
1000000 loops, best of 3: 246 ns per loop

In [48]: %timeit v4()
100000 loops, best of 3: 5.19 μs per loop

In [49]: %timeit v5()
1000000 loops, best of 3: 1.91 μs per loop

In [50]: %timeit v6()
1000000 loops, best of 3: 788 ns per loop

In [68]: %timeit v7()
1000000 loops, best of 3: 404 ns per loop
\end{lstlisting}
\end{multicols}

\end{exercice}



\begin{exercice}[Barrière d'abstraction et Flavius Josèphe le fourbe]


% %\vspace{-6.2cm}
% \setindent{0cm}
% \begin{flushleft}
% \begin{minipage}[t]{3cm}
% %\begin{figure}
%   \includegraphics[width=3.2cm]{quovadis}
% %\end{figure}
% \end{minipage}
% \end{flushleft}
% \setindent{\indentationcours}
% \vspace{-3.1cm}
% \begin{minipage}[t]{\linewidth}


% \end{minipage}
  

Flavius Josèphe (37  - 100) ou plutôt Yossef  ben Matityahou HaCohen est
un  historien romain  d'origine juive  et de  langue grecque  et  qui ne
devait pas être trop mauvais en  mathématiques si on en croit la sinistre
anecdote suivante. Lors de  la première guerre judéo-romaine, Yossef fut
piégé dans une grotte avec 39 autres de ses compagnons en juillet 67. Ne voulant pas
devenir esclaves, ils mirent  au point un algorithme d'auto-destruction:
il s'agissait de se mettre en cercle et de se
numéroter de 1 à 40. 

\begin{center}
\includegraphics[width=6cm]{quovadis}
%\setindent{0cm}
\end{center}

Chaque  septième devait être tué  jusqu'à ce qu'il
n'en  reste plus  qu'un qui  devait alors  se suicider.  Ce  dernier fut
Yossef lui-même...et il ne se suicida  pas! Après deux ans de prison, il
fut libéré, il  entra au service des romains  comme interprète et acquit
la citoyenneté romaine deux ans plus tard.



On voudrait savoir quel numéro portait Yossef. Vous allez créer un programme Python qui donne l'ordre
des  exécutions quelque  soit  le  nombre de  prisonniers,  le  nombre fatal  et
l'implémentation  de  la  structure  linéaire  utilisée: il  faut  penser  à  la
\textbf{barrière d'abstraction}.

TOUTES les  implémentations des listes doivent  suivre la \textbf{spécification}
donnée en cours:

\begin{center}
\begin{tabular}[!h]{|l||l*{4}{|p{1cm}}|}
\hline
\backslashbox[5.8cm]{spécification}{implémentation} & Version 0  (listes natives) & V.1
 couples
& V.2 fonc. & V.3 POO & V.4 POO\\
\hline
\textbf{Vide}: la liste vide&\lstinline{[]} &&&&\\
\hline
\textbf{estVide}: testeur de vacuité& \lstinline{def estVide(xs): return xs == Vide}&&&&\\
\hline
\textbf{tête}: 1\up{er} élément& \lstinline{def tete(xs): return xs[0]}&&&&\\
\hline
\textbf{queue}: la liste décapitée& \lstinline{def queue(xs): return xs[1:]}&&&&\\
\hline
\textbf{insère}: place un élément à gauche& \lstinline{def insere(x,xs): return [x] + xs} &&&&\\
\hline
\end{tabular}
\end{center}


On  pourra alors  créer (par  exemple :-)  ), à  partir des  spécifications, des
fonctions  comme \lstinline{supprime(el  no i,liste)}  qui renvoie  une nouvelle
liste sans l'élément \no
$i$  de la  liste donnée  en argument,  \lstinline{numero(i,lsite)} qui  renvoie
l'élément \no  $i$ d'une liste,  \lstinline{intervalle(n)} qui renvoie  la liste
des entiers de 0 à $n-1$ compris.

On pourra aussi utiliser la fonction \lstinline{repr}:

\begin{lstlisting}
In [5]: ?repr
Type:        builtin_function_or_method
String form: <built-in function repr>
Namespace:   Python builtin
Docstring:
repr(object) -> string

Return the canonical string representation of the object.
For most object types, eval(repr(object)) == object.
\end{lstlisting}




Dans une  autre situation (pour  ne pas  vous donner la  réponse quand
même...),  on  doit obtenir  avec  20  compagnons  et 6  comme  nombre
sinistre suite:

\begin{lstlisting}
La 1e victime est le no 6
La 2e victime est le no 12
La 3e victime est le no 18
La 4e victime est le no 4
La 5e victime est le no 11
La 6e victime est le no 19
La 7e victime est le no 7
La 8e victime est le no 15
La 9e victime est le no 3
La 10e victime est le no 14
La 11e victime est le no 5
La 12e victime est le no 17
La 13e victime est le no 10
La 14e victime est le no 8
La 15e victime est le no 2
La 16e victime est le no 9
La 17e victime est le no 16
La 18e victime est le no 13
La 19e victime est le no 1
Out[62]: 'Et le survivant est le no 20'
\end{lstlisting}

Peut-on prévoir qui sera le survivant sans dresser de liste?





\end{exercice}




\begin{exercice}[Méthodes nouvelles sur les listes]
  Voici un extrait de la documentation du module \texttt{Data.List} du
  langage \textbf{Haskell}:

\haskell

\begin{lstlisting}[caption={Extrait de la documentation Haskell de Data.List}]
  (++) :: [a] -> [a] -> [a]	 
Append two lists, i.e.,
 [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
 [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
If the first list is not finite, the result is the first list.

head :: [a] -> a	 
Extract the first element of a list, which must be non-empty.

last :: [a] -> a	 
Extract the last element of a list, which must be finite and non-empty.

tail :: [a] -> [a]	 
Extract the elements after the head of a list, which must be non-empty.

init :: [a] -> [a]	 
Return all the elements of a list except the last one. The list must be non-empty.

null :: [a] -> Bool	 
Test whether a list is empty.

length :: [a] -> Int	 
length returns the length of a finite list as an Int. It is an instance of the more general Data.List.genericLength, the result type of which may be any kind of number.

map :: (a -> b) -> [a] -> [b]	
map f xs is the list obtained by applying f to each element of xs, i.e.,
 map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
 map f [x1, x2, ...] == [f x1, f x2, ...]

reverse :: [a] -> [a]	
reverse xs returns the elements of xs in reverse order. xs must be finite. 

foldl :: (a -> b -> a) -> a -> [b] -> a	
foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:
 foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
The list must be finite. 

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.

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.

maximum :: Ord a => [a] -> a	
maximum returns the maximum value from a list, which must be non-empty, finite, and of an ordered type. It is a special case of maximumBy, which allows the programmer to supply their own comparison function.

minimum :: Ord a => [a] -> a	
minimum returns the minimum value from a list, which must be non-empty, finite, and of an ordered type. It is a special case of minimumBy, which allows the programmer to supply their own comparison function. 

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] == []

elem :: Eq a => a -> [a] -> Bool	
elem is the list membership predicate, usually written in infix form, e.g., x `elem` xs. 

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.

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]

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; i.e.,
 partition p xs == (filter p xs, filter (not . p) xs)

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{lstlisting}

\pythonc

Créez  les fonctions  (ou méthodes)  similaires pour  les différentes  versions:
a-t-on besoin d'en créer des différentes pour chaque version?

La\textit{ barrière d'abstraction}...


%\begin{figure}
\begin{center}
  \includegraphics[height=6.25cm]{compris}
\end{center}
%\end{figure}




Étudiez le nombre d'opérations élémentaires nécessaires en fonction de
la taille de la liste en argument.



\end{exercice}










\begin{exercice}[Morphisme de monoïde]\label{exo::monoide}
  On a remarqué dans l'exercice précédent que \lstinline{elem}, \lstinline{sum},
  \lstinline{length},  \lstinline{map},  \lstinline{foldl},  \lstinline{filter},
  etc. fonctionnaient toutes selon le même principe et que l'on avait tendance à
  se répéter un peu.

La lumière va venir de l'algèbre  et plus particulièrement des homomorphismes de
monoïdes (derrière se cache en fait la notion de \textit{catégorie}...).

Nous  remarquons en  effet  que  toutes ces  fonctions  sont  des morphismes  de
monoïde.

Soit \lstinline{a} notre type de base. Notons \lstinline{a list} le type des listes d'éléments de
type  \lstinline{a}. Si  on munit  \lstinline{a  list} de  la concaténation  des
chaînes (que nous noterons \lstinline{++}), on obtient un
 monoïde dont l'élément neutre est la liste vide.

Considérons par exemple la fonction  \lstinline{length}. Elle est à valeurs dans
\lstinline{Nat}, le type  des entiers non signés, qui, muni  de l'addition, est
aussi un monoïde.

$$
\mathtt{length(lst1      ++      lst2)}      =      \mathtt{length(lst1)}      +
\mathtt{length(lst2)}\qquad \text{ et } \qquad \mathtt{length(Vide)}=0
$$


Pour  chaque  élément,  on  peut  considérer  la  fonction  $λ  x\  :\  1$  dont
\lstinline{length}  est le  \og gonflement\fg{}  (une liste  ne contenant  qu'un
élément est de longueur 1).

On a donc le diagramme suivant:

$$
\begin{tikzcd}
\mathtt{a} \arrow{rr}{\text{injection canonique}} \arrow[swap]{dr}{λx\ :\ 1}& & \mathtt{a\ list (++,vide)}\arrow{dl}{\mathtt{length}}\\
& \mathtt{Nat(+,0)} & 
\end{tikzcd}    
$$

L'injection canonique transforme un élément  quelconque en la liste constituée
de cet unique élément.

Cela  nous donne  alors  un  moyen d'imaginer  une  construction d'une  fonction
générale qui construira le morphisme en fonction  de la fonction de gauche et du
morphisme du bas.

\begin{lstlisting}
def gonfle(f,loiMonoide,neutreMonoide):
    """
    crée le morphisme de monoïde entre [a] et b si b est un monoïde
    i.e.  gonfle la fonction f : a -> b en le morphisme f* : [a] -> b
    loiMonoide : (b*b) -> b
    neutreMonoide : le neutre de b
    f traite les éléments, f* traite les listes de ces éléments
    f*([a])          = f(a)
    f*([as] ++ [as]) = f*([as]) loiMonoide f*([as])
    f*([])           = neutreMonoide
    ex:
    longueur =  gonfle(lambda x: 1, operator.add, 0)
    """
    ?????
\end{lstlisting}

Construisez cette fonction.

Tracez les diagrammes de \lstinline{elem}, \lstinline{sum},
    \lstinline{map},  \lstinline{foldl}, \lstinline{filter}  puis définissez-les
    sur Python à l'aide de la fonction \lstinline{gonfle}. 

Démontrez  par  récurrence  que  toute fonction  créée  avec  \lstinline{gonfle}
renvoie le morphisme de monoïde défini par le diagramme général: \textit{une preuve pour
les démontrer toutes...
}


%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{anneau}
\end{center}
%\end{figure}

  
\end{exercice}


















\begin{exercice}[Pile!]

Déterminez une spécification de la structure \textit{Pile}.

Implémentez-la sur Python.
  
\end{exercice}


\begin{exercice}[\texttt{operator}]

Python   dispose  d'une   bibliothèque  \texttt{operator}   comprenant
quelques fonctions usuelles.
  

\begin{lstlisting}
In [1]: from operator import add,mul

In [2]: mul(add(2, mul(4, 6)), add(3, 5))
Out[2]: 208
\end{lstlisting}

C'est infixe? Postfixe ? Autre ?

Comment la machine peut évaluer cette expression?

Il faut savoir comment Python procède.

\begin{lstlisting}
In [9]: def fst(c):
   ...: return c[0]
   ...: 

In [10]: fst((1,2))
Out[10]: 1

In [11]: fst((1,1/0))
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-11-707229f26363> in <module>()
----> 1 fst((1,1/0))

ZeroDivisionError: division by zero
\end{lstlisting}


Tout le monde ne fait pas pareil:

\haskell

\begin{lstlisting}
Prelude> let fst (a,b) = a
Prelude> fst (1,2)
1
Prelude> fst (1,1/0)
1
\end{lstlisting}

\pythonc

Dresser un arbre d'expression qui traduit l'évalutation de \texttt{ mul(add(2, mul(4, 6)), add(3, 5))}.


\end{exercice}




\begin{exercice}[HP15C]
  Créez une calculatrice  qui effectue les calculs  arithmétiques à la
  manière du \textit{calculator} d'Emacs.

  On  pourra se  contenter d'une  version simplifiée:  on donne  comme
  argument  la chaîne  correspondant  à l'opération  à effectuer  sous
  forme postfixée. La fonction renvoie le résultat de l'opération. Par
  exemple:

  \begin{lstlisting}
In [1]: seq = '2 3 4 + *' 

In [2]: npi(seq)
Out[2]: 14
  \end{lstlisting}

On pourra utiliser les fonctions du module \texttt{operator}.

Par exemple, \texttt{operator.add(2,3)} renvoie 5.

On peut alors créer un dictionnaire des opérations:

\begin{lstlisting}
operations = {
    '+':  operator.add, '-':  operator.sub,
    '*':  operator.mul, '/':  operator.truediv,
    '%':  operator.mod, '**': operator.pow,
    '//': operator.floordiv
}
\end{lstlisting}

et  on   obtient  l'opération  d'addition   à  partir  de   la  chaîne
\texttt{'+'}:

\begin{lstlisting}
In [3]: operations['+']
Out[3]: <function _operator.add>
\end{lstlisting}

Par exemple:

\begin{lstlisting}
In [1]: hp('3 2 7 9 - * 3 + 2 / +')
Out[1]: 2.5

In [2]: hp('3 2 7 9 - * 3 + 2 /')
  File "<string>", line unknown
SyntaxError: Expression non valide
\end{lstlisting}

Vous   pouvez    ensuite   proposer   une   calculatrice    plus   \og
intercative\fg{}:

\begin{lstlisting}
In [1]: hp_inter()
->  |
rentrer un nombre ou un opérateur: 1
-> 1 |
rentrer un nombre ou un opérateur: 2
-> 2, 1 |
rentrer un nombre ou un opérateur: 3
-> 3, 2, 1 |
rentrer un nombre ou un opérateur: 4
-> 4, 3, 2, 1 |
rentrer un nombre ou un opérateur: '+'
-> 7, 2, 1 |
rentrer un nombre ou un opérateur: '-'
-> -5, 1 |
rentrer un nombre ou un opérateur: '+'
-> -4 |
rentrer un nombre ou un opérateur: 3
-> 3, -4 |
rentrer un nombre ou un opérateur: '*'
-> -12 |
rentrer un nombre ou un opérateur: 'fin'
\end{lstlisting}




\end{exercice}


\begin{exercice}[Casio/TI]

Créez une calculatrice qui lit une expression arithmétique en notation
infixe et  effectue le calcul  en utilisant  une (ou des)  pile(s). On
utilisera les mêmes opérateurs  \textbf{binaires} (i.e. d'arité 2) que
précédemment  (attention  à  séparer  les  opérandes,  parenthèses  et
opératuers par des espaces). Par exemple:

\begin{lstlisting}
In [1]: casio('3 + ( ( ( 2 * ( 7 - 9 ) ) + 3 ) / 2 )')
Out[1]: 2.5

In [2]: casio('3 + ( (  2 * ( 7 - 9 )  + 3 ) / 2 )')
  File "<string>", line unknown
SyntaxError: expression non valide
\end{lstlisting}
  
\end{exercice}





\begin{exercice}[Traces]
  On change un peu la méthode d'affichage des \texttt{Noeuds} dans la version 4:

  \begin{lstlisting}
def __str__(self):
       s = self.get_suivant()
       return "Noeud(" + str(self.get_valeur()) + " -> " + str(s) + ")"
  \end{lstlisting}

Commentaires ?
\end{exercice}



\begin{exercice}[Rendre la justice]

Supposons que nous disposions d'une pièce  de monnaie mal équilibrée: elle tombe
sur face avec une probabilité de \num{0,2} par exemple.

Comment faire  pour malgré tout  effectuer des tirages équilibrés?  (D'après une
idée de John \textsc{Von Neumann})

\begin{enumerate}
\item Déterminer  d'abord une fonction  \lstinline{dePipe()} qui renvoie  1 avec
  une   probabilité    de   \num{0,2}.   On   pourra    utiliser   *0la   fonction
  \lstinline{random()} de Python.

Alors:

\begin{lstlisting}
In [123]: sum(dePipe(0.2) for i in range(10000))
Out[123]: 2045
\end{lstlisting}

\item On lance deux  fois de suite la pièce: quelle  est la probabilté d'obtenir
  face en deuxième ou pile en deuxième si les deux pièces sont différentes.

  Cela doit vous inspirer une méthode pour équilibrer le tirage.

  \begin{lstlisting}
In [125]: sum(deJuste(dePipe,0.2) for i in range(10000))
Out[125]: 5015
  \end{lstlisting}

\end{enumerate}
  
\end{exercice}



\begin{exercice}[Duc de Toscane]
Cosme II de  Médicis (Florence 1590-1621), Duc de Toscane,  fut le protecteur de
l’illustre  Gallilée (né  à Pise  le 15  février 1564  et mort  à Florence  le 8
janvier 1642)  son ancien précepteur. Profitant  d’un moment de répit  du savant
entre l’écriture  d’un théorème  sur la  chute des  corps et  la création  de la
lunette astronomique, le Grand Duc lui soumet le problème suivant : il a observé
qu’en lançant trois dés  cubiques et en faisant la somme  des numéros des faces,
on obtient plus souvent  10 que 9, alors qu’il y a autant  de façons d’obtenir 9
que  10, à  savoir six.   Après quelques  réflexions, Galilée  rédigea un  petit
mémoire sur les jeux de hasard en 1620 expliquant le phénomène.


Observons nous-même  sans perdre trop  d'argent mais  avec seulement 2  dés pour
aller plus vite:


\begin{lstlisting}
from collections import Counter
sObs = [sum( randint(1,7,size = 2) ) for k in range(144000)]
cObs = Counter(sObs)
\end{lstlisting}

On obtient le dictionnaire des effectifs observés: 

\begin{lstlisting}
Counter({7: 23996, 8: 20029, 6: 19934, 9: 15942, 5: 15767, 4: 12152, 10: 12030, 11: 8011, 3: 8003, 12: 4095, 2: 4041})
\end{lstlisting}

Pour un  rendu graphique  d'une grande  qualité, on utilise  le module  pygal de
Python: 

\begin{lstlisting}
from pygal import *
toscane = HorizontalBar()
for v in cObs:
    toscane.add(str(v),cObs[v])
toscane.render_to_file("toscane.svg")
\end{lstlisting}

Ensuite,  depuis ipython  on peut  visualiser sur  firefox par  exemple avec  la
commande: 

\begin{lstlisting}
In [9]: !firefox ./toscane.svg
\end{lstlisting}



%\begin{figure}
\begin{center}
  \includegraphics[height=10cm]{toscane}
\end{center}
%\end{figure}



Remplissez le tableau suivant:

\setindent{0cm}

\sm

\begin{tabularx}{\linewidth}{Y{10}}
\whline
Sortie&2&3&4&5&6&7&8&9&10&11&12\\
\hline
Proba&&&&&&&&&&&\\ 
\whline
\end{tabularx}

\sm

et celui-ci:
\sm


\setindent{0cm}

\begin{tabularx}{\linewidth}{Y{10}}
\whline
Sortie&2&3&4&5&6&7&8&9&10&11&12\\
\hline
Observé&4041&8003&&&&&&&&&\\ 
\hline
Attendu&4000&&&&&&&&&&\\ 
\whline
\end{tabularx}
\sm



On ne  tombe jamais  sur ce  qui était demandé:  combien y  a-t-il de  suites de
\num{144000} lancers de 2 dés possibles? 

Est-ce que les dés lancés par Python sont pipés?

\begin{quote}
Gailleurs bien faitz en piperie \\
Pour ruer les ninars au loing \\
A l'asault tost sans suerie \\
Que les mignons ne soient au gaing\\
Farciz d'un plumbis a coing \\
Qui griffe au gard le duc \\
Et de la dure si tres loing \\
Dont l'ambourex luy rompt le suc.\\

\begin{flushright}
  in \textit{Ballade en Jargon} - Attribué à François \textsc{Villon} - 1489
\end{flushright}
\end{quote}


Une première idée est de mesurer la distance de la distribution observée avec la
distribution attendue.

Notons $O_i$ les valeurs observées et $ A_i=\num{144000}×p_i$ les valeurs attendues.

Comment la mesurer? On peut utiliser la distance euclidienne habituelle:

$$ D^2=(O_2-A_2)^2+(O_3-A_3)^2+\cdots +(O_{12}-A_{12})^2$$

Mais par exemple, 7 apparaît beaucoup plus  que 2 mais dans le calcul précédent,
mais  les distances  ont le  même poids  dans le  calcul précédent.  On va  donc
pondérer les écarts par leurs effectifs théoriques:



$$                    D^2=\frac{(O_2-A_2)^2}{A_2}+\frac{(O_3-A_3)^2}{A_3}+\cdots
+\frac{(O_{12}-A_{12})^2}{A_{12}}$$

Un peu de calcul:

\begin{lstlisting}
sTheo = [x + y for x in range(1,7) for y in range(1,7)]
cTheo = {x: v*len(sObs)/len(sTheo) for x,v in Counter(sTheo).items()}
khi2Details = [(x,((cObs[x] - cTheo[x])**2) /cTheo[x]) for x in cTheo]
khi2 = sum([((cObs[x] - cTheo[x])**2) /cTheo[x] for x in cTheo])
\end{lstlisting}


Alors:

\begin{lstlisting}
In [35]: khi2Details
Out[35]: 
[(2, 0.42025),
 (3, 0.001125),
 (4, 1.9253333333333333),
 (5, 3.3930625),
 (6, 0.2178),
 (7, 0.0006666666666666666),
 (8, 0.04205),
 (9, 0.21025),
 (10, 0.075),
 (11, 0.015125),
 (12, 2.25625)]

In [36]: khi2
Out[36]: 8.556912500000001
\end{lstlisting}


Comment interpréter ce $ 8.55$?

Ceci  est une  autre histoire:  il vous  faudrait étudier  un peu  plus avant  les
probabilités à densité et la loi du $ χ^2$ mais ce n'est pas au programme de prépa...
  
\end{exercice}










\begin{exercice}[Littérature markovienne]


\begin{quote}
ézait sortin au. Il s'énére ter crière que quattais de étaits mait se.

Fros somblogiest sayonnarriansous laffent Fralles et de ceté sate enne ave étot te fur da pour ren couvait diachumi nour l'a destérienséquilbus jau la pieriencet pousquerrissien brille et un antu ces mout, Phoelloribé de
Poire.

La ce, qui l'arcet cetoule notrête dénée l'auvaien vin sant lierier, jourbriet duandit ent d'une cec donne
fait finde ve, le ble forchaité qu'eaux hant-auter savaitité donnath çà et! vionsibie. faibayoucle fon
tousqui fil, etc. Il regant dées dée eur, il, rencont avecerme, que, la sur commenficellemodon de de paithe à etta.

Lier Elle quends  tre de. Ses inait de  choment: Cois, joussé
du més factu 
ler toucaliquisau con et privrent
as de fettencierisi querre gala hon!»

«Part l'une pres forreposi énabla dit de se? Poliertou! guelle. Il conneaude ficiantai sau fortifflèclo ame nait ots te qui les taitille d'es, ourds.

Dommen même forbiens de que! il à von com Le loct au
\end{quote}


\smallskip

Joli  ce  texte? Il  a  été  engendré par  un  petit  programme Python  que  nous
étudierons et qui a analysé le
texte complet  du roman \og Notre-Dame de Paris\fg{} de Victor \textsc{Hugo} en
utilisant des chaînes de Markov...

\smallskip

Voici une version markovienne du text d'\textit{Autant en emporte le vent} de
Margaret \textsc{Mitchell}: est-ce en VO ou en français?

\smallskip

 \begin{quote}
ematin wer there diateeptim!  Scarry yould herseekirlegaveddral froolsid thatill no mithe was was
ney sing thiesse?  Ashlett, bellays of pred, crown so of ley on Buthred, chearm.  I chaby!"

"Go wera brourve.

"Whalliet the se scout re
Melappy lanyth the caries, therappy of th.  "My of thatcarivin ithoess he she to litead a puld lace.  Fonerk the a for, bache orow anyto losed you,
alwal how wery Lon, I kaged ting and She of he forle.  Yan hine, busurstn' the showernow mad heryin't by, to ted cray!

"Oh, ejoyesso looked as becid broarasn't this welim sairlet, hopin feedrught abladeas!

Letne shat I cott astaiddeps Rhey shad had ner in thad ishe's thas ped the goine.

Butland faigh took beet the'd now, Scart it wit Scall dided mords suddly, se so tillike up
anto loo.

"Yes drostry towd the smosixt wusquall is witheir, let she ithenryin she the me wif he gong earls lifulds bon brom wited yould agother or
muslockeptabled
Mer akso com ing hirom, man thad
led
wo red heas imse.

"Gawaracead. 
\end{quote}



On  peut  récupérer de  nombreux  textes  au  formats \lstinline{TXT}  grâce  au
\textit{projet Gutemberg}.

Par exemple:

\begin{lstlisting}
from urllib.request import urlretrieve
urlretrieve('http://www.gutenberg.org/cache/epub/19657/pg19657.txt','ndp.txt')
\end{lstlisting}

vous permet de  récupérer le texte intégrale de \textit{Notre-Dame  de Paris} et
de l'enregistrer en local dans \lstinline{ndp.txt}.

 
\foreignlanguage{russian}{Андрей Андреевич  МАРКОВ} (1856 -
1922), grand mathématicien  russe, initiateur des probabilités modernes,
grand amateur de poésie,   n'hésita pourtant pas à s'impliquer dans la
tumultueuse  histoire  de  son   pays.  Il  n'eut  pas  peur  d'affirmer
publiquement son  anti-tsarisme et fut  renvoyé de l'Université.  Il fut
réhabilité après la Révolution. 

Vous étudierez de manière élémentaire quelques résultats de ses travaux
sur   les   processus   aléatoires  (ou   stochastiques),   c'est-à-dire
l'évolution   dans   le   temps   d'une   variable   aléatoire   appelés
\textit{chaînes  de  \textsc{Markov}} dont  les  applications sont  très
nombreuses, notamment en informatique  (reconnaissance de la langue d'un
texte,  techniques  de  compression,  l'algorithme PageRank  de  Google,
files d'attente, bioinformatique,...)

D'un point de vue plus probabiliste, les chaînes de \textsc{Markov} 
 permettent d'étudier des v.a.r. non indépendantes.


La particularité  des chaînes de \textsc{Markov} est  de représenter des
processus où la probabilité permettant de passer à un instant donné d'un
état présent à un état futur 
ne dépend du passé qu'à travers le présent soit: \og la probabilité du
futur  sachant présent  et passé  est égale  à la  probabilité  du futur
sachant le présent\fg{}.

Pour générer le texte précédent, on considère chaque paire de
lettres rencontrée dans le texte et on  voudrait savoir quelle est la lettre qui
va  suivre. On  construit  une loi  de probabilité  en  fonction des  fréquences
observées dans le texte.

Faites-le...

Vous pourrez avoir besoin de  \lstinline{random.choice} qui permet de choisir un
élément dans un itérable aléatoirement selon une distribution uniforme:

\begin{lstlisting}
from random import choice
In [68]: choice([1,2,3,4,5])
Out[68]: 2
\end{lstlisting}


Quelques rappels sur la manipulation de  fichiers. Voici un moyen de transformer
un fichier TXT codé en UTF-8 en la liste de ses caractères:

\begin{lstlisting}
from itertools import chain

f = open('ndp.txt','r')
d = f.read()
lettres = map(lambda lettre: ','.join(lettre),d)
list(chain.from_iterable(lettres))
\end{lstlisting}

Pensez aux dictionnaires...




\end{exercice}




\begin{exercice}[Tables de Briggs]

Créez les  tables de logarithmes  selon la méthode  de Briggs (vous  ne disposez
que des  opérations arithmétiques élémentaires)  après avoir étudié  le document
suivant:
\href{http://hal.inria.fr/inria-00543939}{http://hal.inria.fr/inria-00543939}
  
\end{exercice}










\modenormal

%%% Local Variables: 
%%% TeX-master: "PolyIPT2014_15"
%%% End: 
