\chapterimage{luka}
\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 :-)}

\chapter{Structures de données linéaires}


\modeexercice

\begin{exercice}[Centrale 2015]
  \begin{enumerate}
  \item Donnez la valeur des expressions suivantes:
    \begin{enumerate}
    \item \mintinline{python}{[1, 2, 3] + [4, 5, 6]}
    \item \mintinline{python}{2 * [1, 2, 3]} 
    \end{enumerate}
  \item Écrivez une  fonction Python \texttt{smul} à deux  paramètres, un nombre
    et une  liste de nombres,  qui multiplie chaque élément  de la liste  par le
    nombre et renvoie une nouvelle liste: \mintinline{python}{ smul(2, [1, 2, 3])} $⟶$ \mintinline{python}{[2, 4, 6]}.
  \item \textbf{Arithmétique des listes}
    \begin{enumerate}
    \item Écrivez une fonction Python  \texttt{vsom} qui prend en paramètre deux
      listes  de nombres  de même  longueur et  qui renvoie  une nouvelle  liste
      constituée de la somme terme à terme de ces deux listes:

\mintinline{python}{vsom([1, 2, 3], [4, 5, 6])} $⟶$ \mintinline{python}{[5, 7, 9]}. 

\item Écrivez une fonction Python  \texttt{vdif} qui prend en paramètre deux
      listes  de nombres  de même  longueur et  qui renvoie  une nouvelle  liste
      constituée de la différence terme à terme de ces deux listes:

\mintinline{python}{vsom([1, 2, 3], [4, 5, 6])} $⟶$ \mintinline{python}{[-3, -3, -3]}. 
\end{enumerate}

\item \textbf{Question subsidiaire}

Créez une fonction d'ordre supérieure qui prendra l'operation comme paramètre.

Ainsi, \texttt{vsom} sera \mintinline{python}{vop(addition)}. 

\end{enumerate}
 
\end{exercice}


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

\begin{multicols}{3}
 \begin{pythoncode}
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{pythoncode}
\end{multicols}
\end{exercice}


\begin{exercice}[Performances]

Commentez:

\begin{multicols}{2}
\begin{pythoncode}
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{pythoncode}

\end{multicols}



\newpage

\begin{multicols}{2}
\begin{pythoncode}
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{pythoncode}
\end{multicols}

\end{exercice}



\begin{exercice}[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=10cm]{flavius}
%\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 et le nombre fatal


Vous pourrez utiliser dans un premier temps les listes de Python et la fonction  \mintinline{python}{pop}.

Ensuite, vous pourrez utiliser la structure générale de liste chaînée vue en cours.



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{multicols}{2}
\begin{pythoncode}
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{pythoncode}
\end{multicols}


Peut-on  prévoir qui  sera le  survivant sans  dresser de  liste avec  une belle
fonction récursive?...





\end{exercice}


\newpage

\begin{exercice}[Piles]

Dans ce TD nous considèrerons disposer d'un type pile et des opérations suivantes~:

\begin{center}
{\renewcommand{\arraystretch}{1.25}
\begin{tabularx}{0.9\textwidth}{|c|X|}
\hline
Opération & Effet\\\hline
\texttt{pile()} & Création d'une nouvelle pile (vide)\\\hline
\texttt{p.pop()}& Retire l'élément au sommet de la pile \texttt{p} et renvoie sa valeur. \par Une erreur survient si la pile est vide. \\\hline
\texttt{p.push(x)}& Ajoute l'élément \texttt{x} au sommet de la pile \texttt{p}.\\\hline
\texttt{p.is\_empty()}&Renvoie \texttt{True} si la pile est vide et \texttt{False} sinon.\\\hline
\end{tabularx}
}
\end{center}


Nous ne disposons d'aucune autre opération sur les piles.



