\thumb

\begin{qcm}{Vérification de connaissances}{5} % titre , temps

Pour chacune des questions suivantes, plusieurs propositions de réponses sont faites dont une seule est correcte. Laquelle ?

\begin{questions}
\item On souhaite insérer dans une structure de données les différentes\linebreak hauteurs d'un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée en Python est:

\choix une liste;

\choix un dictionnaire;

\choix une pile;

\choix une file.

\item\resetchoix Dans une administration, on souhaite insérer dans une structure de\linebreak données les doléances reçues afin de les traiter selon leur ordre\linebreak d'arrivée. On aura alors plutôt intérêt à les enregistrer dans:

\choix une liste;

\choix un dictionnaire;

\choix une pile;

\choix une file.

\item\resetchoix Dans une association, on souhaite enregistrer une liste d'informations pour chaque adhérent : taille, poids, etc. La meilleure structure de\linebreak données pour cela est:

\choix une liste;

\choix un dictionnaire;

\choix une pile;

\choix une file.

\item\resetchoix Pour un logiciel, on doit enregistrer la liste des actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans:

\choix une liste;

\choix un dictionnaire;

\choix une pile;

\choix une file.
\end{questions}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[a]. Quand on observe l'évolution d'une quantité numérique, ce n'est en général pas pour sortir le premier ou le dernier élément en premier, donc pile et file sont à exclure. 

De plus, il n'y a pas d'association donc un dictionnaire est impossible. Seule la liste convient pour ce genre de problème.

\item Réponse \choix[d]. On enregistre les doléances selon le principe : \og première arrivée, première traitée \fg{} (\og first in, first out \fg, donc FIFO) ce qui\linebreak correspond à une file.

\item Réponse \choix[b]. Il s'agit ici d'enregistrer des associations, c'est-à-dire des éléments qui sont rattachés à d'autres (adhérents $\to$ informations) donc le dictionnaire est le plus adapté. Ici, les clés seront les adhérents et les valeurs seront les informations.

\begin{Remarque}
dans ce cas de figure, les informations pourront aussi être implémentées sous forme d'ensemble (\textit{set}) car il y en a plusieurs. On peut alors imaginer une entrée du dictionnaire principal sous la forme :
\Par
{\ttfamily
\{ 'Cécile' : \{ 157 , 48 , 17 \} \}
}
\Par
Ici, \og Cécile \fg{}  est une clé dont la valeur est l'ensemble \texttt{\{157,48,17\}}.
\end{Remarque}

\item Réponse \choix[c]. Il s'agit en effet d'enregistrer les actions selon le principe : \og dernière action faite, première action affichée \fg ( \og last in, first out \fg, donc LIFO), ce qui correspond à une pile.
\end{questions}

\begin{aretenir}
\begin{itemize}
\item Liste : succession de données accessibles sans contrainte.
\item Pile (LIFO) : on imagine une pile de pièces où la dernière mise est la première à pouvoir être prise.
\item \textbf{F}ile (\textbf{F}IFO) : on peut penser aux files d'attente, où la première personne arrivée est la première à être servie.
\end{itemize}
\end{aretenir}
\end{corrige}




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

\begin{exo}{Fabricant de tee-shirts}{\null}{1}{5} 
Un fabricant décide de créer des tee-shirts dont la taille peut-être  : XS, S, M, L, XL, XXL. À chaque taille son prix; il adopte le principe suivant : 8 \euro pour la taille XS et il ajoute 2 \euro en passant à la taille supérieure, jusqu'au XXL.

\begin{questions}
\item Implémenter en Python ces informations dans la structure de données la mieux adaptée.

\item Ce même fabricant décide de changer sa façon de fixer le prix de revente des tee-shirts. Ceux dont la taille est XS sont toujours à 8 \euro, mais cette fois-ci, pour passer d'une taille à la suivante, il ajoute au prix de la taille inférieure la moitié de sa racine carrée.

Par exemple, pour obtenir le prix des tailles S, il fait : 
\[
8 + \sqrt{8}\div2\approx9,41.
\]

Proposer un programme Python qui automatise ces calculs et les\linebreak enregistre dans une structure de données adaptée.
\end{questions}
\end{exo}

\begin{corrige}
Comme toujours, quand il s'agit d'associer deux entités (ici, taille et prix), on utilisera un dictionnaire.
\begin{questions}
\item On implémente le dictionnaire ainsi :

\Par

{\ttfamily
prix = \{ 

\qquad 'XS': 8, 'S': 10, 'M': 12, 'L': 14, 'XL': 16,

\qquad 'XXL': 18 

\}
}

\newpage

\item Dans cette question, il faut imaginer un programme qui effectue les\linebreak calculs au fur et à mesure. On peut donc par exemple stocker les tailles dans une liste, puis créer le dictionnaire élément par élément à partir de cette liste comme dans la proposition suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex01.py}
\end{listing}
\index{Python!get}

\Par

Ce qui donne :

{\ttfamily

\{

\quad 'XS': 8, 'S': 9.41, 'M': 10.94, 'L': 12.59,

\quad 'XL': 14.36, 'XXL': 16.25

\}
}

