\chapter{Méthodes de\\programmation}

\enlargethispage*{5em}
\begin{exointro}{Lycée François Villon, Les Mureaux}
\begin{questions}
\item Qu'affiche le programme suivant ?\vspace*{-0.5em}
\begin{listing}{}{03-01.py}\end{listing}

\item On modifie la première fonction de la manière suivante:\vspace*{-0.5em}
\begin{listing}{}{03-02.py}\end{listing}
\Par
Qu'affiche alors le programme principal précédent ?

Qu'est-ce que cette modification a permis de mettre en relief ?
\end{questions}
\vspace*{-1em}
\end{exointro}
\newpage



\section{Les différents types de variables}

\subsection{Les variables locales}
\index{Variables locales}
\index{Locales (variables)}

\begin{defin}
Une \textit{variable locale} est une variable qui n’existe que durant l’exécution de la fonction l’ayant créée.
\end{defin}

\begin{Exemple}
considérons le programme suivant:
\begin{listing}{}{03-03.py}\end{listing}

\Par

Quand on l'exécute, il s'affiche le message suivant:

\Par

{\ttfamily
La variable 'valeur' n'existe pas encore.

'valeur' vaut 10.

NameError: name 'valeur' is not defined
}

\Par

Dans la fonction \texttt{maFonction}, on \textit{essaie} (\og \texttt{try} \fg) d'afficher la valeur contenue dans la variable \texttt{y}. Si cette variable n'existe pas (\og \texttt{except NameError} \fg), on affiche un message le spécifiant.

Ensuite, on affecte la valeur passée en paramètre à la variable \texttt{y}, puis on affiche cette valeur.

On appelle alors la fonction avec le paramètre \og 10 \fg.

\Par

Pour finir, on demande d'afficher la valeur de la variable \texttt{y} à l'extérieur de la fonction, mais cette variable n'est pas reconnue (car nous sommes justement à l'extérieur de la fonction).

La variable \texttt{y} est \textit{locale} : elle n'existe que dans la fonction définie, et pas ailleurs.
\end{Exemple}
\enlargethispage*{\baselineskip}

\subsection{Les variables globales}
\index{Variables globales}
\index{Globales (variables)}

\vspace*{-1em}
\begin{defin}
Une \textit{variable globale} est une variable déclarée à l'extérieur d'une fonction et pouvant être utilisée n'importe où dans le programme.
\end{defin}

En Python, une variable \texttt{var} déclarée hors de toute fonction est une variable \textit{globale}. Elle est alors accessible -- en lecture uniquement -- dans toute fonction. Pour qu’elle puisse être accessible également en écriture dans une fonction, il faut utiliser explicitement la déclaration \texttt{global var}.

Hors des fonctions, les variables globales sont accessibles en lecture et en écriture.

\vspace*{-1em}
\begin{Exemples}
\begin{minipage}[t]{0.55\linewidth}
\begin{listing}{Partie 1}{03-04.py}\end{listing}
\end{minipage}
\hfill
\begin{minipage}[t]{0.4\linewidth}
\begin{listing}{Partie 2}{03-05.py}\end{listing}
\end{minipage}
\end{Exemples}

Dans la partie 1, la variable \texttt{a} est déclarée à l'extérieur de la fonction \texttt{afficheA()}; pourtant, la fonction affiche bien sa valeur.

Dans la partie 2, \texttt{a} est toujours déclarée à l'extérieur des fonctions, mais il est nécessaire de la référencer avec le mot-clé \texttt{global} pour pouvoir modifier sa valeur.

\vspace*{-1.5em}
\section{Programmation impérative}
\index{Programmation!impérative}

\vspace*{-1em}
\begin{defin}
La \textit{programmation impérative} décrit les différentes opérations sous forme de suites d'instructions exécutées par la machine sur laquelle est lancé le\linebreak programme pour modifier l'état du programme.
\end{defin}

C'est le type de programmation (ou \textit{paradigme} de programmation) le plus utilisé. La plupart des processeurs sont construits de manière à exécuter des suites d'instructions.

