\chapter{Programmation : généralités}

\begin{exointro}{Lycée polyvalent Emile Zola, Aix-en-Provence}
Le \textit{problème de l'arrêt} est une démonstration par l'absurde. proposée par Alan Turing.
\index{Halting problem (Turing)}

Supposons qu'il existe un algorithme $H$ qui décide le problème de l'arrêt, c'est-à-dire que, quel que soit l'algorithme $A$ qu'on lui passe en paramètre, 
\[
\begin{cases}
H(A)\to 1 & \text{si $A$ s'arrête};\\
H(A)\to 0 & \text{si $A$ ne s'arrête pas}.
\end{cases}
\]
Posons alors $\overline{H}$ l'algorithme admettant l'algorithme $A$ en paramètre qui exécute $H(A)$ tel que:
\[
\begin{cases}
\text{si $H(A)=1$ alors une boucle infinie est créée;}\\
\text{si $H(A)=0$ alors il s'arrête.}
\end{cases}
\]
Montrer que le problème de l'arrêt est indécidable.
\end{exointro}


\section{Introduction}

En informatique, la programmation est l'art de créer des programmes, qui sont des suites d'instructions ordonnées destinées à être exécutées par une machine numérique. Pour cela, il est indispensable d'utiliser des langages, qui permettent à la machine de comprendre l'humain. Ces trois notions (machines, programmation et langages) ont évolué de manière parallèle. Commençons par un peu d'histoire...

\section{Historique}

\begin{tabular}{@{}|>{\bfseries\itshape\arraybackslash}P{20mm}|p{9cm}|@{}}
\hline
1842 & La comtesse Ada Lovelace crée des diagrammes pour la machine analytique de Charles Babbage, mathématicien anglais.\\
& Ils sont aujourd'hui considérés comme les premiers programmes informatiques.
\\\hline
1936 & Le concept de programmation et de programme enregistré est émis par Alan Turing, mathématicien anglais, dans un article\linebreak intitulé \og\textit{\mbox{On Computable Numbers}, with an Application to the Entscheidungsproblem : Proceedings of the London Mathematical Society}\fg.  Lors de la seconde guerre mondiale, Turing contribue à déchiffrer le code secret utilisé par les Allemands pour chiffrer leurs messages avec la machine \textit{Enigma}.\\\hline
Années 1940 & Les premiers ordinateurs sont créés. Ils fonctionnent à l'aide de cartes perforées en carton.
\\\hline
1954 & Développement du premier système d'exploitation au MIT (Massachusetts Institute of Technology).\\
& Apparition des premiers assembleurs et du premier\linebreak compilateur pour le langage Fortran (Formula Translator), premier langage de programmation de haut niveau.\\\hline
1964 & le langage BASIC rend l'informatique accessible aux étudiants non scientifiques\\\hline
1970 & Arrivée de la programmation structurée, permettant aux programmeurs de concevoir des programmes plus\linebreak poussés.\\\hline
1972 &  Dennis Richie et Ken Thompson, chercheurs aux Bell Labs, créent le langage C, permettant de développer le système d'exploitation multitâche multi-utilisateur UNIX.\\\hline
%1978 & Brian Kernighan et Dennis Richie publient la définition classique du C dans le livre \textit{The C Programming\linebreak language}.\\
1974 & Vince Cerf et Bob Kahn inventent le protocole TCP/IP, qui servira de base à Internet\\\hline
%1977 & l'Apple II, premier ordinateur personnel produit à grande échelle, démocratise l'informatique.\\\hline
1981 & arrivée de l'IBM-PC sous MS-DOS et développement de la micro-informatique en entreprise.\\\hline
1983 & Création du langage C++.\\\hline
1989 & Le programmeur néerlandais Guido van Rossum crée un langage de script multi-plateforme en s'inspirant des langages ABC, C, et d'UNIX. Fan des Monty Python, il nomme son invention \textit{Python}. La première version publique sort en 1991 sous licence libre.\\\hline
1994 & Apparition du langage HTML (Hypertext Markup Language). Associé au navigateur web Netscape et au protocole www (World Wide Web), HTML rend le réseau Internet accessible à tous.\\\hline
2014 & Trois milliards d'internautes utilisent quotidiennement l'informatique sur un milliard de sites en ligne.\\\hline\end{tabular}

\section{Différents types de langages}

Au plus bas niveau, le processeur ne comprend que le langage machine, qui est une suite d'opérations codées en binaire, incompréhensibles pour un être humain normalement constitué. C'est pourquoi des langages de plus haut niveau ont été inventés, mais il est nécessaire de les traduire en binaire. Il existe pour cela trois méthodes, qui correspondent à trois types de langages de programmation.

\begin{itemize}
\item les langages \textit{compilés}, dans lesquels le code source écrit par le programmeur est transformé en code binaire par un logiciel appelé \textit{compilateur}.\\
\textit{Exemples}: langages C, C++, Pascal.
\Par\Par
\begin{figure}
\begin{center}
\includegraphics{027_compilation}
\figcaption{Langage compilé}
\end{center}
\end{figure}
\Par

\item les langages \textit{interprétés}, dont le code source est utilisé en entrée d'un logiciel appelé \textit{interpréteur}, qui l'exécute ligne par ligne en décidant à chaque étape ce qu'il va faire ensuite.\\ \textit{Exemples}:  Python, JavaScript, PHP.
\Par\Par
\begin{figure}
\begin{center}
\includegraphics{027_interpretation}
\figcaption{Langage interprété}
\end{center}
\end{figure}
\Par

\item les langages \textit{semi-interprétés}, qui requièrent une compilation différente de celle vue précédemment, car elle ne transforme pas le code source en instructions binaires.

Elle se contente de préparer le travail de l'interpréteur en réécrivant les instructions du code source dans un langage intermédiaire (bytecode), qui sera plus facile à traiter par l'interpréteur lors de son exécution.\\
\textit{Exemple}: Java, C\#.
\Par
\begin{figure}
\begin{center}
\includegraphics{028_semiInterpretation}
\figcaption{Langage semi-interprété}
\end{center}
\end{figure}
\end{itemize}

\section{Calculabilité et décidabilité}



\subsection{Calculabilité}
\index{Calculabilité}

La notion de calculabilité est apparue avec Turing en 1936. Pour l'appréhender, il est nécessaire d'en savoir un peu plus sur la machine de Turing.

\subsubsection{La machine de Turing}
\index{Turing (machine de)}
\index{Machine de Turing}

\NathanLiveVideo[\PictoVideo\ Retrouvez en vidéo une explication de la machine de Turing illustrée d'un exemple.]{machine de Turing}{https://media.prepamath.fr/ILTNSIch02crs01}

\qrset{height=1.1cm,version=5}\rput(-1,0.8){
\psframebox{\qrcode{https://media.prepamath.fr/ILTNSIch02crs01}}}
\vspace*{-15pt}

C'est un \textit{modèle} abstrait de machine à calculer composé:
\begin{itemize}
\item d'un \textit{ruban} infini composé de plusieurs cases dans lesquelles se trouve un élément de l'ensemble $\{0;1\}$; par exemple:
\Par
\begin{center}
\begin{tabular}{Zc|*5{Zc|}Zc}
\hline
$\cdots$ & 0 & 0 & 1 & 0 & 1 & $\cdots$\\
\hline
\end{tabular}
\end{center}


\item d'une \textit{tête de lecture et d'écriture} qui se trouve à chaque instant devant une des cases du ruban et qui peut être dans deux états possibles : 0 ou 1; par exemple:
\Par
\begin{center}
\begin{tabular}{|*5{Zc|}Zc}
\hline
0 & 0 & 1 & 0 & 1 & $\cdots$\\
\hline
\end{tabular}

\hspace*{-9mm}$\uparrow$

\hspace*{-9mm}$0$
\end{center}

\item d'une \textit{table de transitions}, tableau contenant, comme son nom l'indique, des transitions (des transformations) ainsi que la valeur que l’on écrit, de la forme:
\Par
\begin{center}
$(t,v) \to (t',v')$
\end{center}
où $t$ et $t'$ sont deux états de la tête de lecture, et où $v$ et $v'$ sont deux valeurs contenues dans une case; 

par exemple, la table:
\begin{center}
\begin{tabular}{|Zc@{\quad$\to$\quad}Zc|}
\hline
$(0,0)$ & $(0,1)$\\
\hline
$(0,1)$ & $(1,1)$\\
\hline
\end{tabular}
\end{center}
signifie que :
\begin{itemize}
\item[$\to$] si la tête de lecture est dans l'état \og 0 \fg{} et pointe sur une case contenant la valeur \og 0 \fg{}  alors la tête de lecture reste sur l'état \og 0 \fg{} mais la valeur passe à \og 1 \fg{} et la tête de lecture avance d'une case;

\item[$\to$] si la tête de lecture est dans l'état \og 0 \fg{} et pointe sur une case contenant la valeur \og 1 \fg{}  alors la tête de lecture passe à l'état \og 1 \fg{} et la valeur reste à \og 1 \fg{} et la tête de lecture avance d'une case; 

\item[$\to$] pour les autres cas, rien ne change : l'état de la tête de lecture reste à sa valeur et il en est de même pour la valeur de la case vers laquelle pointe la tête de lecture. La tête de lecture reste où elle est.
\end{itemize}
\end{itemize}

\begin{Exemple}[incrémentation] Voyons comment modéliser l'opération $n \to n + 1$ pour un entier $n$ à l'aide d'une machine de Turing.
\end{Exemple}

L'entier $n$ est représenté par un ruban contenant $n$ \og 1 \fg{} suivis de plusieurs \og 0 \fg; prenons l'exemple de $n=2$. Initialement, la tête de lecture pointe sur la première case et est dans l'état \og 0 \fg.


\Par

\begin{figure}
\begin{center}
\begin{tabular}{Zc|*5{Zc|}Zc}
\hline
$\cdots$ & 1 & 1 & 0 & 0 & 0 & $\cdots$\\
\hline
\end{tabular}

\hspace*{-25mm}$\uparrow$

\hspace*{-25mm}$0$

\figcaption{Représentation du nombre \og 2 \fg{} dans la machine de Turing}
\end{center}
\end{figure}

\Par\Par

La table de transitions est la suivante :

\Par

\begin{figure}
\begin{center}
\begin{tabular}{|Zc@{\quad$\to$\quad}Zc|}
\hline
$(0,1)$ & $(0,1)$\\
\hline
$(0,0)$ & $(1,1)$\\
\hline
\end{tabular}
\end{center}
\end{figure}

\Par

Alors, comme la tête de lecture est initialement sur l'état \og 0 \fg{} et que la valeur de la première case est \og 1 \fg, d'après la première transition, la tête de lecture restera à \og 0 \fg{} et la valeur restera à \og 1 \fg.

Une fois la transition prise en compte, la tête de lecture avance d'une case.

\Par

\begin{figure}
\begin{center}
\begin{tabular}{|*5{Zc|}Zc}
\hline
1 & 1 & 0 & 0 & 0 & $\cdots$\\
\hline
\end{tabular}

\hspace*{-22mm}$\uparrow$

\hspace*{-22mm}$0$

\figcaption{Après la 1\iere transition}
\end{center}
\end{figure}

\Par\Par

Là encore, la tête de lecture est à \og 0 \fg{} et le nombre de la case vers laquelle elle pointe vaut \og 1 \fg, donc aucun changement n'est fait et la tête de lecture passe à la case suivante:

\Par

\begin{figure}
\begin{center}
\begin{tabular}{|*5{Zc|}Zc}
\hline
1 & 1 & 0 & 0 & 0 & $\cdots$\\
\hline
\end{tabular}

\hspace*{-10mm}$\uparrow$

\hspace*{-10mm}$0$

\figcaption{Après la 2\ieme transition}
\end{center}
\end{figure}

\Par

D'après la 2\ieme{} ligne de la table de transitions, la tête de lecture passe à l'état \og 1 \fg{}  et la valeur de la case aussi, puis la tête de lecture avance d'une case:

\Par

\begin{figure}
\begin{center}
\begin{tabular}{|*5{Zc|}Zc}
\hline
1 & 1 & 1 & 0 & 0 & $\cdots$\\
\hline
\end{tabular}

\hspace*{3mm}$\uparrow$

\hspace*{3mm}$1$

\figcaption{Après la 3\ieme transition}
\end{center}
\end{figure}

\Par\Par

Comme aucune transition ne porte sur l'état $(1,0)$, il n'y a plus de changement et la tête de lecture n'avance plus.

\Par\Par

On aboutit ainsi à la valeur \og 3 \fg{} (car il y a 3 \og 1 \fg), ce qui correspond bien à l'incrémentation de 2.
%---> fin de l'exemple

\subsubsection{Thèse de Church-Turing et calculabilité}
\index{Thèse de Church-Turing}
\index{Church-Turing (thèse de)}


Cette thèse, qui n'est pas un théorème puisqu'elle n'a pas été démontrée, stipule que :

\begin{center}
\textit{Si un problème est tel qu'il existe un algorithme le résolvant, alors il existe une machine de Turing qui résout le problème.}
\end{center}

\Par

Cette thèse mène alors à la notion de calculabilité.

\begin{defin}
On dira qu'un problème est \textit{calculable} s'il existe une machine de Turing le résolvant.
\end{defin}

On peut ainsi définir un algorithme :

\begin{defin}
Un \textit{algorithme} est une table de transitions d'une machine de Turing.
\end{defin}

\newpage
\subsubsection{La machine universelle}
\index{Machine universelle}

Généralisons la notion de machine de Turing et, pour bien comprendre, reprenons l'exemple de l'incrémentation.

Nous avons vu précédemment que nous avons passé en argument à la machine de Turing le nombre $n$ afin d'obtenir son suivant. Appelons \texttt{Inc(n)} cette machine de Turing. \texttt{Inc} est définie par sa table de transitions, que l'on peut représenter simplement par la succession de binaires : \og 01010011 \fg.

\Par

\begin{center}
\begin{tabular}{|Zc@{\quad$\to$\quad}Zc|}
\hline
$(0,1)$ & $(0,1)$\\
\hline
$(0,0)$ & $(1,1)$\\
\hline
\end{tabular}
\qquad
devient
\qquad
\og 01010011 \fg
\end{center}

\Par

L'idée permettant de construire la machine $U$ (la machine universelle) est de\linebreak passer d'abord en argument la table de transitions sous forme binaire, puis le nombre $n$ (pour notre exemple).

%\Par
%La thèse de Church-Turing devient alors légèrement plus simple et donne :
%\begin{center}\textit{Si un problème est tel qu'il existe un algorithme le résolvant alors $U$ résout le problème.}\end{center}

\Par

La machine universelle constitue les principes fondamentaux des ordinateurs\linebreak d'aujourd'hui : on peut considérer un programme comme étant une table de\linebreak transitions que l'on passe en paramètre.

%\begin{thm}
%Tous les problèmes ne peuvent pas être calculables.
%\end{thm}
\begin{Remarque}
tous les problèmes ne sont pas calculables.
\end{Remarque}

%\textit{Voir exercice \ref{pb-calculabilite} page \pageref{pb-calculabilite}.}


\subsection{Décidabilité}
\index{Décidabilité}

\begin{defin}
Un problème est \textit{décidable} si et seulement si il existe un algorithme qui le\linebreak résout.
\end{defin}

Cela sous-entend que l'algorithme se termine en un nombre fini d'opérations.

\begin{Exemple}
un entier donné est-il un carré parfait ?
\end{Exemple}

On peut aisément répondre à ce problème à l'aide de l'algorithme suivant:

\begin{algorithme}{}
n $\leftarrow$ 0
x : nombre entier
Tant que (n$^2$ != x) et (n$^2$ < x):
\quad n $\leftarrow$ n + 1

Retourner (n$^2$ == x)
\end{algorithme} 

\Par

Le code Python correspondant s'écrit :

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

\Par

Le problème est donc décidable.

\Par

Alan Turing a démontré en 1936 que tous les problèmes n'étaient pas décidables à l'aide d'un contre-exemple: le \textit{problème de l'arrêt}. C'est l'objet de l'exercice type proposé au début de ce chapitre.

\begin{solintro}
Nous avons posé $\overline{H}$ l'algorithme admettant l'algorithme $A$ en paramètre qui exécute $H(A)$ tel que:
\[
\begin{cases}
\text{si $H(A)=1$ alors une boucle infinie est créée;}\\
\text{si $H(A)=0$ alors il s'arrête.}
\end{cases}
\]
$\overline{H}$ existe si $H$ existe.

\Par

Considérons alors $\overline{H}\big(\overline{H}\big)$.

\begin{itemize}
\item Si $\overline{H}$ s'arrête alors $H\big(\overline{H}\big)=1$ et donc $\overline{H}\big(\overline{H}\big)$ crée une boucle infinie, donc ne s'arrête pas.

\item Si $\overline{H}$ ne s'arrête pas alors $H\big(\overline{H}\big)=0$ et donc $\overline{H}\big(\overline{H}\big)$ s'arrête.
\end{itemize}

Dans les deux cas, il y a contradiction. Ainsi, $\overline{H}$ n'existe pas, et donc $H$ non plus.

\Par

Le problème de l'arrêt est donc indécidable.
\end{solintro}


\enlargethispage*{\baselineskip}

\section{Récursivité}
\index{Récursivité}

\begin{exointro}{Lycée Sainte-Anne, Brest}
Implémenter en Python une fonction récursive \texttt{somme(n)} qui renvoie la valeur de $S_n =1+2+3+\cdots+(n-1)+n$, en remarquant que $S_{n}=S_{n-1}+n$.
\end{exointro}

\NathanLiveVideo[\PictoVideo\ Retrouvez une vidéo sur la récursivité.]{récursivité}{https://media.prepamath.fr/ILTNSIch02crs02}

\qrset{height=1.1cm,version=5}\rput(-1,0.5){
\psframebox{\qrcode{https://media.prepamath.fr/ILTNSIch02crs02}}}
\vspace*{-15pt}


\subsection{Définition}

\begin{defin}
Une fonction \textit{récursive} est une fonction qui fait appel à elle-même.
\end{defin}

\vspace*{-5mm}
\begin{Remarque}
on parle aussi d'\textit{algorithmes récursifs}.
\end{Remarque}

\vspace*{-3mm}
\begin{Exemple}[calcul d'une factorielle]
\index{Récursivité!Factorielle}
en mathématiques, on définit la factorielle d'un nombre entier $n$ par :
\[
n!=1\times2\times3\times4\times\cdots\times n.
\]
\end{Exemple}
Ainsi, si $f(n)=n!$ alors $f(n+1)=(n+1) \times f(n)$. On peut alors définir la fonction \texttt{factorielle} de façon récursive. 

\Par

En Python, cela donne par exemple le code suivant.


\begin{listing}{}{02-02.py}\end{listing}

\Par

En tapant :

\qquad \texttt{print(factorielle(5))}

\Par

le résultat \og 120 \fg{} s'affiche, qui est bien égal à $5!=1\times2\times3\times4\times5$.

Un autre exemple est celui du calcul du pgcd de deux nombres.


\vspace*{-3mm}
\begin{Remarque}
le langage Python limite le nombre d'appels récursifs. Pour savoir le nombre maximal autorisé, on pourra taper :
\index{Python!Nombre d'appels récursifs}
\end{Remarque}

{\ttfamily
\qquad \textbf{import} sys

\qquad print(sys.getrecursionlimit())
}

\Par

Par exemple, \texttt{factorielle(1000)} va afficher l'erreur :

\qquad\texttt{RecursionError: maximum recursion depth exceeded in}

\qquad \texttt{comparison}

\Par

Pour augmenter ce nombre limite, on pourra utiliser la syntaxe suivante:

\qquad\texttt{sys.setrecursionlimit(1500)}

\Par

On peut alors calculer \texttt{factorielle(1000)}, mais dans la mesure où le résultat comporte \numprint{2568} (= \texttt{len(str(factorielle(1000)))}) chiffres, il ne figurera pas dans ce livre...


\subsection{Complexité d'un programme récursif}
\index{Récursivité!Complexité}

\begin{prop}
Un programme récursif a une complexité linéaire ou exponentielle.
\end{prop}

\begin{Exemple}
reprenons l'exemple précédent (algorithme récursif de la factorielle). Notons $C(n)$ la complexité de la fonction pour la variable  entière $n$.
\end{Exemple}
\begin{itemize}
\item Si $n=0$, seul le test \texttt{n == 0} est effectué donc $C(0)=1$;
\item si $n>0$, le test et le produit sont pris en compte en plus des opérations\linebreak élémentaires de la fonction pour $n-1$, donc $C(n) = 2 + C(n-1)$.
\end{itemize}
On peut donc dire que la complexité de cette fonction est la suite $(c_n)$ définie par $c_0=1$ et $c_{n+1}=c_n+2=2n+1$.

On dira alors que la complexité est :

\begin{multicols}{2}
\begin{itemize}
\item \textit{linéaire} si $C(n)=O(n)$
\item \textit{quadratique} si $C(n)=O(n^2)$
\item \textit{exponentielle} si $C(n)=O(\nep^x)$
\item \textit{logarithmique} si $C(n)=O(\ln x)$
\end{itemize}
\end{multicols}

où la notation $O(\ldots)$ est appelée \textit{notation de Landau}: on prend le terme « dominant » à l’infini sans le coefficient dans l’expression de $C(n)$.


\subsection{Correction d'un algorithme récursif}
\index{Récursivité!Correction d'une algorithme récursif}
Pour garantir qu’un algorithme récursif fonctionne correctement, on doit vérifier :
\begin{itemize}
\item que lorsqu’il atteint un état final, il doit fournir la solution correcte au problème osé : c’est la \textit{correction partielle} ;
\item qu’il doit toujours parvenir à un état final, c’est-à-dire qu’il doit cesser de faire des appels récursifs après un nombre fini d’étapes. Cela implique de s’assurer que chaque appel récursif progresse vers une condition de base qui met fin à la récursion : c’est le\textit{ problème de la terminaison}
\end{itemize}


\subsubsection{Terminaison}
\enlargethispage*{4em}

Regardons sur l'exemple de la fonction récursive \texttt{factorielle} vue précédemment comment vérifier sa terminaison.

La fonction admet un argument entier positif. De plus, 
\begin{itemize}
\item \texttt{factorielle(n)} fait appel à \texttt{factorielle(n-1)};
\item \texttt{factorielle(n-1)} fait appel à \texttt{factorielle(n-2)};
\item etc.
\item \texttt{factorielle(1)} fait appel à \texttt{factorielle(0)};
\item \texttt{factorielle(0)} renvoie la valeur \og 1 \fg.
\end{itemize}
On est donc assurés que cette fonction se termine.


\subsubsection{Correction partielle}

\begin{defin}
Dans une fonction récursive, un \textit{appel interne} est un appel de la fonction déclenchée par elle-même (un appel \textit{récursif}).
\end{defin}


Pour démontrer la \textit{correction partielle} d’un algorithme récursif, il est nécessaire de prouver que, si chaque appel récursif produit le résultat attendu, alors l’algorithme global produira également le résultat correct. En d’autres termes, si les sous-problèmes résolus par les appels récursifs sont corrects, alors la solution globale
le sera aussi. Il en va de même pour une fonction.

\Par

Par exemple, pour la fonction \texttt{factorielle}, si on part du principe que\linebreak \texttt{factorielle(n-1)} représente $(n-1)!$ alors \texttt{n * factorielle(n-1)}\linebreak représente bien $n \times (n-1)! = n!$.

Cela ressemble au \textit{raisonnement par récurrence} vu en mathématiques.

\Par

%\begin{anecdote}
%Le créateur du langage Python, Guido van Rossum, a dit un jour :

%\qquad \og I don’t believe in recursion as the basis of all programming \fg{}

%soit, en français :

%\qquad \og Je ne crois pas à la récursivité comme base de toute programmation \fg{}

%et c'est la raison pour laquelle il n'y a pas beaucoup d'avantage à écrire de manière récursive en Python. En effet, Guido van Rossum n'a pas voulu que la pile d'appels récursifs soit optimisée à cet effet.

%C'est pourquoi cette pile d'appels est limitée à \numprint{1000}. Vous constaterez d'ailleurs qu'au-delà de ce nombre, Python plante. Et même s'il est possible d'augmenter cette taille avec les commandes :

%\Par

%{\ttfamily
%import sys

%sys.setrecursionlimit(4000)
%}

%\Par

%Python a tout de même tendance à planter pour un trop grand nombre d'appels.
%\end{anecdote}

%\textit{Voir exercices \ref{exo:fct-mystere} à \ref{exo:sudoku} pages \pageref{exo:fct-mystere} à  \pageref{exo:sudoku}.}

\section{Modularité}

\subsection{Principe}

Quand on doit élaborer un programme complexe, il est primordial de le penser en terme de modularité. Cela signifie qu'il est nécessaire de le découper en un maximum de blocs afin de le rendre plus lisible et fonctionnel. 

Concevoir un programme avec plusieurs fonctions permet de faire appel à ces fonctions à plusieurs endroits dans le programme.

Les fonctions les plus utilisées pourront être placées dans des fichiers auxiliaires, autrement appelés \textit{modules} ou \textit{bibliothèques} (en Python par exemple).

\begin{Exemple}
imaginons un module nommé \texttt{bienpratique} renfermant plusieurs fonctions. On peut alors écrire un programme principal faisant appel à ce module, c'est-à-dire le programme qui contient l'ensemble des instructions qui seront directement exécutées à son lancement.

\Par

L'exemple de la page suivante montre le contenu du fichier \texttt{bienpratique.py}, contenant deux fonctions \texttt{is\_square}  et \texttt{is\_odd}, qui pourront être utilisées dans le fichier \texttt{main.py} dans lequel on importe \texttt{bienpratique.py}.
\end{Exemple}

\begin{Remarque}
quand on écrit un module, il est nécessaire de le documenter au mieux afin que toute personne puisse s'y retrouver et comprendre les blocs de code.
\end{Remarque}
\newpage
%%\nathanlive{progmargin}{}
\begin{listing}{Module : bienpratique.py}{02-03.py}\end{listing}

%%\nathanlive{progmargin}{}
\begin{listing}{Programme principal: main.py}{02-04.py} \end{listing}

\subsection{Ne pas réinventer la roue}
\enlargethispage*{5em}

Il existe déjà de nombreux modules libres et gratuits, fournis par Python, des entreprises et des particuliers. Il n'est donc pas nécessaire de créer des fonctions qui existent déjà.
\newpage
Par exemple,

\begin{itemize}
\item le module \texttt{random} contient des fonctions qui ont un rapport avec la génération de nombre pseudo-aléatoires.

Documentation : \texttt{https://docs.python.org/fr/3/library/random.html}.

\item le module \texttt{numpy} concerne les calculs scientifiques.

Documentation : \texttt{https://www.numpy.org}.

\item le module \texttt{sympy} concerne les mathématiques symboliques (le calcul\linebreak algébrique par exemple).

Documentation : \texttt{https://www.sympy.org/en/index.html}.

%\item le module \texttt{matplotlib} concerne les tracés de courbes.

%Documentation : \texttt{https://matplotlib.org}. 

\item le module \texttt{pandas} concerne les statistiques et les manipulations de données.

Documentation : \texttt{https://pandas.pydata.org}. 

\item le module \texttt{os} fournit des fonctionnalités dépendantes du système d'exploitation.

Documentation : \texttt{https://docs.python.org/fr/3/library/os.html}. 
\end{itemize}


\begin{solintro}
Comme dans toute fonction récursive, il faut penser à la terminaison, sans quoi le programme risque de ne jamais s'arrêter.

Ici, le premier terme de la somme est 1 donc il nous faut renvoyer \og 1 \fg{} quand $n=1$.

De plus, si on note $S_n=1+2+\cdots+n$, on voit que $S_n=S_{n-1}+n$, ce qui nous permet de dire que si $n\neq1$ alors on doit retourner la somme de \texttt{somme(n-1)} et \texttt{n}.

On en déduit la fonction suivante:

%\nathanlive[10mm]{progmargin}{}
\begin{listing}{}{02-05.py}\end{listing}

\end{solintro}