\textit{Remarques~liminaires.}
\begin{itemize}
\item  Vous indiquerez pour chaque fonction la complexité en temps et en espace.
\item Certaines fonctions supposent que la pile est non-vide. On ne vérifiera pas que la pile est bien non-vide et on laissera l'erreur survenir si la pile est en fait vide.
\item Vous veillerez à bien faire la différence entre modifier une pile existante et créer une nouvelle pile.
\item Vous n'utiliserez aucune autre structure de données que les piles. En particulier, vous n'utiliserez pas de listes.
\end{itemize}

Implémenter les fonctions suivantes sur les piles:

\begin{enumerate}
\item \texttt{nonepop(p)} qui a le même effet que \texttt{p.pop()}, sauf si la pile est vide : dans ce cas, la pile reste inchangée et \texttt{nonepop(p)} renvoie \texttt{None}.

\item \texttt{duplique(p)} qui duplique l'élément au sommet de la pile.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
%\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {B};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{duplique(p)}};
\end{tikzpicture}
\end{center} 

\item \texttt{echange(p)} qui échange les deux premiers éléments de la pile \texttt{p}.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {A};
\node [cell] at (0,0.75) {C};
\node [cell] at (0,0.75*2) {B};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{echange(p)}};
\end{tikzpicture}
\end{center} 

%\begin{tikzpicture}[>=stealth, shape aspect=.5]
%\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}
%
%\begin{scope}[xshift=-4cm]
%\node [base] at (0,-0.75) {};
%\node [invisible] (A) at (0,0) {};
%\node at (0,-1) {pile vide};
%\end{scope}
%
%\begin{scope}
%\node[cell] (B)  at (0,0) {A};
%\end{scope}
%
%\begin{scope}[xshift=4cm]
%\node[cell] (C)  at (0,0) {A};
%\node [cell] at (0,0.75) {B};
%\end{scope}
%
%
%\begin{scope}[xshift=8cm]
%\node[cell] (D)  at (0,0) {A};
%\end{scope}
%
%
%\begin{scope}[xshift=12cm]
%\node[cell] (E)  at (0,0) {A};
%\node [cell] at (0,0.75) {A};
%\end{scope}
%
%\path[draw,->,line width=5pt] (A) -- (B) node [midway,below] {\mintinline{python}{push(A)}};
%\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{push(B)}};
%\path[draw,->,line width=5pt] (C) -- (D) node (xxx) [midway,below] {\mintinline{python}{pop()}};
%\node (Y) [below= 0.7cm of xxx] {\mintinline{python}{return B}};
%\path[draw,->,line width=3pt] (xxx) -- (Y);
%\path[draw,->,line width=5pt] (D) -- (E) node [midway,below] {\mintinline{python}{push(A)}};
%\end{tikzpicture}


\item \texttt{ecrase(p)} qui efface tous les éléments de \texttt{p}.

\item \texttt{rotation(p)} qui met au fond de la pile \texttt{p} l'élément qui est actuellement au dessus de la pile.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {C};
\node [cell] at (0,0.75) {A};
\node [cell] at (0,0.75*2) {B};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{rotation(p)}};
\end{tikzpicture}
\end{center} 