\enlargethispage*{4em}
\vspace*{-2mm}
\begin{defin}[effet de bord]
\index{Effets de bord}
Un \textit{effet de bord} (\textit{side effect}) est une modification provoquée par une fonction sur une dépendance partagée (variable ou périphérique par exemple) autre que celle explicitement spécifiée lors de l'appel de cette fonction.
\end{defin}

Généralement, un effet de bord aboutit à des valeurs ou des comportements non prévus.


\begin{solintro}
\begin{questions}
\item Le programme affiche successivement : \og 250 \fg{} (résultat obtenu avec l'instruction \texttt{calculSomme(50)}) et \og 195 \fg{} (résultat obtenu avec l'instruction \texttt{calculDiff(5)}).
\vspace*{-5mm}
\Break
\item Le même programme principal donnera après modification : \og 250 \fg{} (résultat obtenu avec l'instruction \texttt{calculSomme(50)}) et \og 245 \fg{} (résultat obtenu avec l'instruction \texttt{calculDiff(5)}).
\Par
On constate que la fonction \texttt{calculSomme()} continue de fonctionner et
retourne le même résultat. En revanche, la fonction \texttt{calculDiff()}, qui
n'a pourtant pas été modifiée, retourne une erreur de calcul ! 

Cela met en relief le fait que \texttt{calculDiff()} est \textit{victime} d'un effet de bord suite à la modification de \texttt{calculSomme()}.
\end{questions}
\end{solintro}

\vspace*{-1em}
\section{Programmation fonctionnelle}
\index{Programmation!fonctionnelle}

\vspace*{-1em}
\subsection{Principe de base}

\begin{defin}
La \textit{programmation fonctionnelle} est un concept de programmation ayant pour but principal de considérer les fonctions comme des données, et donc de pouvoir les passer en paramètres à des fonctions, évitant ainsi les effets de bord.

Une fonction prenant en paramètre une autre fonction est appelée « fonction d’ordre supérieur ».
\end{defin}

Python est un langage essentiellement impératif. Il existe des langages essentiellement
fonctionnels (LISP, Ocaml, Haskell) mais il est possible de programmer en Python dans un « style fonctionnel ».

\vspace*{-1em}
\enlargethispage*{5em}
\begin{Exemple}
voici deux programmes écrits en Python de deux manières différentes, mais dont le résultat est identique : incrémenter de 1 une variable. À gauche, la méthode de programmation est impérative, tandis qu'à droite, elle est fonctionnelle.
\end{Exemple}

\vspace*{-2mm}
\begin{minipage}[t]{0.45\linewidth}
\begin{listing}{Impérative}{03-06.py} \end{listing}
\end{minipage}
\hfill
\begin{minipage}[t]{0.45\linewidth}
\begin{listing}{Fonctionnelle}{03-07.py} \end{listing}
\end{minipage}

\subsection{Manipulation sur les listes}

\subsubsection{Introduction}

En programmation fonctionnelle, l'utilisation de \texttt{pop()} ou \texttt{append()} sur une liste ne serait pas tolérée car ces fonctions modifient l'état de la liste courante. 

\newpage

\begin{aretenir}
\begin{itemize}
\item \texttt{liste = liste.append(element)} est remplacé par:
\begin{center}
\texttt{liste + [element]}
\end{center}

\item \texttt{element = liste.pop()} est remplacé par:
\begin{center}
\texttt{liste, element = liste[:-1], liste[-1]}
\end{center}
\end{itemize}
\end{aretenir}



\subsubsection{La fonction \og map \fg{} }
\index{Python!map}

En Python, la fonction \texttt{map} est un exemple de fonction d’ordre supérieur. Cette fonction prend en argument une fonction \texttt{f} et une liste de données \texttt{L}. 

Elle applique successivement la fonction \texttt{f} à chacune des données de la liste et « stocke les résultats obtenus dans une nouvelle liste \texttt{G} ».

Ainsi, \texttt{G = [ f(L[0]), f(L[1]), ..., f(L[-1]) ]}.

\begin{Exemples}
\begin{itemize}
\item On souhaite connaître la longueur de plusieurs chaînes de caractères.