\Par

\begin{Remarque}
la racine carrée d'un nombre $x$ peut s'écrire \texttt{x ** 0.5} car $\sqrt{x} = x^{1/2}$. %On peut aussi fait appel au module \texttt{math} et à sa fonction \texttt{sqrt}, mais pour si peu, ce n'est pas nécessaire.
\end{Remarque}
\end{questions}
\end{corrige}


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

\begin{exo}{Séparation opérations / nombres}{\null}{1}{5} 
On considère une expression arithmétique \texttt{E} contenant des nombres et les opérations élémentaires (+, -, *, et /).


\'Ecrire une fonction Python \texttt{separe(E)} qui renvoie deux listes : la\linebreak première, nommée \texttt{nombres}, contenant les nombres de \texttt{E} et la seconde,\linebreak nommée \texttt{operations}, contenant les opérations de \texttt{E}.

Par exemple, si \texttt{E} = '3 + 5 * 7 - 2' alors \texttt{nombres = [3,5,7,2]} et \texttt{operations = ['+','*','-']}
\end{exo}

\begin{corrige}
Il suffit ici de parcourir l'expression \texttt{E} est d'effectuer des tests pour savoir si le caractère rencontré est un nombre (avec la méthode \texttt{isdigit} par exemple), une opération, ou autre chose (en l'occurrence, une espace).

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex02.py}
\end{listing}
\index{Python!isdigit}
\end{corrige}



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

\begin{exo}{Contrôle de parenthèses}{\null}{1}{10} 
On considère une expression arithmétique qui peut contenir des parenthèses.
\begin{questions}
\item \'Ecrire un algorithme permettant de vérifier que l'expression ne comporte pas d'erreur de parenthésage (s'il y a $n$ parenthèses ouvrantes, il faut qu'il y ait aussi $n$ parenthèses fermantes).

\item Implémenter en Python une fonction \texttt{controle(E)} qui renvoie \og True \fg{} si l'expression \texttt{E} est correctement parenthésée, et \og False \fg{} sinon.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Il s'agit ici de compter le nombre de parenthèses ouvrantes et fermantes. Rien de bien compliqué.

\begin{algorithme}{}
E est une expression arithmétique
f $\leftarrow$ 0 (nombre de parenthèses fermantes)
o $\leftarrow$ 0 (nombre de parenthèses ouvrantes)
Pour chaque élément i de E:
\quad Si i = "(":
\qquad o $\leftarrow$ o + 1
\quad Sinon:
\qquad Si i = ")":
\qquad\quad f $\leftarrow$ f + 1
\quad Fin du Si
\quad Si f = o:
\qquad Renvoyer True
\quad Sinon:
\qquad Renvoyer False
\end{algorithme}

\item Une implémentation possible est alors:

\begin{listing}{}{01-ex03.py}
\end{listing}
\end{questions}
\end{corrige}

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


\begin{exo}{Bon parenthésage ?}{\null}{1}{10} 
Une expression (algébrique ou arithmétique) est correctement parenthésée si d'une part, le nombre de parenthèses (et crochets) ouvrant.e.s et fermant.e.s est le même et si d'autre part les correspondances ne se croisent pas.

Par exemple, l'expression \og $\big[ 3 + (5 -7] * 3 \big)$ \fg{} n'est pas correctement\linebreak parenthésée car la parenthèse fermante ne peut pas venir après le crochet fermant.

\begin{questions}
\item \'Ecrire un algorithme qui s'aide d'une pile pour contrôler le bon\linebreak parenthésage d'une expression.

\item \'Ecrire en Python une fonction \texttt{is}\_\texttt{goodpar(E)} qui renvoie \og True \fg{} si l'expression \texttt{E} est correctement parenthésée, et \og False \fg{} dans le cas contraire.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Il s'agit ici d'empiler les crochets et parenthèses ouvrant.e.s et de dépiler quand on rencontre son équivalent fermant.e.

\Par

\begin{algorithme}{}
P est une pile vide
E est une expression

Pour chaque élément i de E:
\quad Si i = "(" ou i = "[":
\qquad i est empilé
\Break
\quad Si i = ")":
\qquad Si la tête de P est "(":
\qquad\quad On dépile "("
\qquad Sinon:
\qquad\quad Renvoyer False
\qquad Fin du Si (tête de P)
\quad Fin du Si i = ")"

\quad Si i = "]":
\qquad Si la tête de P est "]":
\qquad\quad On dépile "["
\qquad Sinon:
\qquad\quad Renvoyer False
\qquad Fin du Si (tête de P)
\quad Fin du Si i = "]"

Si P est vide:
\quad Renvoyer True
\end{algorithme}

\Par

\item Une implémentation de cet algorithme en Python est:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex04.py}
\end{listing}

\begin{Remarque}
on aurait pu aussi écrire \texttt{pile.pop()} au lieu de \texttt{del pile[-1]}.
\end{Remarque}
\index{Python!del}
\end{questions}
\newpage
\end{corrige}

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

