\chapter{Algorithmique}

\begin{exointro}{Lycée Camille Claudel, Blois}
\'Etant donnée une série de $n$ valeurs $x_1$, $x_2$, \ldots, $x_n$, on appelle \textit{variance} le nombre :
\[
V = \dfrac{1}{n}\sum_{i=1}^n\big(\Moy{x}-x_i\big)^2,\quad\text{où $\Moy{x}$ représente la moyenne des $n$ valeurs.}
\]
\begin{questions}
\item En supposant la moyenne connue, écrire un algorithme permettant de calculer la variance de $n$ valeurs.
\item Montrer que cet algorithme est de coût linéaire.
\item Dans quel cas cet algorithme peut-il être de coût quadratique ?
\end{questions}
\vspace*{-1em}
\end{exointro}

\enlargethispage*{\baselineskip}
Nous avons vu au chapitre 3 qu'il existait beaucoup de langages de\linebreak programmation, chacun ayant ses spécificités, mais tous ayant quelques points en commun.

Le point commun le plus important est la façon dont les programmes sont construits : leurs algorithmes, qui constituent la base de tout programme.

\section{Introduction}

\subsection{Définition}

\begin{defins}
Un \textit{algorithme} est une succession d'instructions permettant d'aboutir à un\linebreak résultat souhaité.

\Par

L'\textit{algorithmique} est l'étude et la conception de règles permettant d'écrire des algorithmes.
\end{defins}

Autrement dit, l'algorithmique va nous permettre d'écrire un algorithme qui, une fois traduit en un langage, va donner un programme.

\subsection{Historique}

Le mot \og algorithme \fg{} vient du nom du mathématicien perse \textit{Al-Khwârizmî}.

On retrouve les premières traces d'algorithmes dans la civilisation babylonienne, où des méthodes de calculs et de résolutions d'équations sont décrites. L'un des algorithmes les plus connus est celui d'Euclide, permettant de calculer le plus grand commun diviseur de deux nombres entiers, et présent dans le livre 7 des \textit{Éléments}, recueil mathématique de 13 livres écrit par Euclide lui-même. Fait remarquable : cet algorithme contient une itération (c'est-à-dire que l'on y voit la répétition d'un même processus) et la démonstration du fait que l'algorithme fait ce qu'on lui demande (on dit dans ce cas que l'algorithme est  \textit{correct}).

Un second algorithme connu par les mathématiciens est celui d'Archimède pour calculer le nombre $\pi$.

\Par

De nos jours, il existe plusieurs types d'algorithmiques. Citons par exemple :
\begin{itemize}
\item l'algorithmique itérative;
\item l'algorithmique récursive;
\item l'algorithmique parallèle.
\end{itemize}
Selon l'algorithmique choisie, l'algorithme n'aura pas la même structure.