\begin{listing}{}{03-08.py}\end{listing}

\Par

Ce programme affiche : \texttt{[8, 5, 4]}.


\item On souhaite calculer le carré des longueurs calculées précédemment.

\begin{listing}{}{03-09.py}\end{listing}

\Par

Ce programme affiche : \texttt{[64, 25, 16]}.
\end{itemize}
\end{Exemples}



\subsubsection{La fonction \og reduce \fg{} }
\index{Python!reduce}

La fonction \texttt{reduce} (du module \texttt{functools}) est un autre outil de la programmation fonctionnelle. Elle fonctionne de la même façon que \texttt{map}, mais à partir d'une fonction \texttt{lambda} à deux paramètres: l'élément de la liste à traiter (\texttt{x}) et le résultat du traitement précédent (\texttt{a}). Elle ne retourne qu'un seul résultat, qui correspond au dernier calcul effectué.

\newpage

\begin{attention}
Il est à noter que la fonction \texttt{lambda} n'est pas exécutée sur le premier élément de la liste (en tant que \texttt{x}), pour lequel il n'existe pas encore d'antécédent! C'est le premier élément de la liste qui sert d'antécédent lors de la première exécution de la fonction \texttt{lambda}. Cette toute première exécution de \texttt{lambda} par \texttt{reduce()} porte donc sur le deuxième élément de la liste (en tant que \texttt{x}) avec le premier élément de la liste comme antécédent (devenant \texttt{a}).
\end{attention}

\begin{Exemple}
on souhaite calculer le résultat de l'opération:
\[
2^2 + 3^2 + 4^2 + 5^2.
\]
On utilise alors le programme suivant:
\begin{listing}{}{03-10.py}\end{listing}

\Par

Ce programme affiche \og 52 \fg, et non \og 54 \fg (qui correspondrait au résultat de $2^2+3^2+4^2+5^2$). En effet, ce programme calcule le résultat de l'opération : $2+3^2+4^2+5^2$.
\end{Exemple}

\begin{aretenir}
\begin{itemize}
\item La fonction \texttt{reduce()}, tout comme la fonction \texttt{map()}, exécute de multiples fois la fonction \texttt{lambda}: \texttt{len(liste)-1} itérations.

\item Contrairement à \texttt{map()}, les résultats des exécutions successives (hormis le dernier) ne sont pas conservés. Le résultat de l'itération $n-1$ (de lambda) est utilisé en tant qu'antécédent (\texttt{a}) de l'exécution $n$ (de lambda).
\end{itemize}

C'est cette \og mécanique \fg qui permet d'agréger (de consolider) le résultat final, donc de \textit{réduire} les itérations successives à un unique résultat.
\end{aretenir}


%\subsubsection{Compléments}

%Pour programmer de manière fonctionnelle, il existe les modules suivants:
%\begin{itemize}
%\item \texttt{itertools}, dans lequel on trouvera des fonctions créant des itérateurs de boucle efficaces;
%\item \texttt{functools}, dans lequel on trouvera des fonctions performantes comme la\linebreak fonction \texttt{reduce};
%\item \texttt{operator}, dans lequel on trouvera des opérateurs standards (opérateurs de comparaison ou encore addition par exemple) en tant que fonction.
%\end{itemize}

%Il est à noter enfin que rien n'empêche de mélanger la programmation\linebreak fonctionnelle avec d'autres types de programmation.

%\textit{Voir exercices \ref{exo:03-reecriture} à \ref{exo:03-pipeline} pages \pageref{exo:03-reecriture} à \pageref{exo:03-pipeline}.}

\enlargethispage*{5em}
\vspace*{-5mm}
\section{Diviser pour régner}
\index{Diviser pour régner}

\vspace*{-3mm}
\begin{exointro}{Lycée Henri Bergson, Angers}
Écrire un algorithme de \textit{tri fusion} permettant de trier une liste de chiffres en la scindant en deux parties à peu près égales, puis en triant récursivement chacune de ces sous-listes. 