\begin{exo}{Implémentation d'une file}{\null}{1}{15} 
Le module \texttt{collections}, avec \texttt{deque}, permet d'implémenter une file. Ainsi, les instructions :

\Par

{\ttfamily
\pychevrons f = deque()

\pychevrons f.appendleft(1)

\pychevrons f.appendleft(2)

\pychevrons print(f)
}

\Par

enfile la valeur \og 1 \fg{} puis la valeur \og 2 \fg, et affiche : \og \texttt{deque([2,1]} \fg, qui représente la file.

\Par

\'Ecrire une fonction \texttt{enfile(liste,tuple)} qui admet pour arguments une liste \texttt{liste} (qui nous sert de file) et un tuple regroupant les éléments à enfiler dans l'ordre que l'on veut.

Par exemple,

\Par

{\ttfamily

\pychevrons f = []

\pychevrons f = enfile( f , (1,2) )

\pychevrons f = enfile( f , 3)
}

\Par

retourne la liste \texttt{[3,2,1]} (on a enfilé \og 1 \fg, puis \og 2 \fg, et enfin \og 3 \fg).
\end{exo}

\begin{corrige}
Une implémentation possible est la suivante :

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex05.py}
\end{listing}
\index{Python!isinstance}

\Par

Ainsi, on aura par exemple :

\Par

\hrulefill

{\ttfamily

\pychevrons f = [2,1] \textit{\# On initialise la file comme une liste}

\pychevrons f = enfile(f,(3,4)) \textit{\# On enfile 3, puis 4}

\pychevrons f = enfile(f,5) \textit{\# puis 5}

\pychevrons f

[5, 4, 3, 2, 1]
}

\hrulefill
\end{corrige}


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

\begin{exo}{D'une liste à un dictionnaire}{\null}{1}{15} 
\'Ecrire en Python une fonction \texttt{list}\_\texttt{to}\_\texttt{dico(liste)} qui admet en\linebreak argument une liste de la forme \texttt{[clé1,valeur1,clé2,valeur2,...]} et qui retourne le dictionnaire correspondant de la forme:
\begin{center}
\texttt{\{ clé 1 : valeur 1, clé 2 : valeur 2, ... \}}.
\end{center}
\end{exo}

\begin{corrige}
Il s'agit ici de parcourir la liste donnée en argument en sautant un élément sur deux afin de mettre l'élément sauté en valeur.

Une fonction possible est alors la suivante:

\begin{listing}{}{01-ex06.py}
\end{listing}

\newpage

Ce qui donne par exemple:

\Par

\hrulefill

{\ttfamily

\pychevrons L = [ 'France' , 'Paris' , 

... 'Angleterre' , 'Londres' ,

... 'Espagne' , 'Madrid' , 

... 'Allemagne' , 'Berlin' ]


\pychevrons print( liste\_to\_dico(L) )

\{'France': 'Paris', 

'Angleterre': 'Londres', 

'Espagne': 'Madrid', 

'Allemagne': 'Berlin'\}
}

\hrulefill
\end{corrige}


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

\begin{exo}{Chiffrement}{\null}{2}{15} 
La fonction \texttt{ord(<caractère>)} renvoie le point de code Unicode du\linebreak caractère spécifié. Par exemple, \og \texttt{ord('f')} \fg{} renvoie la valeur 102.

La fonction inverse est \texttt{chr(<entier>)}. Par exemple, \og \texttt{chr(102)} \fg{} renvoie \og f \fg.

Pour calculer $a$ modulo $n$, on utilise la syntaxe \og a \% n \fg.

Pour chiffrer un mot $M$, on décide de procéder ainsi: pour chaque\linebreak caractère $c$ de $M$,

\begin{itemize}
\item on calcule $3 \times \text{ord}(c) - 61$ modulo 91, puis on ajoute 33. Le résultat est noté $r$;

\item on trouve ensuite le caractère correspondant à $r$ avec \texttt{chr(r)} : on note ce caractère $c_1$.

\item si $r$ est pair, on calcule $2 \times \text{ord}(c) - 31$ modulo 91 puis on ajoute 33, et on trouve le caractère correspondant à ce résultat, noté $c_2$. Dans ce cas, le caractère $c$ est chiffré en $c_1c_2$;

\item si $r$ est impair, on calcule $2 \times \text{ord}(c) - 32$ modulo 91 puis on ajoute 33, que l'on transforme en son caractère $c_2$, puis on calcule $3 \times \text{ord}(c) - 60$ modulo 91 puis on ajoute 33, que l'on transforme en son caractère $c_3$. Le caractère $c$ est alors chiffré en $c_1c_2c_3$.
\end{itemize}

Par exemple, pour chiffrer \og P \fg{} :

\begin{itemize}
\item \texttt{ord('P') = 80}, donc on calcule :
\[
3 \times 80 - 61 \mod 89 = 179 \mod 91 = 88,
\]
puis on ajoute 33:
\[
r = 88+33 = 121,
\]
qui est impair et qui correspond à \texttt{chr(121)} = \og y \fg. Donc $c_1$ correspond au caractère: \og y \fg;

\item $r$ est impair donc on calcule:
\[
2\times 80-32\mod 91 = 37,
\]
puis on ajoute 33:
\[
37+33=70,
\]
qui correspond à $c_2 = \text{chr}(70) = $ \og F \fg{} ;

\item ensuite, on calcule:
\[
3\times80-60\mod 91=89
\]
puis on ajoute 33:
\[
89+33=122
\]
qui correspond à $c_3 = \text{chr}(122) = $ \og z \fg;

\item \og P \fg{} est donc chiffré en \og yFz \fg.
\end{itemize}

Afin d'optimiser le temps de cryptage, on souhaite implémenter une structure de données nous permettant d'obtenir le cryptage de tous les caractères dont le point de code Unicode est compris entre 32 et 122 compris.

\begin{questions}
\item Implémenter la structure de données adéquate.
\item Chiffrer le message : \og informatique \fg.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item 
\begin{methode}
On peut ici créer un dictionnaire où les clés seront les caractères dont le point de code Unicode est compris entre 32 et 122 et où les valeurs\linebreak seront les résultats des chiffrements.
\end{methode}

On obtient une implémentation comme celle-ci:

\begin{listing}{}{01-ex07-1.py}\end{listing}
\index{Python!chr}

\Par

Ici, \texttt{crypt} est un dictionnaire auquel on pourra faire appel lors de tout chiffrement.

\vfil\hfil\textit{Suite de l'exercice page suivante.}

\newpage

\item On peut utiliser le programme suivant:

\begin{listing}{}{01-ex07-2.py}\end{listing}

\Par

On obtient alors le résultat suivant :

\begin{center}
\includegraphics{026_02-exo-chiffrement}
\end{center}
\end{questions}

\nathanlive{prog}{Téléchargez le programme complet.}% \texttt{[01-ex07.py]}.}
\end{corrige}


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

\begin{exo}{Labyrinthe}{\null}{2}{15} 
\index{Labyrinthe}
Une manière d'implémenter un labyrinthe rectangulaire est de découper le rectangle en cases, puis de définir pour chaque case s'il y a un mur en haut, en bas, à gauche et à droite avec des booléens.

\Par

\begin{figure}
\begin{center}
\includegraphics{015_02-exo-labyrinthe}
\figcaption{Labyrinthe à implémenter en Python}
\end{center}
\end{figure}

\Par

Utiliser une structure de données adaptée afin d'implémenter ce labyrinthe selon cette façon de concevoir les choses.

On ne demande pas d'implémenter tout le labyrinthe, mais d'expliquer\linebreak comment on ferait, en donnant l'exemple de la première case (en haut à gauche).
\end{exo}


\begin{corrige}
\begin{methode}
On peut représenter la grille par une matrice \texttt{L}, où \texttt{L[i][j]} représente la case de la $(i+1)$-ième ligne en partant du haut (par exemple) et \mbox{$(j+1)$-ième} colonne en partant de la gauche (par exemple).

Ensuite, la valeur de chaque cellule est un dictionnaire dont les clés seront par exemple quatre booléens \texttt{top}, \texttt{bottom}, \texttt{left} et \texttt{right} représentant la présence ou l'absence de murs respectivement  en haut, en bas, à gauche et à droite. 
\end{methode}

On aura ainsi :

\Par

{\ttfamily
M[0][0] = \{  'top' : True , 'bottom' : False , 

\hspace*{2cm} 'left' : False , 'right' : True \}
}

\Par

Cette implémentation a le mérite d'être claire, mais peu pratique car assez longue à faire. Ainsi, pour alléger, on peut opter pour une liste de booléens dans chaque cellule, en convenant de garder le même ordre (mais l'ordre peut différer selon la logique de la personne qui programme). On aura alors :

\Par

{\ttfamily

M[0][0] = [ True , False , False , True]
}

\Par

ce qui est bien plus simple et rapide à écrire, mais cette redondance introduit un risque de discordance des informations, souvent à l'origine de bugs dans la pratique.
\Par\enlargethispage*{3em}
\textit{Remarque}: nous verrons plus tard qu'il existe d'autres façons, peut-être plus pratiques, de représenter un labyrinthe, notamment à l'aide d'une \textit{classe} (voir le chapitre sur la Programmation Orientée Objet).
\end{corrige}

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

\begin{exo}{Suites imbriquées}{\null}{2}{20} 
On considère deux suites numériques $(u_n)$ et $(v_n)$ définies par:
\[
\forall n\in\N,\quad
\begin{cases}
u_0 = 5,\ u_1 = 3\\
u_{n+2} = 2u_n + 3u_{n+1}
\end{cases}
\qquad\text{et}\qquad
\begin{cases}
v_0 = 2,\ v_1 = 4\\
v_{n+2} = \dfrac{v_n}{v_{n+1}} + \dfrac{u_{n+2}}{u_{n+1}}
\end{cases}
\]

\begin{questions}
\item Vérifier que $u_2=19$ et $v_2=\dfrac{41}{6}$.
\item \'Ecrire un premier programme en Python qui permet d'afficher tous les termes des deux suites jusqu'à $n=20$ à l'aide d'une boucle. 

Quelle est sa complexité ?

\item \'Ecrire un second programme qui fait la même chose que le premier, mais à l'aide d'une structure de données adaptée. 

Quelle est sa complexité ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Cette question est uniquement posée afin de voir si vous avez compris le mode de calcul des deux suites.
\begin{itemize}
\item $u_2 = u_{0+2} = 2u_0 + 3u_1 = 2 \times 5 + 3 \times 3 =19$.

\item $v_2 = v_{0+2} = \dfrac{v_0}{v_1}+\dfrac{u_2}{u_1}=\dfrac{2}{4}+\dfrac{19}{3}=\dfrac{41}{6}$.
\end{itemize}

\item Le premier programme peut ressembler à celui-ci:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex08-1.py}
\end{listing}

\Par

Dans ce genre de cas, où les termes d'une suite se calculent non pas en fonction du seul précédent mais du précédent et du pénultième, il faut nécessairement faire intervenir une variable transitoire.

C'est la raison pour laquelle nous avons ici choisi de calculer d'abord la valeur de deux variables transitoires \texttt{u} et \texttt{v}, qui jouent le rôle de $u_{n}$ et $v_{n}$, puis de faire les affectations nécessaires pour la boucle suivante, à savoir dans un premier temps:
\begin{itemize}
\item \texttt{u}\_\texttt{penult}, qui joue le rôle de $u_{n-2}$, devient \texttt{u}\_\texttt{preced}, qui joue le rôle de $u_{n-1}$,
\item et enfin remplacer \texttt{u}\_\texttt{preced} par la valeur du terme fraîchement\linebreak calculé \texttt{u}
\end{itemize}

car en effet, d'une boucle à l'autre, $u_{n-2}$ devient $u_{n-1}$ et $u_{n-1}$ devient $u_{n}$.

Le raisonnement est analogue pour les termes de la suite $(v_n)$.

On voit ainsi s'afficher:

\Par

{\ttfamily
u( 2 ) =  19  ; v( 2 ) :  6.833333333333333

u( 3 ) =  63  ; v( 3 ) :  3.9011553273427473

u( 4 ) =  227  ; v( 4 ) :  5.3547924599257275

$\vdots$

\newpage

u( 18 ) =  11975495755  ; v( 18 ) :  4.561936982933018

u( 19 ) =  42651360591  ; v( 19 ) :  4.561326557332556

u( 20 ) =  151905073283  ; v( 20 ) :  4.56168663914045
}

\Par

La complexité de ce programme est linéaire (13 affectations et opérations élémentaires par boucle, donc une complexité égale à $13n$). On dit que la complexité est en $O(n)$, si $n$ représente l'indice du dernier terme affiché.

\item Dans cette question, on souhaite utiliser une structure de données. Il s'agit donc ici d'enregistrer la valeur des termes successifs dans une liste car cette dernière semble être la plus adaptée à nos exigences.

Un programme possible est alors:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex08-2.py}
\end{listing}

\Par

Ce programme est plus intuitif et plus court que le premier.

De plus, sa complexité, bien que linéaire aussi, est égale à $9n$: pour chaque terme, il y a 3 opérations plus une affectation dans la liste, soit 4 opérations, et une affectation pour la variable \texttt{i}.

Ce dernier programme est donc meilleur sous tous les angles : plus\linebreak rapide, plus court et plus explicite que le premier.
\end{questions}
\end{corrige}





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

\begin{exo}{Expressions postfixées}{\null}{3}{20} 
\index{Postfixées (expressions)}
On ne considère dans cet exercice que les expressions numériques contenant les quatre opérations élémentaires (addition, soustraction, multiplication et\linebreak division).

La notation postfixée consiste à mettre les opérations arithmétiques après leurs deux arguments. Ainsi, l'opération $a \bigstar b$, où $\bigstar \in \{ + ; - ; \times ; \div \}$, a pour notation postfixée : $a b \bigstar$.

1\ier{} exemple : l'expression 3 * ((4 + 5) + 6) peut s'écrire \og 3 4 5 + 6 + * \fg (mais aussi : \og 4 5 + 6 + 3 * \fg{} ou encore \og 3 6 4 5 + + * \fg). 

2\ieme{} exemple : (4 + (5 + 6)) * 3 peut s'écrire \og 4 5 6 + + 3 * \fg.

\begin{questions}
\item \'Ecrire un algorithme utilisant une pile pour effectuer une opération en notation postfixée.

\item Implémenter l'algorithme en Python en définissant une fonction \texttt{calcul(E)}, où \texttt{E} est l'expression en notation postfixée dans laquelle chaque nombre ou symbole est séparé par une espace.
\end{questions}
\end{exo}


\begin{corrige}
\begin{questions}
\item Un algorithme possible est le suivant :

\begin{algorithme}{}
P est une pile 
E est une expression en notation postfixée

Pour chaque élément i de E:
\quad Si i est un nombre:
\qquad Empiler i dans P
\quad Sinon:
\qquad Dépiler les deux premières valeurs v1 et v2 de P
\qquad Effectuer l'opération i sur v1 et v2
\qquad Empiler le résultat dans P
\quad Fin du Si
\end{algorithme}

\newpage

\item Une implémentation possible de cette fonction est la suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex09.py}
\end{listing}
\index{Python!del}
\index{Python!str}
\index{Python!split}

\begin{itemize}
\item On commence par découper la chaîne de caractères représentant\linebreak l'expression à l'aide de la méthode \texttt{split(' ')}, qui va donc créer une liste dont les éléments sont ceux séparés par une espace dans E. Il s'agit donc ici des nombres et des opérations.

\item On définit ensuite une liste \texttt{liste}\_\texttt{nombres} qui va nous servir de pile.

\item On parcourt ensuite la liste \texttt{expr}: si l'élément n'est pas une opération alors on enregistre cet élément dans la liste \texttt{liste}\_\texttt{nombres}; sinon, on effectue l'opération rencontrée entre les deux éléments de la liste \texttt{liste}\_\texttt{nombres}.

\item Une fois l'opération effectuée, on efface les deux premiers éléments de la pile, donc les deux derniers éléments de la liste \texttt{liste}\_\texttt{nombres} (avec \texttt{del}) puis on ajoute à cette liste le résultat de l'opération trouvé.

\item À la fin, la pile est composée d'un élément qui est le résultat de\linebreak l'opération.
\end{itemize}
\end{questions}
\end{corrige}


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

\begin{exo}{Permutations}{\null}{3}{30} 
On considère un ensemble $E=\{e_1;e_2;e_3;\ldots;e_8;e_9\}$ de 9 éléments.

On définit alors une application $\sigma$ qui transforme $E$ en l'ensemble :

\[
E_1=\{e_5;e_9;e_3;e_6;e_1;e_4;e_2;e_7;e_8\}.
\]

$\sigma$ est appelée une \textit{permutation}, et on peut noter :
\[
E_1 = \sigma(E).
\]

Une notation matricielle de $\sigma$ est alors:
\[
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
5 & 9 & 3 & 6 & 1 & 4 & 2 & 7 & 8
\end{pmatrix}
\]

car $e_1$ se transforme en $e_5$, $e_2$ en $e_9$, etc.

\Par

Pour tout entier naturel $n$, on note $E_n$ l'ensemble: 
\[
E_n = \sigma^n(E) = \sigma(\sigma(\ldots\sigma(E)\ldots)),
\]

où $\sigma$ a été appliquée $n$ fois à $E$.

Par exemple, $E_2 = \sigma\big(\sigma(E)\big)$.

\begin{questions}
\item \'Ecrire une fonction \texttt{sigma(E,n)} retournant une liste des éléments de $E_n$.
Par exemple, si:
\begin{center}
\texttt{E = [1,2,3,4,5,6,7,8,9]}
\end{center}
alors:
\begin{center}
\texttt{sigma(E,1) = [5,9,3,6,1,4,2,7,8]}\\
\texttt{sigma(E,0) = [1,2,3,4,5,6,7,8,9]}.
\end{center}

\item Un théorème mathématique nous permet de dire qu'il existe un entier $n$ tel quel $E_n=E_0$.

\'Ecrire un programme en Python permettant de trouver le plus petit entier $n$ tel que $E_n=E_0$.

\item Un \textit{cycle} est un objet mathématique qui s'écrit par exemple $(5,2,3)$ et qui signifie que l'élément 5 d'un ensemble devient l'élément 2 de cet\linebreak ensemble, puis que l'élément 2 devient l'élément 3, et enfin que l'élément 3 devient l'élément 5, tout en conservant les autres éléments. Ainsi, sur un ensemble à 5 éléments,
\[
(5,2,3) = \begin{pmatrix}
1&2&3&4&5\\
1&3&5&4&2
\end{pmatrix}.
\]
Si $\sigma$ et $\tau$ sont deux cycles, on note $\sigma \circ \tau$ le cycle correspondant au fait que l'on ait appliqué le cycle $\tau$ puis le cycle $\sigma$ à un ensemble.

\begin{questions}
\item Vérifier que sur un ensemble à 8 éléments:
\[
(4,8)\circ(8,5)\circ(5,1)=(1,4,8,5).
\]

\item \'Ecrire en Python une fonction \texttt{image(sigma,tau,n)} qui admet deux cycles en arguments et un entier (le nombre d'éléments d'un ensemble) et qui renvoie sous forme de liste la permutation\linebreak correspondant à $\sigma\circ\tau$.

Vérifier que :

\begin{center}
\texttt{image( (1,3,4,5,8,6) , (2,7) , 8 )}
\end{center}

retourne la liste :

\begin{center}
\ttfamily
[3,7,4,5,8,1,2,6].
\end{center}
\end{questions}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item 
\begin{methode}
Il faut d'abord définir une fonction \texttt{permut(liste)} qui renvoie une liste dont les éléments sont ceux de l'argument \texttt{liste} permutés selon la permutation $\sigma$.

Ensuite, on définit la fonction \texttt{sigma(E,n)} qui retourne \texttt{E} si $n=0$ et sinon, qui calcule \texttt{permut(E)} $n$ fois (à l'aide d'une boucle).
\end{methode}

Cela donne par exemple le programme suivant:

\begin{listing}{}{01-ex10-1.py}\end{listing}

\item L'idée ici est de définir deux listes identiques \texttt{E} et \texttt{F} : la première va\linebreak servir de référence (c'est l'ensemble initial) et la seconde sera\linebreak transformée par $\sigma$ tant que le résultat ne sera pas identique à \texttt{E}.

Cela donne :\enlargethispage*{\baselineskip}

\begin{listing}{}{01-ex10-2.py} \end{listing}
\Par
On trouve $n=4$.

\newpage


\item
\begin{questions}
\item On doit partir du dernier cycle : $(5,1)$ signifie que l'on permute les éléments 1 et 5 :
\[
\begin{pmatrix}
1&2&3&4&5&6&7&8\\
5&2&3&4&1&6&7&8
\end{pmatrix}
\]
$(8,5)$ signifie que l'on permute les éléments 8 et 5 du nouvel\linebreak ensemble obtenu après la première permutation:
\[
\begin{pmatrix}
1&2&3&4&5&6&7&8\\
5&2&3&4&1&6&7&8\\
5&2&3&4&8&6&7&1
\end{pmatrix}
\]
Et enfin, $(4,8)$ signifie que l'on permute les éléments 4 et 8, ce qui donne:
\[
\begin{pmatrix}
1&2&3&4&5&6&7&8\\
5&2&3&4&1&6&7&8\\
5&2&3&4&8&6&7&1\\
5&2&3&1&8&6&7&4
\end{pmatrix}
\]
Au final, on obtient la permutation $\begin{pmatrix}
1&2&3&4&5&6&7&8\\
5&2&3&1&8&6&7&4
\end{pmatrix}$, ce qui donne : $(1,5,8,4)$ (car les autres éléments ne sont pas\linebreak permutés).

\item Un programme possible est le suivant:

\begin{listing}{}{01-ex10-3-1.py}\end{listing}

\newpage
\begin{listing}{}{01-ex10-3-2.py}\end{listing}

\Par

Nous avons opté ici pour créer une fonction \texttt{cycle}\_\texttt{to}\_\texttt{permut} qui transforme un cycle en une permutation (définie par une liste) afin de nous ramener à ce qui a été fait précédemment. 

Puis nous nous sommes inspirés de la fonction \texttt{permut} de la\linebreak question précédente pour en créer une autre avec un argument en plus (la permutation).

Enfin, nous avons créé la fonction principale \texttt{image} qui permet d'obtenir la permutation finale.

Pour vérifier l'exactitude du programme, on essaie avec les cycles donnés dans l'énoncé :

\Par

\hrulefill

{\ttfamily
\pychevrons sigma , tau = (1,3,4,5,8,6) , (2,7)

\pychevrons image(sigma,tau,8)

[3, 7, 4, 5, 8, 1, 2, 6]
}

\hrulefill

Cela signifie que:
\[
(1,3,4,5,8,6)\circ(2,7)=\begin{pmatrix}
1&2&3&4&5&6&7&8\\
3&7&4&5&8&1&2&6
\end{pmatrix}.
\]
\end{questions}

\end{questions}

\begin{plusloin}
Les permutations sont utiles dans la théorie du Rubik's Cube.

C'est notamment à l'aide de permutations que l'on peut démontrer que la répétition de certains mouvements conduit à l'état initial.

\Par

\begin{figure}
\begin{center}
\includegraphics{032_sdd-rubik}
\end{center}
\end{figure}

\Par

Par exemple, si le mouvement consiste à tourner la face droite de 90$^\circ$ vers le haut, puis de tourner la face du haut de 90$^\circ$ vers la droite, si on le répète 63 fois, on obtient la configuration initiale.
\end{plusloin}

\Par

\nathanlive{prog}{Téléchargez le programme complet.}% \texttt{[01-ex10-C.py]}.}
\end{corrige}


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