\item \texttt{longueur (p)}  qui calcule la taille de la pile \texttt{p}. %\`A la fin et au début de l'exécution de \texttt{longueur(p)}, la pile \texttt{p} devra être dans le même état.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
%\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
%\node [cell] at (0,0.75*2) {B};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node (xxx) [midway,below] {\mintinline{python}{longueur(p)}};
\node (Y) [below= 0.7cm of xxx] {\mintinline{python}{return 2}};
\path[draw,->,line width=3pt] (xxx) -- (Y);
\end{tikzpicture}
\end{center} 


\item \texttt{inverse (p)} qui inverse l'ordre des éléments de \texttt{p}.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {C};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {A};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{inverse(p)}};
\end{tikzpicture}
\end{center} 


\item \texttt{copy (p)} qui renvoie une nouvelle pile, qui est une copie de \texttt{p}. %\`A la fin et au début de l'exécution de \texttt{taille p}, la pile \texttt{p} devra être dans le même état.

\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=6cm]
\node[cell]  at (0,0) {A};
\node [cell] at (0,0.75) {B};
\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{q}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node [midway,below] {\mintinline{python}{q=copy(p)}};
\end{tikzpicture}
\end{center} 
\item \texttt{cherche(p,  x)} qui renvoie \texttt{True} si \texttt{x} est dans la pile \texttt{p} et \texttt{False} sinon.


\begin{center}
\begin{tikzpicture}[>=stealth, shape aspect=.5,scale=1]
\tikzset{glob/.style={cylinder, shape border rotate=90,minimum width=1.5cm,minimum height=1cm},cell/.style={glob,draw,thick,fill=gray!20},base/.style={glob,cylinder, cylinder uses custom fill, cylinder end fill=gray!100},invisible/.style={glob}}

\begin{scope}
\node[cell] (B)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
%\node [cell] at (0,0.75*2) {C};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\begin{scope}[xshift=4cm]
\node[cell] (C)  at (0,0) {A};
\node [cell] at (0,0.75) {B};
%\node [cell] at (0,0.75*2) {B};
\node at (0,-1) {pile \mintinline{python}{p}};
\end{scope}

\path[draw,->,line width=5pt] (B) -- (C) node (xxx) [midway,below] {\mintinline{python}{cherche(p,A)}};
\node (Y) [below= 0.7cm of xxx] {\mintinline{python}{return True}};
\path[draw,->,line width=3pt] (xxx) -- (Y);
\end{tikzpicture}
\end{center} 

\end{enumerate}




\end{exercice}



\begin{exercice}[D'après une épreuve posée lors d'un entretien Google]

Dans cet exercice on considère des chaînes de caractères avec $3$ types  de parenthèses () [] \{\} (par exemple \texttt{s}=\texttt{"\{([[]]))\}"}).

\begin{enumerate}
\item Parmi les chaînes de caractères suivantes, lesquelles sont bien parenthésées ?
\begin{multicols}{2}%
\begin{enumerate}%
\item \texttt{()[]\{()\}} \item \texttt{([(]))} \item \texttt{([][]\{()\}} \item  \texttt{([][]\{()\})}
\end{enumerate}\end{multicols}
\item  \'Ecrire une fonction qui prend en argument une telle chaîne de caractères et vérifie qu'elle est bien parenthésée, c'est-à-dire qui renvoie \texttt{True} si elle est bien parenthésée et \texttt{False} sinon.
\item Indiquer votre complexité en temps et en espace.
\item Comment simplifier l'algorithme dans le cas où il n'y aurait qu'un seul type de parenthèses ? Quelle est alors la complexité en temps et en espace ?
\item Dans l'épreuve de Google, on suppose disposer de $N$ types de parenthèses différentes. Comment traiter ce cas ?
\end{enumerate}
  
\end{exercice}






\begin{exercice}
  [Notation polonaise inverse]

La notation polonaise inverse ou notation postfixée consiste à placer les opérateurs \emph{après} les opérandes, en cela il diffère de la notion infixe.

Exemples.

\begin{center}
{\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|}
\hline
Notation infixe & Notation postfixe\\\hline
$1+2$& $1$ $2$ $+$\\\hline
$ 10 \div 0.5 $ & $10$  $0.5$ $\div$ \\\hline
$ 2\times 3 $  &  $2$ $3$ $\times$ \\\hline
$ (1+2)\times 3 $   & $1$ $2$ $+$ $3$ $\times$ \\\hline
$ 1+(2\times 3) $   & $1$ $2$ $3$ $\times$ $+$  \\\hline
$ (-2) - 3 $  & $2$  $-_1$ $3$ $-_2$ \\\hline
$ -(2 - 3) $& $2$ $3$ $-_2$ $-_1$ \\\hline

\end{tabular}
}
\end{center}

\textit{Remarques sur la notation postfixe.}
\begin{itemize}
\item Pas besoin de parenthèses
\item Il faut distinguer le $-$ unaire (noté ici $-_1$) du moins binaire (noté ici $-_2$). Le premier transforme un nombre en son opposé (exemple : $-2$) le second calcule la différence entre deux termes (exemple : $1-3$).
\end{itemize}


\begin{enumerate}
\item Convertir les expressions suivantes en notation polonaise inverse.%
\begin{multicols}{2}%
\begin{enumerate}%
\item $1+2+3+4+5+6$
\item $7 + (1+3)\times (2+3) $
\item $ 2\times 3 \times 5 \div 7  $
\item $ 3 + 9\times (5\times (7 + 2) +2)   $
 \end{enumerate}\end{multicols}

\item Convertir en notation usuelle les expressions postfixes suivantes.

\begin{multicols}{2}%
\begin{enumerate}
\item $2$ $3$ $-_1$ $-_2$
\item $1$ $2$ $3$ $+$ $\times$  
\item $1$ $2$ $3$ $+$ $-_1$ $\times$  
\item $7$ $5$ $3$ $2$ $1$ $+$ $\times$ $\div$ $+$
\end{enumerate}\end{multicols}

\end{enumerate}

\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{pythoncode}
In [1]: seq = "2 3 4 + *"

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

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{pythoncode}
operations = {
    '+':  operator.add, '-':  operator.sub,
    '*':  operator.mul, '/':  operator.truediv,
    '%':  operator.mod, '**': operator.pow,
    '//': operator.floordiv
}
\end{pythoncode}

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

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

Par exemple:

\begin{pythoncode}
In [1]: npi("3 2 7 9 - * 3 + 2 / +")
Out[1]: 2.5

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

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

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




\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{pythoncode}
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{pythoncode}
  
\end{exercice}



% \begin{exercice}[Pile d'exécution]
  
% \begin{multicols}{3}
% \begin{pythoncode}
% def m(x):
%     return m(x)

% def s(x):
%     return x+s(x+1)
    
% def p(x):
%     if x%3==1:
%         return x
%     else :
%         return p(x//3)

% def h(x):
%     return x+2
    
    
% def g(x):
%     return x*2
    
% def k(x):
%     s=0
%     for k in range(x):
%         s=s+g(h(k))
%     return s
    
% def u(x):
%     if x==1:
%         return 1
%     elif x%2==0:
%         return u(x//2)
%     else:
%         return v(x)
% def v(x):
%     return u(3*x+1)
 
    
% def fa(x):
%     if x==0:
%         return 1
%     else:
%         return x*fa(x-1)
        
% def fi(x):
%     if x<2:
%         return x
%     else:
%         return fi(x-1)+fi(x-2)
% \end{pythoncode}
% \end{multicols}

% \begin{enumerate}\item %
% Détaillez l'évolution de la pile d'exécution lors des calculs suivants~: \begin{multicols}{4}\begin{enumerate}\item \mintinline{python}{k(3)} \item\mintinline{python}{m(18)}\item\mintinline{python}{p(137)}\item\mintinline{python}{p(89)}\item  \mintinline{python}{u(7)}\item\mintinline{python}{fa(3)}\item\mintinline{python}{fa(-1)}\item\mintinline{python}{fi(5)}\end{enumerate}\end{multicols}
% \item Lors du calcul de \mintinline{python}{fi(5)}, combien de fois est-ce que \mintinline{python}{fi(2)} est-il calculé ?
% \item Pour chacune des fonctions $f$ ci-avant, déterminez l'ensemble des $n\in\mathbb{Z}$ pour lesquels le calcul de $f(n)$ termine.
%  \end{enumerate}
% \end{exercice}




\begin{exercice}[Morphisme de monoïde (ENS)]\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{pythoncode}
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{pythoncode}

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]{ring}
\end{center}
%\end{figure}

  
\end{exercice}


\begin{flushright}
  \textit{Merci à Jean-Loup \textsc{Carré} pour les exercices 5 et 6.}

\end{flushright}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2015_16"
%%% End: 