Écrire le code Python correspondant.\vspace*{-3mm}
\end{exointro}

\newpage
%En classe de première, nous avons vu la notion de complexité d'un programme et son importance. 

%Pour améliorer la complexité d'un programme, on peut utiliser une méthode\linebreak d'optimisation \og par le règne \fg, connue aussi sous l'appellation \og diviser pour\linebreak régner \fg. Cette méthode consiste à découper un problème en plusieurs\linebreak sous-problèmes, puis à résoudre ces derniers (en général, de façon récursive sauf s'ils sont assez petits pour les résoudre directement).

%\begin{Exemple}
%on souhaite calculer $7^{12}$. On peut voir ce problème de la manière\linebreak suivante :
%\[ 7^{12} =  \underbrace{7 \times 7 \times 7 \times \cdots \times 7}_{\text{11 multiplications}} = \underbrace{\underbrace{7^{6}}_{\text{5 multiplications}} \times 7^6}_{\text{6 multiplications}} = \underbrace{\underbrace{7^3}_{\text{2 mult.}} \times 7^3 \times 7^3 \times 7^3}_{\text{5 multiplications}}. \] On est alors passé de 11 multiplications à seulement 5.
%\end{Exemple}

Pour trier une liste d'entiers, il vient naturellement à l'esprit de la scinder en deux sous-listes de même taille, qu'on triera séparément, puis de combiner le résultat de chacun de ces tris.

Si par exemple on veut trier la liste \texttt{[ 5 2 3 8 4 1 6 9 ]}, on peut diviser cette liste en :
\begin{center}
\texttt{[ 5 2 3 8 ]} et \texttt{[ 4 1 6 9 ]}, 
\end{center}

puis les trier séparément :
\begin{center}
\texttt{[ 2 3 5 8 ]} et  \texttt{[ 1 4 6 9 ]},
\end{center}

et ensuite combiner ces résultats pour obtenir la liste complète triée:  
\begin{center}
\texttt{[ 1 2 3 4 5 6 8 9 ]}.
\end{center}

\Par

On aurait pu aussi scinder en deux chacune des sous-listes \texttt{[ 5 2 3 8 ]} et\linebreak \texttt{[ 4 1 6 9 ]} pour parvenir de manière récursive au même résultat.

\Par

Cette méthode est appelée \og Diviser pour régner \fg. 

\begin{defin}[diviser pour régner]
Technique algorithmique consistant à diviser un problème initial en sous-problèmes que l'on résout récursivement ou directement, puis à combiner les résultats.
\end{defin}

Elle comporte trois phases :
\begin{itemize}
\item \textit{diviser} : on divise le problème initial en plusieurs sous-problèmes,
\item \textit{régner} : on résout récursivement ou directement chacun des sous-problèmes,
\item \textit{combiner} : on combine les différents résultats obtenus pour parvenir à la solution finale.
\end{itemize}

\Par


\begin{solintro}
Un algorithme possible est le suivant:

\begin{algorithme}{}%{Algorithme de tri fusion}
fonction tri(L):
\quad L : liste à trier
\quad N $\leftarrow$ longueur de L
\quad Si N = 0 ou N = 1:
\qquad Retourner L
\quad Sinon:
\qquad M $\leftarrow$ E(N/2)
\qquad L1 $\leftarrow$ liste des M premiers éléments de L
\qquad L2 $\leftarrow$ liste L privée de L1
\qquad Retourner la fusion de tri(L1) et tri(L2)
\end{algorithme}

\Break

En Python, cela donne: 

\qrset{height=1.1cm,version=5}\rput(-1.3,-0.8){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-11-triFusion.py}}}
\vspace*{-10pt}
\begin{listing}{Tri fusion en Python}{03-11-triFusion.py}\end{listing}

\begin{attention}
Il ne faut jamais oublier d'écrire une condition d'arrêt à une fonction récursive, sous peine d'aboutir à une boucle infinie...
\end{attention}
\end{solintro}

\vspace*{-3mm}
\section{Recherche textuelle}