\sectionnn{Packing et unpacking}

\begin{exo}{Longueur d'une ligne brisée}{\null}{1}{5} 
Nous disposons du dictionnaire suivant:

\Par

{\ttfamily
points = \{ 'A':(-2,4), 'B':(1,-2), 'C':(3,7), 'D':(5,-3) \}
}

\Par

Compléter le programme page suivante afin qu'il retourne la longueur\linebreak $AB + BC + CD$.

\newpage
\begin{listing}{}{01-ex11.py}\end{listing}
\end{exo}

\begin{corrige}
Le programme complété est le suivant:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex12.py}\end{listing}

\Par

Explications:

\begin{itemize}
\item dans la fonction \texttt{longTotale}, on commence par initialiser la variable \texttt{somme} à 0 : elle représentera la somme totale demandée;

\item ensuite, on initialise un booléen \texttt{prem} à \texttt{True}: il ne sert ici qu'à indiquer le premier point;

\item on parcourt ensuite le dictionnaire passé en arguments de la fonction avec la ligne :\\
\texttt{for key,value in points.items()}

\item si nous sommes sur le premier point, indiqué à l'aide du booléen, nous définissons la variable \texttt{previous} comme étant les coordonnées du point sur lequel nous sommes, et nous passons le booléen à \texttt{False} pour indiquer que les points suivants ne sont pas le premier point;