\section{Parcours séquentiel d'un tableau}

\subsection{Recherche d'une occurrence}

Dans ce paragraphe, on s'intéresse à la recherche d'une occurrence sur des valeurs de type quelconque : nombres, chaînes de caractères ou tableaux.

Nous allons noter \texttt{b} l'élément recherché et \texttt{a[0]}, \texttt{a[1]}, ..., \texttt{a[n-1]} les $n$ éléments parmi lesquels \texttt{b} est recherché. 

Pour cela, une simple boucle itérative bornée suffit :

\enlargethispage*{2\baselineskip}

\begin{algorithme}{}
p $\leftarrow$ Faux (p est un booléen)
Pour i allant de 0 à n-1:
\quad Si b = a[i] alors:
\qquad	p $\leftarrow$ Vrai
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

On voit ici qu'il est nécessaire d'effectuer $n+1$ affectations : une avant la boucle, et $n$ dans la boucle. Ceci n'est pas la méthode la plus efficace car on effectue $n$ itérations même si l'élément recherché est le premier du tableau.


\subsection{Recherche d'un extremum}

Dans ce paragraphe, on recherche les valeurs minimale et maximale sur une liste de $n$ nombres \texttt{a[0]}, \texttt{a[1]}, ..., \texttt{a[n-1]}.

Là encore, une simple boucle itérative bornée suffit :

\begin{algorithme}{}
Pour i allant de 0 à n-1:
\quad Si i=0 alors:
\qquad min $\leftarrow$ a[0]
\qquad max $\leftarrow$ a[0]
\quad Fin du Si
\quad Si a[i]$<$min alors:
\qquad min $\leftarrow$ a[i]
\qquad Sinon:
\qquad\quad Si a[i]$>$max alors:
\qquad\qquad max $\leftarrow$ a[i]
\qquad\quad Fin du Si
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

On constate ici qu'il y a :
\begin{itemize}
\item 2 affectations (\texttt{min $\leftarrow$ a[0]} et \texttt{max $\leftarrow$ a[0]});
\item au maximum $n-1$ affectations pour \texttt{min $\leftarrow$ a[i]} ou \texttt{max $\leftarrow$ a[i]} (les deux affectations ne peuvent pas survenir en même temps).
\end{itemize}
Il y a donc au maximum $n+2$ affectations.

\subsection{Calcul d'une moyenne}

On souhaite ici calculer la moyenne des valeurs \texttt{a[0]}, \texttt{a[1]}, ..., \texttt{a[n-1]}.

Encore une fois, une simple boucle itérative bornée suffit :

\begin{algorithme}{}
m $\leftarrow$ 0
Pour i allant de 0 à n-1:
\quad m $\leftarrow$ m + a[i]
Fin du Pour
m $\leftarrow$ m/n
\end{algorithme}

\Par

Ici, \texttt{m} est la variable dans laquelle est stockée la moyenne à la fin de la boucle. En effet, on sait que la moyenne de $n$ nombres se calcule ainsi :
\[
m = \dfrac{a_0+a_1+\cdots+a_{n-1}}{n}=\dfrac{a_0}{n}+\dfrac{a_1}{n}+\cdots+\dfrac{a_{n-1}}{n}.
\]
\enlargethispage*{3em}
On constate alors qu'il y a ici :
\begin{itemize}
\item $n+2$ affectations (\texttt{m $\leftarrow$ 0}, $n$ affectations dans la boucle et \texttt{m $\leftarrow$ m/n});
\item $n$ opérations arithmétiques (une addition par itération).
\end{itemize}
Il y a ainsi $2n+2$ affectations et opérations arithmétiques.

\subsection{Le coût d'un algorithme}
\label{cout-algo-moyenne}

\subsubsection{Définition}

\begin{defin}
Le \textit{coût d'un algorithme} est le nombre d'opérations élémentaires (arithmétiques ou logiques) ainsi que d'affectations nécessaires à son exécution.
\end{defin}

Ainsi,
\begin{itemize}
\item pour la recherche d'une occurrence, le coût de l'algorithme est égal à $n+1$;
\item pour la recherche d'un extremum, il est égal à $n+2$;
\item pour le calcul de la moyenne, il est égal à $2n+2$.
\end{itemize}

\begin{aretenir}
Dans la pratique, le coût est souvent une approximation.

\Par

Ainsi, on dira que le coût de l'algorithme du calcul de la moyenne de $n$ nombres est de l'ordre de $2n$. 

\Par

Concrètement, dans un algorithme comportant une seule boucle, le coût est généralement proportionnel au nombre d'itérations effectuées. En revanche, dans le cas de boucles imbriquées, le coût dépend du produit du nombre d'itérations de chaque boucle.
\end{aretenir}

\subsubsection{Coût linéaire et coût quadratique}

\begin{defins}
On dira qu'un algorithme a un \textit{coût linéaire} si son approximation est de la forme $kn$, où $k>0$.

On dira qu'un algorithme a un \textit{coût quadratique} si son approximation est de la forme $kn^2$, où $k>0$.
\end{defins}

\begin{Exemples}
\begin{itemize}
\item Les algorithmes précédents ont des coûts linéaires.
\item Si le coût calculé précisément est égal à $2n^2+n+2$ alors son approximation est $2n^2$ et il est alors quadratique. 
\end{itemize}
\end{Exemples}

\newpage

\section{Tris}

\subsection{Tris par insertion}

\subsubsection{Principe}

\begin{defin}
L'algorithme de \textit{tri par insertion} est l'algorithme de tri \og naturel \fg.
\end{defin}

\begin{Exemple}
\label{exemple-tri}
soit le tableau \texttt{t = [8,5,1,9,7]} à trier.
\begin{itemize}
\item 1\iere{} itération : \texttt{[8,5,1,9,7]} devient \texttt{[5,8,1,9,7]};
\item 2\ieme{} itération : \texttt{[5,8,1,9,7]} devient \texttt{[1,5,8,9,7]};
\item 3\ieme{} itération : \texttt{[1,5,8,9,7]} devient \texttt{[1,5,7,8,9]}.
\end{itemize}
\end{Exemple}

L'algorithme est le suivant :

\begin{algorithme}{}
t est un tableau de n valeurs
Pour i allant de 1 à n-1:\hfill(1)
\quad x $\leftarrow$ t[i]\hfill(2)
\quad j $\leftarrow$ i\hfill(3)
\quad Tant que j $>$ 0 et t[j-1] $>$ x:\hfill(4)
\qquad t[j] $\leftarrow$ t[j - 1]\hfill(5)
\qquad j $\leftarrow$ j - 1\hfill(6)
\quad Fin du Tant que
\quad t[j] $\leftarrow$ x\hfill(7)
Fin du Pour
\end{algorithme}

\Par

Explications :
\begin{itemize}
\item la boucle itérative (ligne~1) parcourt le tableau \texttt{t};

\item ensuite, on affecte à la variable \texttt{x} la valeur sur laquelle on est (ligne~2);

\item on introduit ensuite (ligne~3) une variable auxiliaire \texttt{j} qui prend la valeur du rang auquel on est (\texttt{i});

\item on créé une boucle conditionnelle \og Tant que \fg{} pour exécuter des instructions quand les valeurs précédentes sont inférieures à celle sur laquelle on est (celle de rang \texttt{i}) (ligne~4);

\item dans ce dernier cas, la valeur de rang \texttt{j} devient celle de rang \texttt{j-1} (ligne~5) et on passe au rang précédent (ligne 6);

\item la boucle conditionnelle étant terminée, la valeur qui était auparavant au rang \texttt{i} est mise au rang \texttt{j}: le premier rang nul ou pour lequel \texttt{t[j-1] $\leqslant$ x} (ligne 7).
\end{itemize}

\newpage

Regardons ce qui se passe pour la première itération (\texttt{i=1}) sur l'exemple\linebreak précédent :
\begin{itemize}
\item \texttt{x $\leftarrow$ 5} car \texttt{t[1]=5} (ligne 2) et \texttt{j $\leftarrow$ 1} (ligne 3);

\item \texttt{j>0} et \texttt{8>5} donc on entre dans la boucle conditionnelle (ligne 4);

\item \texttt{t[1] $\leftarrow$ 8} (ligne 5) et \texttt{j $\leftarrow$ 0} (ligne 6);

\item la condition \texttt{j>0} n'est plus remplie (ligne 4) donc la boucle conditionnelle est terminée. Alors, \texttt{t[0] $\leftarrow$ 5} (ligne 7).
\end{itemize}

\subsubsection{Terminaison de l'algorithme}

La boucle itérative (ligne 1) ne pose aucun problème. En revanche, une boucle conditionnelle (ligne 4) est dangereuse car il se peut qu'elle ne se termine jamais.

Dans notre algorithme, la condition de la boucle est de la forme \og $c_1$ et $c_2$ \fg, où $c_1$ et $c_2$ sont deux conditions. La boucle s'arrête quand \og non($c_1$ et $c_2$) \fg{} est vérifiée, c'est-à-dire quand \og non($c_1$) ou non($c_2$) \fg{} est vérifiée. Il faut donc qu'au moins l'une des conditions contraires soit vérifiée.

Dans notre algorithme, \texttt{j} est décrémentée à chaque fois, donc nous sommes assurés que la condition \texttt{j>0} ne sera plus remplie à une certaine étape. 

Ceci nous assure que l'algorithme se termine.

\subsubsection{Correction de l'algorithme}

Posons $P(i)$ la propriété :
\begin{center}
$P(i)$\quad:\quad\og le tableau [t[0], t[1],...,t[i-1]] est trié. \fg{} 
\end{center}

On peut montrer que pour tout \texttt{i} variant de 1 à \texttt{n-1}, donc à chaque itération, $P(i)$ est vraie.

Comme $P(n-1)$ signifie que le tableau entier est trié, l'algorithme est correct.

\begin{methode}[invariant de boucle]
La propriété $P(i)$ est appelée un \textit{invariant de boucle} : c'est une propriété qui est vraie avant et après chaque itération. S'il existe un invariant de boucle alors l'algorithme est correct.
\end{methode}

\subsubsection{Coût de l'algorithme}

Le pire des cas que l'on peut rencontrer est un tableau où toutes les valeurs sont dans l'ordre décroissant (comme \texttt{[9,8,7,5]} par exemple).

Dans ce cas, pour chaque itération, il y a $2$ affectations (lignes 2 et 3), puis $2n$ affectations (lignes 5 et 6) et enfin 1 affectation (ligne 7), soit $2n+3$ affectations.

Il y a $n$ itérations, donc au final, il y a $n(2n+3)$ affectations, ce qui entraîne un coût approximatif de $2n^2$.

\begin{prop}
Le coût de l'algorithme de tri par insertion est quadratique.
\end{prop}

\subsection{Tri par sélection}

\subsubsection{Principe}

\begin{defin}
L'algorithme de \textit{tri par sélection} consiste à :
\begin{itemize}
\item rechercher le plus petit élément d'un tableau de valeurs et l'échanger avec l'élément d'index 0;
\item rechercher le second plus petit élément du même tableau et à l'échanger avec l'élément d'index 1;
\item de continuer ainsi avec les autres éléments.
\end{itemize}
\end{defin}

\begin{Exemple}
reprenons le tableau de l'exemple \ref{exemple-tri} : \texttt{t = [8,5,1,9,7]}.
\begin{itemize}
\item \texttt{t = [8,5,1,9,7]} devient \texttt{t = [1,5,8,9,7]};
\item \texttt{t = [1,5,8,9,7]} devient \texttt{t = [1,5,8,9,7]} (le \og 5 \fg{} ne bouge pas);
\item \texttt{t = [1,5,8,9,7]} devient \texttt{t = [1,5,7,9,8]};
\item \texttt{t = [1,5,7,9,8]} devient \texttt{t = [1,5,7,8,9]}.
\end{itemize}
\end{Exemple}

L'algorithme est le suivant :

\begin{algorithme}{}
Pour i allant de 0 à n - 2:\hfill(1)
\quad min $\leftarrow$ i\hfill(2)
\quad Pour j allant de i+1 à n-1:\hfill(3)
\qquad Si t[j] $<$ t[min]:\hfill(4)
\qquad\quad min $\leftarrow$ j\hfill(5)
\qquad Fin du Si
\quad Fin du Pour
\quad Si min $\neq$ i:\hfill(7)
\qquad x $\leftarrow$ t[min]\hfill(8)
\qquad t[min] $\leftarrow$ t[i]\hfill(9)
\qquad t[i] $\leftarrow$ x\hfill(10)
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

L'algorithme ne comporte que des boucles bornées donc il se termine nécessairement.

\subsubsection{Correction de l'algorithme}

Posons $P(i)$ la propriété :
\begin{center}
$P(i)$\quad:\quad\og À la fin de la boucle Pour sur \texttt{i}, le tableau obtenu est un tableau ne contenant que des valeurs du tableau initial, et les $i$ premiers éléments de ce tableau coïncident avec ceux du tableau final. \fg
\end{center}
C'est un invariant de boucle, donc l'algorithme est correct.

\subsubsection{Coût de l'algorithme}

Dans le \og pire \fg{} des cas, pour chaque itération de \texttt{i}, il y a :
\begin{itemize}
\item 1 affectation (ligne 2);
\item $n-i-1$ affectations (ligne 5) car il y a $n-i+1$ valeurs de \texttt{j} (ligne 3);
\item 3 affectations (lignes 8, 9 et 10).
\end{itemize}
Le nombre total d'affectations est donc :
\begin{align*}
\sum_{i=0}^{n-2}(3+n-i) & = \sum_{i=0}^{n-2}3 + \sum_{i=0}^{n-2}(n-i)\\
& = 3(n-1) + \dfrac{n(n+1)}{2}-1\\
& = \dfrac{1}{2}n^2+\dfrac{7}{2}n-4.
\end{align*}

\begin{prop}
Le coût de l'algorithme de tri par sélection est quadratique.
\end{prop}

\section{Algorithme des k plus proches voisins}

\subsection{Première approche}

\begin{defin}
\'Etant donnés $n$ nombres $x_0$, $x_1$, ..., $x_{n-1}$ décrivant un ensemble $X$, l'algorithme des $k$ plus proches voisins consiste à trouver les $k$ valeurs de $X$ les plus proches d'un nombre $x$ donné.
\end{defin}

Pour cela, \enlargethispage*{2em}
\begin{itemize}
\item on prend les $k$ premières valeurs de $X$ : $x_0$, ..., $x_{k-1}$, et on les met dans un ensemble $Y$;
\item on note $y$ la valeur de $Y$ la plus éloignée de $x$;
\item pour chaque valeur restante de $X$, si elle est plus proche de $x$ que $y$ alors on remplace $y$ par cette valeur.
\end{itemize}
On obtient :

\begin{algorithme}{}
/* on met les k premiers éléments de X dans Y */
Pour i allant de 0 à k-1:
\quad y[i] $\leftarrow$ x[i]
Fin du Pour\\
/* on parcourt les éléments restants de X */
Pour i allant de k à n-1:
\quad Pour j allant de 0 à k-1:\hfill(1)
\qquad Si j=0:
\qquad\quad d $\leftarrow$ |x-y[0]|
\qquad\quad r $\leftarrow$ 0
\qquad Sinon:
\qquad\quad Si |x-y[j]| $>$ d:
\qquad\qquad d $\leftarrow$ |x-y[j]| 
\qquad\qquad r $\leftarrow$ j
\qquad\quad Fin du Si
\qquad Fin du Si
\quad Fin du Pour\hfill(2)

/* à ce stade, "d" représente la plus grande distance et 
"r" l'index du  terme le plus éloigné de x */

\quad Si |x-x[i]| $<$ d:\hfill(3)
\qquad y[r] $\leftarrow$ x[i]\hfill(4)
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

Pour chaque itération de $k$ à $n-1$,
\begin{itemize}
\item entre les lignes (1) et (2), on détermine la distance la plus grande entre $x$ et toutes les valeurs de $Y$ ainsi que le rang du terme (\texttt{r}) le plus éloigné de $x$;


\item ensuite, on teste si la valeur de rang \texttt{i} est plus proche de $x$ que le terme le plus éloigné de $Y$ (ligne 3). Si tel est le cas, on remplace cette valeur (la plus éloignée de $x$) par \texttt{x[i]} (ligne (4)).
\end{itemize}

\subsection{Généralités}

L'algorithme des $k$ plus proches voisins est en réalité un peu plus complexe que ce que nous venons de voir. En effet, dans la pratique, il permet de \og prédire \fg{} la\linebreak nature d'un élément (on parle ici de \textit{classe} de l'élément) informé à partir\linebreak d'éléments déjà enregistrés. 

\newpage

Prenons un exemple visuel : dans un repère, on considère une série de $n$ points de coordonnées $(x_i~;y_i)$, $i$ variant de $0$ à $n-1$. Chaque point est de couleur bleue ou rouge. On met ensuite un point au hasard (en vert) :

\Par

\begin{center}
\includegraphics{220_192_07-k-proches-voisins}
\end{center}

\Par

Ici, les éléments sont les points et leur classe est leur couleur.

L'objectif est de prédire la classe de l'élément rajouté selon nos critères. On va prendre par exemple $k=5$ et on va regarder les 5 plus proches voisins du point vert. 

On constate alors que parmi les 5 points les plus proches du point vert, 4 sont rouges et 1 est bleu. On prédit alors que la classe du point ajouté sera \og rouge \fg.

\section{Recherche dichotomique dans un tableau trié}

\subsection{Première approche}

Soit \texttt{t} un tableau de taille $n$ dont les éléments sont triés. On souhaite retrouver un élément \texttt{e} parmi les valeurs de ce tableau.

Bien sûr, on pourrait parcourir le tableau en partant du début jusqu'à trouver\linebreak l'élément, comme dans l'algorithme page suivante.

\newpage

\begin{algorithme}{}
i $\leftarrow$ 0
bingo $\leftarrow$ Faux
Tant que bingo $\neq$ Vrai ou i $<$ n:
\quad Si t[i] = e:
\qquad bingo $\leftarrow$ Vrai
\quad Sinon:
\qquad i $\leftarrow$ i+1
\quad Fin du Si
Fin du Tant que
\end{algorithme}

\Par

Le coût de cet algorithme est linéaire dans le pire des cas (si \texttt{e} se trouve à la fin du tableau). Mais on peut tout de même faire mieux en accélérant la recherche.

\subsection{Dichotomie}

Le principe est le suivant :

\begin{questions}
\item on pose \texttt{min=0]} et \texttt{max=n-1};
\item\label{dicho} on prend le milieu \texttt{t[m]} de l'intervalle \texttt{[min~;~max]};
\item si \texttt{t[m]=e} alors on a fini;
\item si \texttt{t[m] > e} alors on pose \texttt{max=m}, sinon on pose \texttt{min=m} et on\linebreak retourne au point \ref{dicho}.
\end{questions}

Dans la pratique, il faudra faire attention au fait que \texttt{m} n'est pas toujours un entier; il faudra donc faire en sorte qu'il le soit.

Avant de voir l'algorithme en lui-même, regardons sur un exemple son fonctionnement.

\begin{Exemple}
soit \texttt{t = [1,2,5,7,8,9,12,15,16,18,19,23,25,26,27,30]}.

Alors \texttt{min=0, max=15}. Prenons \texttt{e = 9}.
\begin{itemize}
\item \texttt{0 < 15} donc on pose $m=E\left(\dfrac{0+15}{2}\right)=7$.

\Par

\texttt{t[7]=15 > 9} donc \texttt{max = m = 7}, en gardant \texttt{min = 0}.

\item \texttt{0 < 7} donc on recommence : $m=E\left(\dfrac{0+7}{2}\right)=3$.

\Par

\texttt{t[3]=7 < 9} donc \texttt{min = m = 3}, en gardant \texttt{max = 7}.

\item \texttt{3 < 7} donc on recommence : $m=E\left(\dfrac{3+7}{2}\right)=5$.

\Par

\texttt{t[5]=9}. On a trouvé ! On arrête donc la boucle.
\end{itemize}
\end{Exemple}

\newpage

L'algorithme itératif est alors le suivant :

\begin{algorithme}{}
min $\leftarrow$ 0
max $\leftarrow$ n-1
Tant que min $<$ max:
\quad m $\leftarrow$ E((min + max)/2)
\quad Si t[m] $<$ e:
\qquad min $\leftarrow$ m+1
\quad Sinon:
\qquad max $\leftarrow$ m
\quad Fin du Si
Fin du Tant que

Si t[min] = e:
\quad Afficher min
Sinon:
\quad Afficher : "Non trouvé"
\end{algorithme}

\Par

Nous parlons ici d'\textit{algorithme itératif} car vous verrez l'année prochaine qu'un\linebreak \textit{algorithme récursif} existe.

\begin{Remarque}
cet algorithme n'est bien entendu pas unique. Il existe d'autres\linebreak syntaxes, mais le fond reste le même.
\end{Remarque}

\subsection{Terminaison de l'algorithme}

\begin{methode}[variant de boucle]
Pour démontrer qu'une boucle conditionnelle de type \og Tant que \fg{} se termine, on considère un entier qui décroît à chaque itération. 

Cette quantité est appelée \textit{variant de boucle}.
\end{methode}

Dans notre algorithme, \texttt{min} et \texttt{max} sont deux entiers naturels, par conséquent la variable \texttt{d = max - min} est aussi un entier naturel. Elle n'est pas présente dans notre algorithme, mais nous pourrions la définir.

À chaque itération, \texttt{d} décroît car soit \texttt{min} augmente, soit \texttt{max} diminue. Ainsi, il existe une itération pour laquelle \texttt{d} ne sera pas strictement positive : la boucle \og Tant que \fg{} s'arrêtera alors, ce qui prouve la terminaison de l'algorithme.

\newpage

\section{Algorithmes gloutons}

\subsection{Principe général}

Les algorithmes gloutons existent pour résoudre des \textit{problèmes d'optimisation}. Ils correspondent à une solution optimale obtenue en effectuant une suite de meilleurs choix pour chaque étape de l'algorithme (à chaque étape, on fait le meilleur choix possible).

De plus, il n'y a pas de retour en arrière : quand un choix est fait à une étape, il n'est pas modifié ultérieurement et il ne modifie pas les choix précédents.

L'autre caractéristique des algorithmes gloutons est que lorsqu'un choix est fait, on tente de résoudre un problème plus petit. 

On appelle cela la \textit{progression descendante}.

\subsection{Le problème du rendu de monnaie}

Nous allons illustrer ce qu'est un algorithme glouton à travers l'un des plus\linebreak célèbres problèmes : \og étant donné un système de monnaie (pièces et billets),\linebreak comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ? \fg{} 

\Par

Plaçons-nous dans notre système de monnaie; nous disposons alors de la monnaie suivante (toutes les valeurs sont exprimées en euros) :
\begin{itemize}
\item \textit{pièces} : 0,01 -- 0,02 -- 0,05 -- 0,10 -- 0,20 -- 0,50 -- 1 -- 2 ;
\item \textit{billets} : 5 -- 10 -- 20 -- 50 -- 100 -- 200 -- 500.
\end{itemize}

Notons:
\begin{itemize}
\item $S$ ce système (composé donc de 15 valeurs) : c'est un tableau trié;
\item $m$ le montant à obtenir;
\item $T$ le tableau contenant (à la fin de l'algorithme) toutes les valeurs telles que leur somme soit égale à m;
\end{itemize}

Alors, l'algorithme glouton correspondant à notre problème est le suivant :\enlargethispage*{\baselineskip}

\begin{algorithme}{}
i $\leftarrow$ 14, r $\leftarrow$ 0
Tant que m $\neq$ 0:
\quad Si m $\geqslant$ S[i]:
\qquad T[r] $\leftarrow$ S[i]
\qquad r $\leftarrow$ r+1
\qquad m $\leftarrow$ m - S[i]
\quad Sinon:
\qquad i $\leftarrow$ i-1
\quad Fin du Si
Fin du Tant que
\end{algorithme}

\newpage

Voyons chacune des étapes pour $m=746$ :

\Par

\begin{center}
\begin{tabular}{|*6{Zc|}}
\tabulartitle\hline
T & m & i & r & $m \neq 0$ & $m \geqslant S[i]$  \\
\hline
[] & 746 & 14 & 0 & vrai & vrai \\
\hline
[500] & 246 & 14 & 1 & vrai & faux \\
\hline
[500] & 246 & 13 & 1 & vrai & vrai\\
\hline
[500,200] & 46 & 13 & 2 & vrai & faux\\
\hline
[500,200] & 46 & 12 & 2 & vrai & faux\\
\hline
[500,200] & 46 & 11 & 2 & vrai & faux\\
\hline
[500,200] & 46 & 10 & 2 & vrai & vrai\\
\hline
[500,200,20] & 26 & 10 & 3 & vrai & vrai\\
\hline
[500,200,20,20] & 6 & 10 & 4 & vrai & faux\\
\hline
[500,200,20,20] & 6 & 9 & 4 & vrai & faux\\
\hline
[500,200,20,20] & 6 & 8 & 4 & vrai & vrai\\
\hline
[500,200,20,20,5] & 1 & 7 & 5 & vrai & faux\\
\hline
[500,200,20,20,5] & 1 & 8 & 5 & vrai & faux\\
\hline
[500,200,20,20,5] & 1 & 6 & 5 & vrai & vrai\\
\hline
[500,200,20,20,5,1] & 0 & 6 & 6 & faux & ---\\
\hline
\end{tabular}
\end{center}

\begin{anecdote}\label{anecdote-algo-glouton}
Pourquoi n'y a-t-il pas de pièces ou de billets de 7 \euro ? Parce que si tel était le cas, l'algorithme glouton du rendu de monnaie ne serait plus optimal (alors qu'il l'est avec le système monétaire actuel). 

En effet, supposons qu'il y ait une pièce ou un billet de 7 \euro. Sur un montant de 14 \euro, l'algorithme donne la décomposition $
14 = 10 + 2 + 2$ alors que la décomposition $14 = 7 + 7$ serait optimale.

Afin que l'algorithme glouton soit optimal, il est nécessaire qu'un système monétaire soit au minimum composé des premiers termes d'une suite \textit{super-croissante}, c'est-à-dire une suite $(u_n)$ telle que pour tout entier naturel $n$,
\[
u_{n+1}>\sum_{k=0}^{n}  u_k.
\]
Mais ce n'est pas suffisant (ça le serait si on ne pouvait rendre qu'une pièce ou qu'un billet d'un montant donné, ce qui n'est pas le cas).

On dit que le système est \textit{canonique} s'il est composé de valeurs d'une suite super-croissante et si l'algorithme glouton est optimal; le système monétaire européen est canonique.
\end{anecdote}

\newpage

\begin{solintro}
\begin{questions}
\item Un algorithme de calcul de la variance est le suivant :

\begin{algorithme}{}
V $\leftarrow$ 0
m $\leftarrow$ moyenne
Pour i allant de 1 à n:
\quad V $\leftarrow$ V + (m-x[i])*(m-x[i])
Fin du Pour
V $\leftarrow$ V/n
\end{algorithme}

\item En dehors de la boucle itérative, il y a 3 affectations.

Dans la boucle, il y a 1 affectation par itération. Donc en tout, il y a $n+3$ affectations.

Le coût de l'algorithme est alors linéaire.

\item Supposons que la moyenne ne soit pas connue (ce qui est souvent le cas quand un utilisateur entre les valeurs au clavier). Il faut alors la calculer :

\begin{algorithme}{}
V $\leftarrow$ 0
Pour i allant de 1 à n:
\quad V $\leftarrow$ V + (moyenne(X)-x[i])*(moyenne(X)-x[i])
Fin du Pour
V $\leftarrow$ V/n
\end{algorithme}

\Par

Dans ce cas, on suppose que la fonction \texttt{moyenne(X)} calcule la moyenne des valeurs du tableau \texttt{X}. Cette fonction  est de coût linéaire (comme nous l'avons vu dans le cours) et il y a $n$ affectations (1 par itération); le coût final est donc d'ordre $n \times n$, soit quadratique.
\end{questions}

\begin{aretenir}
Si \texttt{f} est une fonction à coût linéaire, alors la boucle :

\begin{algorithme}{}
Pour i allant de 1 à n:
   x $\leftarrow$ x + f(i)
Fin du Pour
\end{algorithme}

\Par

est à coût quadratique.
\end{aretenir}
\end{solintro}