\begin{problematique}
Rechercher une chaîne de caractères dans une autre est un problème récurrent, que ce soit en informatique ou dans d'autres sciences comme par exemple en génétique, dès lors qu'il s'agit de localiser un motif dans une séquence d'ADN.

Une approche naïve mènerait à un algorithme de complexité conséquente. Comment y remédier ?
\end{problematique}

\enlargethispage*{\baselineskip}
\subsection{Approche naïve}

Nous disposons de la séquence d'ADN suivante:

\begin{center}
ATAACAGAGAATAAGGCTAGGAAATACTGAA
\end{center}

\newpage

Nous souhaitons savoir si le motif \og AGGCTA \fg{} apparaît dans cette séquence.

L'approche naïve consiste à effectuer une comparaison du motif avec la séquence en partant de la droite et en décalant le motif vers la droite jusqu'à trouver une coïncidence.

\begin{center}
\begin{tabular}{|m{8.5cm}|>{\centering\arraybackslash}m{2cm}|}
\tabulartitle\hline
\centering\arraybackslash
Comparaison & Coïncidence\\
\hline
\includegraphics{067_BM-adn01} & Non\\
\hline
\includegraphics{067_BM-adn02} & Non\\
\hline
\includegraphics{067_BM-adn03} & Non\\
\hline
\centering $\vdots$ & \\
\hline
\includegraphics{067_BM-adn04} & Oui\\
\hline
\end{tabular}
\end{center}

\Par

Dans cette approche, on aligne donc le motif avec la séquence sur la gauche et on compare les caractères de la gauche vers la droite.

Ainsi, pour la première comparaison, les premiers caractères (A) coïncident, mais pas les deuxièmes; on décale donc le motif d'un caractère vers la droite.

Le \og A \fg{} se retrouve donc sous un \og T \fg{} : les deux caractères ne coïncident pas, donc on décale à nouveau.

On fait cela jusqu'à obtenir une parfaite coïncidence.


En Python, cela donne :

%%\nathanlive{progmargin}{}
\begin{listing}{Approche naïve}{03-13.py}\end{listing}

\Par\enlargethispage*{\baselineskip}

qui retourne : {\ttfamily ATAACAGAGAATA[AGGCTA]GAAATACTGAA}.

La complexité de cet algorithme est $O\big(m(s-m)\big)$, où $m$ et $s$ représentent\linebreak respectivement le nombre de lettres du motif et de la séquence.