\item si nous ne sommes pas sur le premier point alors nous incrémentons la variable \texttt{somme} de la longueur entre le point précédent (dont les coordonnées sont stockées dans la variable \texttt{previous}) et le point actuel.
\newpage
Nous utilisons ici l'unpacking lors de l'appel de la fonction \texttt{longueur} car les variables sont des tuples;


\item ensuite, nous définissons \texttt{previous} comme étant les coordonnées du point actuel (qui représenteront ainsi les coordonnées du point précédent quand nous serons sur le point suivant);

\item quand le parcours du dictionnaire est fini, nous retournons la valeur contenue dans la variable \texttt{somme}.
\end{itemize}
\end{corrige}

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

\begin{exo}{Somme de nombres}{\null}{1}{5} 
\'Ecrire en Python une fonction \texttt{somme}, admettant un nombre indéfini\linebreak d'arguments numériques, qui calcule la somme de tous les nombres mis en argument.

Par exemple, \texttt{somme(1,2,3,4,5,6,7,8,9)}  doit retourner \og 45 \fg.
\end{exo}


\begin{corrige}
Le packing explicite va nous servir pour écrire la fonction demandée :

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex13.py}\end{listing}

\Par

Dans notre fonction, \texttt{nombres} représente une liste grâce à l'opérateur \textit{splat} (l'étoile).

