\chapter{Notions d'algorithmique}

\section{Qu'est-ce qu'un algorithme~?}

\begin{exointro}{Lycée Marie Curie, Sceaux}
On considère la séquence d'instructions~: 
 
\begin{algorithme}{}
1> a = 3
2> b = a/2
3> a+b = 4.5
4> b = b+1
\end{algorithme}

\Par

Expliquer ce qui est effectué sur chaque ligne
et préciser si chaque opération est autorisée. 
\end{exointro}

\subsection{Introduction}

Au collège, vous avez vu que le logiciel Scratch permettait de construire votre propre programme et ce, rien qu'en déplaçant des blocs d'instructions (les\linebreak instructions sont des ordres à exécuter par l'ordinateur).

Ces blocs d'instructions constituent un moyen simple de visualiser ce que l'on appelle un \textit{algorithme}.

\begin{defin}[algorithme]
Un \emph{algorithme} est une suite finie d'instructions permettant de résoudre un\linebreak problème. 
\end{defin}


Dans un premier temps, on peut écrire l'algorithme
dans un langage \emph{naturel}. 

\newpage

\begin{Exemple}
\begin{algorithme}{}
Variable 
\quad x est un nombre
Début 
\quad x $\leftarrow$ 5
\quad Afficher x
\quad x $\leftarrow$ 10
\quad Afficher x
Fin
\end{algorithme}

\Par

L'instruction \texttt{x $\leftarrow$ 5}
est une \emph{affectation}. La valeur 5 est stockée
dans la variable~\texttt{x}

Au départ, le nombre \og 5 \fg{} s'affiche (car c'est la première valeur de la variable \texttt{x}) et dans un second temps, c'est \og 10 \fg{} qui s'affiche (car on a \emph{affecté} à \texttt{x} une autre valeur après le premier affichage).
\end{Exemple}

On traduit l'algorithme pour l'ordinateur sous forme
de \emph{programme}, à l'aide d'un \emph{langage de programmation}, comme Python. 

\begin{Exemple}
\begin{listing}{}{01-crs-01.py}\end{listing}
\end{Exemple}



\subsection{Type des variables}

Dans le programme précédent, 
on remarque que Python n'a pas besoin qu'on lui 
précise que la variable \texttt{x} va contenir un nombre. 

Au moment de l'affectation \texttt{x = 5}, Python détermine
lui-même que 5 est un entier et que \texttt{x} va contenir
un entier. On dit alors que la variable \texttt{x} est du 
\emph{type} entier. 

Le type d'une variable est important car il détermine
(entre autres) quelle place la variable peut occuper en
mémoire. 

En Python, on distingue les types suivants~: 
\begin{itemize}
\item entier (en Python, \texttt{int}, 
de l'anglais \emph{integer})~:
\texttt{-234}.
\item booléen (du mathématicien et logicien anglais George Boole, 1815-1864). Ce type ne contient que deux valeurs~:
\texttt{True} (vrai) et \texttt{False} (faux)
\item flottant (en Python \texttt{float}) \texttt{45.156},
\text{-8.11}. À noter~: Python utilise le point décimal
au lieu de la virgule. La position \og flottante \fg
de la virgule donne son nom à ce type.
\item chaînes de caractères (en Python, \texttt{str} pour
\emph{string}), \texttt{'mathématiques'}, 
\texttt{"bonjour"}.
\end{itemize}

Le nom d'une variable obéit à certaines règles. Pour simplifier, disons qu'il consiste en une suite de lettres, 
y compris le caractère \og \verb+_+ \fg, suivie éventuellement d'une suite de chiffres. Noter que Python fait la différence
entre majuscules et minuscules. 

Par exemple, 

\begin{itemize}
\item \texttt{ab1}, \verb+ ma_variable+, \texttt{Résultat},
\texttt{vAriAble} sont des noms autorisés;

\item \texttt{2}, \texttt{51ab}, \texttt{x+y}, \texttt{'hello'} sont interdits (\texttt{'hello'} est une chaîne de caractère,\linebreak 2 est un entier : ce sont des \emph{constantes}). 
\end{itemize}


\subsection{L'affectation}

En Python, le symbole d'affectation est le
signe égal (\og $=$ \fg). 

Contrairement à ce qui se passe en mathématiques, 
le signe \og = \fg n'est pas du tout symétrique. 

Le membre de gauche est toujours un nom de variable. Si
cette variable n'existe pas encore, elle est créée. 

En revanche, le membre de droite peut contenir des
variables mais elles doivent déjà contenir une valeur. 
La valeur du membre de droite est alors calculée
puis stockée dans la
variable située du côté gauche du \og = \fg. 

Par exemple, dans l'instruction \texttt{x=5}, 
on calcule la valeur du membre de droite (donc 5),
qui est stockée dans la variable \texttt{x}. 

Si maintenant on effectue \texttt{x=10}, la valeur 10
vient remplacer la valeur 5 dans la variable \texttt{x}. 


\begin{solintro}
\begin{algorithme}{}
1> a = 3
\end{algorithme}

\Par

La valeur 3 est évaluée et stockée dans la variable 
\texttt{a}, qui est donc de type entier. 

\begin{algorithme}{}
2> b = a/2
\end{algorithme}

\Par

Le membre de droite est évalué. Comme \texttt{a}
contient 3, le quotient n'est pas entier et sa valeur
est \texttt{1.5}, qui est stockée dans \texttt{b}. 
Cette variable est de type flottant. 

Si l'instruction avait été~: 

\begin{algorithme}{}
2> b = a//2
\end{algorithme}

\Par

on aurait alors une division \emph{entière}, et
c'est l'entier \texttt{1} qui serait stocké dans~\texttt{b}. 
\vspace*{-0.5em}

\Break

\begin{algorithme}{}
3> a+b = 4.5
\end{algorithme}

\Par

Le membre de droite n'est pas un nom de variable 
autorisé, cette instruction est donc fausse. 
Pourtant, l'instruction~:

\begin{algorithme}{}
3> print(a+b)
\end{algorithme}

\Par

devrait bien donner \texttt{4.5} mais le signe '=' n'est
pas un symbole de comparaison, mais d'affectation. 

\begin{algorithme}{}
4> b = b+1
\end{algorithme}

\texttt{b} contient la valeur \texttt{1.5}, donc le 
membre de droite a pour valeur \texttt{2.5}. Cette valeur
est stockée dans \texttt{b} et remplace la valeur précédente. 
La variable \texttt{b} reste du type flottant. 

Remarquons qu'on vient d'assister à l'addition de \texttt{1}, 
qui est de type entier, avec \texttt{1.5}, qui est de type
flottant. Ceci peut paraître anodin, mais c'est une
opération qui ne va pas de soi sur un ordinateur. 
En fait, Python convertit automatiquement l'entier \texttt{1}
en le flottant \texttt{1.0} pour pouvoir faire l'addition. 
Certains langages de programmation ne font pas cette
conversion automatiquement et produiraient un message
d'erreur. 
\end{solintro}


\section{Les instructions composées} 

\begin{exointro}{Lycée Jules Ferry, Versailles}
On considère la fonction $f$ définie sur $\R_+$ par 
$f(x)=\dfrac{2x^2+x}{x^2+2x+1}$.

\Par

{\'E}crire un algorithme qui permet d'afficher $f(0)$, $f(1)$, $f(2)$, ... , $f(20)$.
\end{exointro}

\subsection{Les séquences d'instruction}
Une séquence d'instructions est tout simplement une
suite d'instructions à exécuter les unes après les autres.
En Python, les instructions de la séquence doivent
être écrites les unes sous les autres, avec la 
même indentation (c'est-à-dire, le même retrait). 

\newpage

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

\Par

Si on manque de place, ou pour la clarté du code, 
on peut écrire les instructions de la séquence sur
une même ligne. Elles doivent alors être séparées par
un point-virgule~: 

\begin{listing}{}{01-crs-03.py}\end{listing}

\Par

Chaque instruction de la séquence peut elle aussi être
une séquence~: 

\begin{listing}{}{01-crs-04.py}\end{listing}

\Par

Une instruction simple est un cas particulier de séquence
d'instructions. 

\subsection{Instruction conditionnelle : SI ... ALORS ...}

L'instruction \og SI ... ALORS ...\fg{}  permet d'exécuter une ou plusieurs instructions si une condition est remplie. Sa structure générale est :

\Par

\begin{algorithme}{}
SI condition ALORS
\quad instruction(s) à exécuter si la condition est remplie
FIN SI 
\end{algorithme}
\Par
Le plus souvent, la condition est une égalité ou une inégalité portant sur une variable. 

\begin{Exemple}
\begin{algorithme}{}
Variable x : nombre
Début
	$\quad$x $\leftarrow$ 0
	$\quad$Si x$>$10 alors 
		$\qquad$Afficher x
	Ajouter 20 à x
	$\quad$Si x$>$10 alors 
		$\qquad$Afficher x
	$\quad$Fin Si 
Fin
\end{algorithme}

\Break

Au début, \texttt{x} vaut 0. Comme la condition 
\texttt{x>10} est fausse, il ne se passe rien
et on passe à la ligne suivante. On ajoute alors 20 à \texttt{x}, qui vaut maintenant 20. 
L'instruction suivante teste si \texttt{x>10}, ce qui 
est vrai, donc la valeur de \texttt{x} est affichée, 
c'est-à-dire 20. 
Voici la version Python~: 

\begin{listing}{En Python}{01-crs-05.py}\end{listing}

\Par

La séquence concernée par la condition doit être
indentée (c'est-à-dire, qu'on doit faire un 
retrait). L'instruction \verb' x = x + 20' n'est pas
indentée et doit donc être exécutée quelle que
soit la valeur de la condition \verb' x>10'. 
\end{Exemple}

Une variante de cette instruction est \og SI ... ALORS ... SINON ... \fg{} :

\begin{algorithme}{}
SI condition ALORS
\quad instruction(s) à exécuter si la condition est remplie
SINON
\quad instruction(s) à exécuter si la condition n'est pas 
\quad remplie
FIN SI 
\end{algorithme}

\begin{Exemple}
\begin{algorithme}{}
Variable x : nombre
Début
	$\quad$x $\leftarrow$ 0
	$\quad$Si x$>$10 alors 
		$\qquad$Afficher x
	$\quad$Sinon 
		$\qquad$Afficher : "trop petit"
	$\quad$Fin Si 
Fin
\end{algorithme}

\Par

Ici, \texttt{x} contient la valeur $0$. 
Comme la condition \texttt{x>10} est fausse,
c'est l'instruction qui suit "sinon" qui est exécutée
et la chaîne de caractères : \og trop petit \fg
s'affiche à l'écran. 

\Break

\begin{listing}{En Python}{01-crs-06.py}\end{listing}

\end{Exemple}


\subsection{Les boucles POUR et TANT QUE}

Une \emph{boucle} permet d'exécuter plusieurs fois une ou plusieurs instructions.

\subsubsection{La boucle bornée POUR}

On utilisera la boucle POUR quand on saura le nombre de fois qu'il faut exécuter un bloc d'instructions.

Sa structure générale est de la forme :

\begin{algorithme}{}
POUR variable ALLANT DE valeur initiale À valeur finale 
\quad instruction(s) à répéter
FIN POUR
\end{algorithme}

\begin{Remarques}
\begin{itemize}
\item La variable, qui change de valeurs à chaque fois que la boucle s'exécute, est aussi appelée \emph{variable de boucle} ou \emph{compteur}, pour ne pas qu'il y ait d'ambiguïté avec les autres variables de l'algorithme.
\item \og FIN POUR\fg{} indique la fin de la liste des instructions à répéter.
\end{itemize}
\end{Remarques}

\begin{Exemple}
soit $f(x)=x^2-3x$. 

Pour calculer $f(0)$, $f(1)$, $f(2)$, ... , $f(20)$, on peut utiliser l'algorithme suivant.

\Par

\begin{algorithme}{}
Variables x,y : nombres
Début
\quad Pour x allant de 0 à 20
\qquad y prend la valeur x**2-3*x
\qquad Afficher y	
\quad Fin Pour 
Fin
\end{algorithme}

\Par

On note que \texttt{x**2} signifie que la valeur
de \texttt{x} est mise au carré. 

\Break

En Python, on utilise le mot-clé \emph{range} (\emph{intervalle}, 
en anglais). Attention, par convention, la valeur finale
est toujours exclue. Si on veut que \texttt{x} décrive
les valeurs de 0 à 20 inclus, il faut donc demander
que x prenne les valeurs de 0 à 21 (exclu)~:

\begin{listing}{En Python}{01-crs-07.py}\end{listing}
\end{Exemple}

\begin{Remarque}
il n'est pas obligatoire d'utiliser la variable de boucle à l'intérieur même de la boucle. Par exemple, si on veut afficher 100 fois la chaine\linebreak \og Bonjour ! \fg, on pourra utiliser l'algorithme suivant.

\Par

\begin{algorithme}{}
Variable : i
Début
\quad Pour i allant de 1 à 100
\qquad Afficher "Bonjour !"
\quad Fin Pour
Fin
\end{algorithme}

\begin{listing}{En Python}{01-crs-08.py}\end{listing}
\end{Remarque}

\subsubsection{Boucle non bornée TANT QUE}
On utilise une boucle TANT QUE lorsque la longueur
de la boucle n'est pas connue (ou difficile à prévoir)
au moment de l'écriture de l'algorithme. 

La forme générale de cette boucle s'écrit~: 


\begin{algorithme}{}
TANT QUE condition FAIRE
\quad instruction(s)
FIN TANT QUE
\end{algorithme}

\Par

\begin{Remarque}
\og FIN TANT QUE\fg{} indique la fin de la liste des instructions à répéter.
\end{Remarque}

On utilisera la boucle TANT QUE quand la condition dépendra du contenu de la boucle.

\newpage

\begin{Exemple}
on veut afficher le plus petit entier $n$ pour lequel $\dfrac{1}{n^2+n+1}\geq 10^{-6}$. Pour cela, on utilise l'algorithme suivant.

\begin{algorithme}{}
Variable : n
Initialisation : n prend la valeur 0
Début
\quad Tant que 1/(n*n+n+1) $>$ 10$^{\text{-6}}$
\qquad n prend la valeur n+1
\quad Fin Tant que
\quad Afficher n
Fin
\end{algorithme}

\begin{itemize}
\item Avant d'entrer dans la boucle, \texttt{n} vaut 0, et donc :
\[
\dfrac{1}{n^2+n+1}=\dfrac{1}{0^2+0+1}=1,
\]
qui est strictement supérieur à $10^{-6}$. Donc on exécute l'instruction dans la boucle : \texttt{n} est augmenté de 1, donc vaut 1. 

\item On teste à nouveau la condition : 
\[
\dfrac{1}{n^2+n+1}=\dfrac{1}{1^2+1+1}=\dfrac{1}{3},
\]
qui est encore plus grand que $10^{-6}$ donc on exécute l'instruction à l'intérieur de la boucle.

\item Ainsi de suite jusqu'à ce que $\dfrac{1}{n^2+n+1}$ soit strictement plus petit que $10^{-6}$. Dans ce cas, on sort de la boucle et on affiche la dernière valeur de \texttt{n}, celle pour laquelle $\dfrac{1}{n^2+n+1}\leq 10^{-6}$ pour la première fois.
\end{itemize}

\begin{listing}{}{01-crs-08b.py}
\end{listing}

\Par

Pour information, ce programme affiche le nombre \numprint{1000}.

Les boucles non bornées sont délicates à manier. 
Dans l'algorithme ci-dessus, il ne faut pas oublier
d'initialiser ou d'incrémenter la variable \texttt{n}. 
Il faut s'assurer également que la condition finira
par devenir fausse, sous peine que la boucle ne s'arrête
plus (c'est ce qu'on appelle un \og plantage \fg). 
Il n'y a pas ces difficultés avec une boucle bornée, 
pour laquelle l'initialisation, l'incrémentation
et l'arrêt sont en général assurés.
\end{Exemple}

\begin{solintro}
Il s'agit de répéter le calcul de $f(x)$, $x$ prenant les valeurs $0$, $1$, etc. jusqu'à $20$. 

Une boucle POUR paraît toute indiquée. 

\begin{algorithme}{Algorithme}
Variable : x
Début
\quad x $\leftarrow$ 0
\quad Pour x allant de 0 à 20
\qquad y $\leftarrow$ (2*x**2+x)/(x**2+2*x+1)
\qquad Afficher y
\quad Fin Pour
Fin		
\end{algorithme}


\begin{listing}{En Python}{01-crs-09.py}\end{listing}
\end{solintro}


\section{Comment écrire une fonction en Python ?}


\begin{exointro}{Lycée Marie Curie, Sceaux}
On considère la fonction $f$ définie sur $\R\setminus\{-1\}$ donnée par: \[f(x)=\dfrac{2x^2-1}{x+1}.\] 

Programmer la fonction \texttt{f(x)} en Python.
\end{exointro}


En mathématiques, une fonction $f$ utilise un nombre $x$
pour calculer une valeur $f(x)$.

Une fonction Python généralise ce principe.
À partir d'un \emph{argument} \texttt{x} (parfois plusieurs, 
parfois aucun !), elle exécute un certain nombre
d'instructions et renvoie une valeur. Pour programmer
une fonction, on utilise le mot-clé \emph{def}. 
Le nom de la fonction doit vérifier les règles habituelles
des noms de variables. 

Ne pas oublier qu'un ordinateur fait ce qu'on lui demande,
certes très vite, mais qu'il ne prend pas d'initiative. Lui 
demander de calculer une valeur ne suffit pas : il faut
demander que cette valeur soit \emph{communiquée}, d'une manière ou d'une autre. 

Prenons l'exemple de la fonction carré. 
Le programme~: 

\begin{listing}{}{01-crs-10.py}\end{listing}

\Par

ne contient pas de faute de langage. Cependant, 
il n'est pas satisfaisant parce que la fonction f 
calcule bien le carré de la variable x, mais
le résultat du calcul est perdu.  On peut penser à utiliser \verb+print+ : 

\begin{listing}{}{01-crs-11.py}\end{listing}

\Par

C'est déjà mieux, le résultat du calcul sera affiché
à l'écran. Cependant, on ne peut pas utiliser $f(x)$
dans un calcul comme on le fait en mathématiques.
par exemple : \verb' 1+f(2)' va déclencher une erreur. 

Le mieux est de demander à la fonction de renvoyer 
le résultat calculé à l'aide du mot-clé : \verb+ return+.  Par exemple, la fonction \og carré \fg s'écrit en Python~:

\begin{listing}{}{01-crs-12.py}\end{listing}

\Par

On peut ensuite utiliser la fonction dans un autre
programme~:

\begin{listing}{}{01-crs-13.py}\end{listing}

\Par

À la première ligne, on \og appelle \fg \texttt{f(2)}. 
Cette valeur est évaluée en remplaçant le \texttt{x} de
la définition de \texttt{f} par 2. La fonction \texttt{f}
renvoie alors la valeur 4, et c'est donc 4 qui est affiché. 
Dans l'instruction suivante, qui est une affectation,
on évalue \texttt{f(3)}, c'est-à-dire 9, et c'est donc 10 qui est stocké dans 
\texttt{y}, puis affiché. 

En fait, nous avons déjà rencontré des fonctions, 
comme \texttt{print} et même \texttt{range}.

On notera que \texttt{def} ou \texttt{return} ne 
sont pas suivis de parenthèses car ce sont
des mots-clés et non des fonctions.

\enlargethispage*{3em}

\begin{solintro}
La définition de la fonction commence par 
le mot-clé \verb+ def+. 
Il faut penser à bien indenter la séquence d'instructions
et utiliser \verb+ return+ pour renvoyer la valeur
calculée. 

\begin{listing}{}{01-crs-14.py}\end{listing}
\end{solintro}