\subsection{L'algorithme de Boyer-Moore}
\index{Algorithme de Boyer-Moore}
\index{Boyer-Moore (algorithme de)}

\subsubsection{Approche à travers un exemple}

Nous allons expliquer cet algorithme à travers l'exemple de la séquence et du motif précédent.

\begin{itemize}
\item On commence par aligner la séquence et le motif à gauche, comme\linebreak précédemment, mais la comparaison se fait sur le dernier caractère du motif:
\Par
\begin{center}
\includegraphics{068_BM-adn05}
\end{center}
\Par
Ce dernier caractère coïncide avec le 6\ieme{} de la séquence. On compare alors les deux caractères précédents:
\Par
\begin{center}
\includegraphics{068_BM-adn06}
\end{center}
\Par
Ils ne coïncident pas. 
\enlargethispage*{4em}
\item Le caractère rencontré dans la séquence (C) apparaît tout de même dans le motif : nous allons donc décaler le motif de sorte que ce caractère (C) coïncide avec le même caractère du motif:
\Par
\begin{center}
\includegraphics{068_BM-adn07}
\end{center}

\item On recommence alors la comparaison en partant de la droite du motif:
\Par
\begin{center}
\includegraphics{068_BM-adn08}
\end{center}
\Par
Ils ne coïncident pas.

\item Mais \og G \fg apparaît dans le motif donc on décale ce dernier de sorte à faire coïncider le \og G \fg{} de la séquence avec le premier \og G \fg{} du motif rencontré en partant de la droite:
\Par
\begin{center}
\includegraphics{068_BM-adn09}
\end{center}

\item On recommence alors la comparaison en partant de la droite du motif:
\Par
\begin{center}
\includegraphics{068_BM-adn10}
\end{center}
\Par
Les caractères de droite coïncident, mais pas leurs précédents.
\enlargethispage*{2em}
\item On décale donc le motif de sorte que le \og G \fg{} de la séquence coïncide avec le premier \og G \fg{} du motif en partant de droite:
\Par
\begin{center}
\includegraphics{068_BM-adn11}
\end{center}
\Par
Les derniers caractères ne coïncident pas.

\item On décale donc le motif de sorte que le \og T \fg{} de la séquence coïncide avec le \og T \fg{} du motif qui est juste avant:
\Par
\begin{center}
\includegraphics{069_BM-adn12}
\end{center}
\Par
Les deux derniers caractères coïncident mais pas les troisièmes. 

\item On décale donc le motif de sorte à faire coïncider le \og A \fg{} de la séquence avec le \og A \fg{} du motif qui est à gauche des caractères qui coïncidaient (donc avec le \og A \fg de gauche du motif):
\Par
\begin{center}
\includegraphics{069_BM-adn13}
\end{center}
\Par
Les derniers caractères ne coïncident pas.

\item On décale donc le motif de sorte à aligner le \og G \fg{} de la séquence avec celui du motif qui est le plus à droite:
\Par
\begin{center}
\includegraphics{069_BM-adn14}
\end{center}
\Par
Il y a alors correspondance entre le motif et le bout de séquence. L'algorithme s'arrête donc.
\end{itemize}

\subsubsection{Table de sauts}
\enlargethispage*{5em}

À travers l'exemple vu précédemment, on peut facilement comprendre l'utilité de construire une première table qui indique la distance maximale de chaque\linebreak caractère distinct au dernier dans le motif : on appelle cette table la \og première table de sauts \fg, ne dépendant que du motif et pas de la séquence.

On commence par l'avant-dernier caractère (en effet, le dernier caractère du motif n'est pas pris en compte pour cette table) : le motif étant \og AGGCTA \fg, le caractère \og T \fg{}   est à une distance de 1 du dernier \og A \fg, etc.

\Par

\begin{minipage}[t]{0.45\linewidth}
On obtient la table suivante:

\vspace*{6mm}

\begin{figure}
\begin{center}
\begin{tabular}{|Zc|Zc|}
\tabulartitle\hline
Caractère & Distance\\
\hline
T & 1\\
\hline
C & 2\\
\hline
G & 4\\
\hline
A & 5\\
\hline
Autres & 6\\
\hline
\end{tabular}
\tabcaption{1\iere{} table de sauts\newline du motif \og AGGCTA \fg{} }
\end{center}
\end{figure}
\end{minipage}
\hfill
\begin{minipage}[t]{0.45\linewidth}
\begin{Remarque}
pour un motif où les caractères sont tous distincts, on aura par exemple:

\Par

\begin{figure}
\begin{center}
\begin{tabular}{|Zc|Zc|}
\tabulartitle\hline
Caractère & Distance\\
\hline
C & 1\\
\hline
B & 2\\
\hline
A & 3\\
\hline
Autres & 4\\
\hline
\end{tabular}
\tabcaption{1\iere{} table de sauts\newline du motif \og ABCD \fg{} }
\end{center}
\end{figure}
\end{Remarque}
\end{minipage}




Cette première table concerne la \textit{séquence}, bien qu'elle soit construite sur le \textit{motif}, car elle donne le décalage du motif à faire sur la séquence (on doit décaler le motif de 1, 2, 3,... sur la séquence).

\subsubsection{Programme en Python}
\index{Algorithme de Boyer-Moore!programme Python}

La table de sauts précédemment vue nous donne l'idée de construire un\linebreak dictionnaire contenant toutes les lettres de l'alphabet considéré ainsi que leur\linebreak premier rang dans le motif à trouver, puis de s'appuyer sur ces valeurs pour\linebreak décaler le motif. C'est le but de la fonction \texttt{table}\_\texttt{sauts} du programme ci-dessous.

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-14-BoyerMoore.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-14-BoyerMoore.py}\end{listing}