Ainsi, il ne reste plus qu'à parcourir cette liste et à ajouter chaque élément.
\end{corrige}

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

\begin{exo}{Convertir une liste en dictionnaire}{\null}{1}{10} 
\'Ecrire une fonction \texttt{convertToDico} qui admet un nombre indéfini de mots en argument et qui retourne un dictionnaire dont les clés sont nommées\linebreak \og clé 1\fg, \og clé 2 \fg, ... et dont les valeurs sont les mots passés en arguments.

Par exemple, \texttt{convertToDico("un","cheval","blanc")} retournera un\linebreak dictionnaire de la forme :

\Par

{\ttfamily

\{ "Clé 1" : "un",\\
"Clé 2" : "cheval",\\
"Clé 3" : "blanc" \}
}
\end{exo}

\begin{corrige}
Voici une fonction possible :

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex14.py}\end{listing}
\newpage
\end{corrige}

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

\begin{exo}{Calculs mathématiques}{\null}{1}{10} 
On souhaite que la ligne :
\begin{center}
\texttt{discr(a = 1, b = 2, c = -3)}
\end{center}
appelle une fonction qui affiche la valeur $b^2-4ac$.

\Par

Proposer une telle fonction en utilisant la méthode du packing, c'est-à-dire une fonction définie par:

\Par

{\ttfamily

def discr(**coefs):\\
\hspace*{2em} ...
}
\end{exo}

\begin{corrige}
Une fonction possible est la suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex15.py}\end{listing}

\Par

Les arguments de la fonction \texttt{discr} étant nommés respectivement \texttt{a}, \texttt{b} et \texttt{c}, en passant \texttt{**coefs} en argument de la fonction \texttt{discr}, on crée un dictionnaire dont les entrées sont nommées \texttt{a}, \texttt{b} et \texttt{c}, et dont les valeurs sont celles des variables \texttt{a}, \texttt{b} et \texttt{c}. C'est pour cela que l'on écrit \og \texttt{a = coef['a']} \fg{} dans la fonction (et de même pour les autres variables).
\end{corrige}

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

\begin{exo}{Remplacements}{\null}{1}{10} 
Nous disposons de 50 fichiers :

\begin{center}
fichier1.txt, fichier2.txt, ... , fichier50.txt
\end{center}

dans lesquels nous souhaitons remplacer le mot \og dinosaure \fg{} par \og brachiosaure \fg.


On suppose que l'on a déjà à notre disposition la liste :

\Par

{\ttfamily

L = [ 

\qquad "fichier1.txt" ,

\qquad "fichier2.txt",

\qquad ... ,

\qquad "fichier50.txt" 

]
}

\Par

contenant les noms de tous les fichiers.

Nous souhaitons alors créer une fonction \texttt{remplace} qui permet d'effectuer cette tâche en écrivant:

\begin{center}
\texttt{remplace("dinosaure","brachiosaure",*L)}
\end{center}
\Par

Proposer une fonction.
\end{exo}

\begin{corrige}
Voici une proposition:

\nathanlive{progmargin}{}
\begin{listing}{}{01-ex16.py}\end{listing}

\Par

Dans cette fonction, on parcourt la liste \texttt{args} avec la boucle : \texttt{for fichier in args}. Dans cette boucle, on ouvre le fichier courant en mode lecture (\texttt{'r'} pour \textit{read}) et on crée un alias \texttt{f} pour ce fichier. Pour chaque ligne parcourue, on remplace le mot contenu dans la variable \texttt{original} par celui contenu dans \texttt{remplacant}. La variable \texttt{content} contient ainsi les lignes modifiées.

À la sortie de la boucle, il ne reste plus qu'à enregistrer le fichier (\texttt{'w'} pour \textit{write}) dont le contenu est celui de la variable \texttt{content}.

\end{corrige}


\thumb
\AfficheCorrige
