\thumb

\begin{qcm}{Coût d'un algorithme}{5} % titre , temps
Pour chacune des questions suivantes, 2 choix sont proposés. Quel est le bon ?
\begin{questions}
\item Le coût d'un algorithme de tri par insertion est :

\choix linéaire

\choix quadratique

\item\resetchoix Le coût d'un algorithme de recherche dans un tableau est :

\choix linéaire

\choix quadratique

\item\resetchoix Le coût d'un algorithme de recherche de maximum est :

\choix linéaire

\choix quadratique

\item\resetchoix Un algorithme dans lequel il y a une boucle itérative qui appelle une fonction de coût linéaire a un coût :

\choix linéaire

\choix quadratique
\end{questions}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[b]. Un algorithme de tri par insertion  (comme par sélection) a un coût quadratique.

\item Réponse \choix[a]. Un algorithme de recherche séquentielle dans un tableau a un coût linéaire.

\item Réponse \choix[a]. Un algorithme de recherche séquentielle dans un tableau a un coût linéaire.

\item Réponse \choix[b]. En effet, la boucle itérative peut entraîner $n$ affectations, et pour chacune d'elles, il y en a $n$ autres (parce que la fonction appelée est de coût linéaire). Ainsi, il y aura un coût d'environ $n \times n=n^2$. 

Le coût est donc quadratique.
\end{questions}
\end{corrige}


%%%


\begin{vf}{Connaître le cours}{5} % titre , temps
Les affirmations suivantes sont-elles vraies ou fausses ?
\begin{questions}
\item Le coût d'un algorithme de calcul de moyenne est linéaire.
\item Les algorithmes gloutons donnent toujours une solution optimale.
\item Un variant de boucle permet de corriger un algorithme.
\item Un algorithme dans lequel il y a une boucle itérative dans une autre boucle itérative peut avoir un coût quadratique. 
\end{questions}
\end{vf}

\begin{corrige}
\begin{questions}
\item La proposition est \textit{vraie}. Nous l'avons vu dans le cours, à la page \pageref{cout-algo-moyenne}.

\item La proposition est \textit{fausse}. Nous avons vu dans le cours un contre-exemple sur le problème du rendu de monnaie quand on utilise un système non canonique (voir l'anecdote de la page \pageref{anecdote-algo-glouton}).

\item La proposition est \textit{fausse}. En effet, pour corriger un algorithme, on\linebreak utilise un \textit{invariant} de boucle (et non un \textit{variant}).

\item La proposition est \textit{vraie}. En effet, si la première boucle itérative est du type \og Pour i allant de 1 à n \fg{} et si la seconde est de la forme \og Pour j allant de 1 à n \fg, alors il y aura $n \times n$ affectations au minimum, ce qui donne un coût quadratique à l'algorithme.
\end{questions}
\end{corrige}

\sectionnn{Algorithmes de tri}

\begin{exo}{Tri à bulle}{Lycée François Mauriac, Bordeaux}{1}{15} 
On considère l'algorithme de la page ci-contre.
\begin{questions}
\item Si \texttt{a=[3,2,1]} au début de l'algorithme, qu'en est-il à la fin ?
\item Expliquer ce que fait cet algorithme.
\item Quel est son coût dans le pire des cas ?
\end{questions}

\begin{algorithme}{}
a est un tableau de n valeurs
passage $\leftarrow$ 0
permut $\leftarrow$ Vrai
Tant que permut = Vrai:
\quad permut $\leftarrow$ Faux
\quad Pour i allant de 0 à n-2-passage:
\qquad Si a[i] $>$ a[i+1]:
\qquad\quad temp $\leftarrow$ a[i+1]
\qquad\quad a[i+1] $\leftarrow$ a[i]
\qquad\quad a[i] $\leftarrow$ temp
\qquad\quad permut $\leftarrow$ Vrai
\qquad Fin du Si
\quad Fin du Pour
\quad passage $\leftarrow$ passage + 1
Fin du Tant que
\end{algorithme}
\end{exo}

\begin{corrige}
\begin{questions}
\item Au début, \texttt{passage=0}, \texttt{permut=Vrai} et \texttt{n=3}.
\begin{itemize}
\item Entrée dans la boucle itérative : \texttt{i=0}. \texttt{a[0] > a[1]} ($3>2$) donc \texttt{temp=2}, \texttt{a[1]=3}, \texttt{a[0]=2} et \texttt{permut=Vrai}.
\item \texttt{i=1} : \texttt{a[1]>a[2]} ($3>1$) donc \texttt{temp=1}, \texttt{a[2]=3}, \texttt{a[1]=1} et\linebreak \texttt{permut=Vrai}.
\item Fin du Pour : \texttt{passage=1}. À ce stade, \texttt{a=[2,1,3]}.
\item \texttt{permut=Vrai} donc on entre dans la boucle \og Tant que \fg.
\item \texttt{permut=Faux}, \texttt{n-2-passage=3-2-1=0} et \texttt{i=0} : \texttt{a[0]>a[1]} ($2>1$) donc \texttt{temp=1}, \texttt{a[1]=2}, \texttt{a[0]=1} et \texttt{permut=Vrai}.
\item Fin de la boucle itérative Pour. À ce stade, \texttt{a=[1,2,3]}, \texttt{permut=Vrai} et \texttt{passage=2}.
\item Entrée dans la boucle \og Tant que \fg{} car \texttt{permut=Vrai} : \texttt{permut=Faux} et comme \texttt{n-2-passage=-1}, on n'entre pas dans la boucle \og Pour \fg. 
\item Fin de la boucle \og Tant que \fg{}  car \texttt{permut=Faux}.
\end{itemize}
Ainsi, le tableau \texttt{[3,2,1]} devient \texttt{[1,2,3]}.

\Par

Une autre façon de représenter les résultats successifs est le tableau\linebreak suivant :

\begin{center}
\begin{tabular}{|>{\ttfamily}C|*5{Zc|}}
\hline
a & [3,2,1] & [2,3,1] & [2,1,3] & [1,2,3] & [1,2,3]\\\hline
permut & vrai & vrai & vrai & vrai & faux\\\hline
n-2-passage & 1 & 1 & 0 & -1 & --\\\hline
i & 0 & 1 & 0 & -- & --\\\hline
a[i]>a[i+1]&  vrai & vrai & vrai & --& --\\\hline
temp & 2 & 1 & 1 & -- & --\\\hline
a[i+1] & 3 & 3 & 2 & -- & --\\\hline
a[i] & 2 & 1 & 1 & -- & --\\\hline
passage & 0 & 1 & 2 & 3 & --\\\hline
\end{tabular}
\end{center}

\Par

\item La boucle itérative nous informe que l'on parcourt le tableau \texttt{a}. La boucle conditionnelle \og Si a[i] > a[i+1] \fg{} nous dit que l'on intervertit deux valeurs consécutives si la première est supérieure à la seconde.

Ainsi, on parcourt le tableau et on intervertit deux valeurs consécutives s'il le faut pour les mettre dans l'ordre croissant. Si tel est le cas, le booléen \texttt{permut} vaut \textit{Vrai}.

La boucle \og Tant que \fg{} nous informe que ce processus est répété jusqu'à ce qu'il n'y ait plus d'échange, donc jusqu'à ce que les valeurs du tableau soit toutes dans l'ordre croissant.

L'algorithme trie alors le tableau initial.

\item Le pire des cas est un tableau où toutes les valeurs sont dans l'ordre décroissant. Dans ce cas, la boucle \og Pour \fg{} effectue dans un premier temps $n-1$ itérations, puis $n-2$ itérations, etc. jusqu'à 1 itération, soit au total :
\[
\sum_{k=1}^{n-1}(n-k)=n^2-(1+2+3+\cdots+1)=n^2-\dfrac{n(n+1)}{2}=\dfrac{n^2-n}{2}
\]
itérations.

Le coût de l'algorithme est donc de l'ordre de $n^2$. 

Il est donc quadratique.
\end{questions}
\newpage
\end{corrige}

%%%

\begin{exo}{Le tri Gnome}{Lycée Camille Claudel, Blois}{2}{20} 
On considère l'algorithme suivant :

\begin{algorithme}{}
a est un tableau de n valeurs
i $\leftarrow$ 1
Tant que i $<$ n:
\quad Si a[i] $\geqslant$ a[i-1]:
\qquad i $\leftarrow$ i+1
\quad Sinon:
\qquad temp $\leftarrow$ a[i]
\qquad a[i] $\leftarrow$ a[i-1]
\qquad a[i-1] $\leftarrow$ temp
\qquad Si i $>$ 1:
\qquad\quad i $\leftarrow$ i-1
\qquad Fin du Si
\quad Fin du Si
Fin du Tant que
\end{algorithme}
\begin{questions}
\item Exécuter cet algorithme sur le tableau \texttt{a = [3,2,1]}.
\item Quel est son coût ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Aidons-nous d'un tableau pour exécuter cet algorithme ($n=3$) :

\Par

\hspace*{-3.5em}
\begin{tabular}{|>{\ttfamily\centering\arraybackslash}M{1cm}|*7{Zc|}}
\hline
a & [3,2,1] & [2,3,1] & [2,3,1] & [2,1,3] & [1,2,3] & [1,2,3] & [1,2,3]\\\hline
i & 1 & 1 & 2 & 1 & 1 & 2 & 3\\\hline
i < n & vrai & vrai &  vrai & vrai & vrai & vrai & faux\\\hline
a[i] $\geqslant$ a[i-1] & faux & vrai & faux & faux & vrai & vrai & --\\\hline
temp & 2 & -- & 1 & 1 & -- & -- & --\\\hline
a[i] & 3 & -- & 3 & 2 & -- & -- & --\\\hline
a[i-1] & 2 & -- & 1 & 1 & -- & -- & --\\\hline
i > 1 & faux & -- & vrai & faux  & -- & -- & --\\\hline
\end{tabular}

\item L'algorithme est similaire au tri par insertion, sauf que, au lieu d'insérer directement l'élément à sa bonne place, l'algorithme effectue une série de permutations, comme dans un tri bulle.

L'algorithme a donc le même coût que le tri par insertion, c'est-à-dire quadratique.
\end{questions}
\end{corrige}

%%%
\newpage
\begin{exo}{Le tri à peigne}{Lycée Sainte-Clotilde, Strasbourg}{3}{20} 
On considère l'algorithme suivant :

\begin{algorithme}{}
a est un tableau de n valeurs
gap $\leftarrow$ n-1
permut $\leftarrow$ Vrai
Tant que permut = Vrai ou gap $>$ 1:
\quad permut $\leftarrow$ Faux
\quad gap $\leftarrow$ gap / 1.3
\quad Si gap $<$ 1:
\qquad gap $\leftarrow$ 1
\quad Fin du Si
\quad Pour i allant de 1 à n-1 avec un pas de gap:
\qquad Si a[i] $>$ a[i+gap]:
\qquad\quad temp $\leftarrow$ a[i]
\qquad\quad a[i] $\leftarrow$ a[i+gap]
\qquad\quad a[i+gap] $\leftarrow$ temp
\qquad\quad permut $\leftarrow$ Vrai
\qquad Fin du Si
\quad Fin du Pour
Fin du Tant que
\end{algorithme}

\begin{questions}
\item En comparant cet algorithme aux différents algorithmes précédents,\linebreak donner son coût.

\item Quelle incidence le changement de la valeur \og 1,3 \fg{} aurait sur cet\linebreak algorithme  ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Cet algorithme ressemble à l'algorithme de tri à bulle. La différence est dans le pas de la boucle itérative (dans l'algorithme à bulle, il est égal à 1 alors qu'ici, il est variable).

L'objectif ici est de ne plus comparer uniquement les éléments adjacents d'un tableau, mais de commencer par comparer des éléments plus lointains, puis de raccourcir l'intervalle entre les éléments pour aboutir à un tri à bulle classique exécutable plus rapidement du fait que le tableau est déjà mieux trié.

Ainsi, dans le pire des cas, le coût de l'algorithme est quadratique.

\begin{Remarque}
dans le tri à bulle, les grandes valeurs en début de tableau montent rapidement vers la fin (on parle de « lièvres »), alors que les petites valeurs proches de la fin du tableau ne redescendent que très lentement vers le début (on les appelle les « tortues »).
\end{Remarque}
\enlargethispage*{5em}

\item L'instruction \texttt{gap $\leftarrow$ gap/1.3} signifie que le pas diminue de plus en plus jusqu'à valoir 1 (à l'aide de la condition \og Si gap < 1 \fg). Si on change cette valeur pour un nombre plus petit (par exemple 1.25), cela aura pour conséquence un plus grand nombre de comparaisons et donc un ralentissement de l'algorithme. 

\newpage

Au contraire, si on l'augmente légèrement, par exemple en lui attribuant la valeur de 1.5, les \og tortues \fg{} ne sont pas toutes éliminées quand le pas est devenu égal à 1, et que l'on aboutit à un tri à bulle ce qui, au final, ralentit le tri.
\end{questions}

\begin{anecdote}
Ce tri est aussi appelé le \og tri de Dobosiewicz \fg, du nom de son créateur, Wodzimierz Dobosiewicz en 1980. Il a été redécouvert et popularisé par Stephen Lacey et Richard Box dans un article publié en avril 1991 dans la revue \textit{Byte Magazine}. Les auteurs de cet article ont proposé un coefficient égal à 1,3 pour une meilleure efficacité de l'algorithme.
\end{anecdote}
\end{corrige}

\sectionnn{Correction d'algorithmes}

\enlargethispage*{5em}

\begin{exo}{Factorielle}{Lycée Henri Bergson, Angers}{1}{10} 
On considère l'algorithme suivant:

\Par

\begin{minipage}{0.33\linewidth}
\begin{algorithme}{}
i $\leftarrow$ 0
f $\leftarrow$ 1
Tant que i $<$ n:
\quad i $\leftarrow$ i+1
\quad f $\leftarrow$ f*i
Fin du Tant que
\end{algorithme}

\vspace*{2.5em}
\end{minipage}
\hfill
\begin{minipage}{0.65\linewidth}
\begin{questions}
\item Justifier que la boucle n'est pas infinie.
\item Montrer, en utilisant la pré-condition \texttt{n$\geqslant$0}, que la propriété: 
\begin{center}
$P$ : \texttt{f=i! et i$\leqslant$n}
\end{center}
est un invariant de cette boucle.
\item Formuler une post-condition qui établit la correction du programme.
\end{questions}
\end{minipage}
\end{exo}

\begin{corrige}
\begin{questions}
\item La variable \texttt{i} vaut initialement 0. À chaque itération, elle est incrémentée. Or, \texttt{n} est constante donc  il existe une itération à partir de laquelle\linebreak\texttt{i = n}, ce qui aura pour conséquence la fin de la boucle.

\item On suppose ici que \texttt{n$\geqslant$0}. 
\begin{itemize}
\item Avant d'entrer dans la boucle, \texttt{i=0} et \texttt{f=1=0!=i!} (par convention). De plus, \texttt{i} est bien inférieure ou égale à \texttt{n}, puisque les deux variables valent le même nombre.

Ainsi, la propriété $P$ est vraie avant de rentrer dans la boucle.

\item Notons \texttt{i1}, \texttt{f1} les valeurs de \texttt{i} et \texttt{f} lors d'une certaine étape, et supposons $P$ vraie à cette étape. Donc \texttt{f1 = (i1)!} et \texttt{i1 < n}.

Notons \texttt{i2} et \texttt{f2} les valeurs de ces mêmes variables après l'exécution des instructions de la boucle. On a ainsi :
\begin{center}
\texttt{i2 = i1+1 $\leqslant$ n}
\end{center}
et 
\begin{center}
\texttt{f2 = f1*(i1+1) = (i1!)*(i1+1) = (i1+1)!}.
\end{center}
Ainsi, $P$ est vraie après exécution de la boucle, donc $P$ est un invariant de la boucle.

\item À la sortie de la boucle, on a \texttt{i $\geqslant$ n} (négation de la condition), et $P$ est vraie (donc \texttt{f=i!} et \texttt{i$\leqslant$n}). Donc \texttt{i = n}, d'où \texttt{f = n!}, qui est une bonne post-condition pour prouver la correction de l'algorithme.
\end{itemize}
\end{questions}
\newpage
\end{corrige}

%%%

\begin{exo}{Calcul du PGCD}{Lycée Henri Alain-Fournier, Bourges}{2}{15} 
On considère l'algorithme suivant:

\Par

\begin{minipage}{0.35\linewidth}
\begin{algorithme}{}
a $>$ b deux entiers
r entier
Tant que b $>$ 0:
\quad r $\leftarrow$ a\%b
\quad a $\leftarrow$ b
\quad b $\leftarrow$ r
Fin du Tant que
\end{algorithme}
\end{minipage}
\hfill
\begin{minipage}{0.62\linewidth}
\begin{questions}
\item Justifier que la boucle n'est pas infinie.
\item Trouver un invariant de cette boucle.
\end{questions}

\Par

\textit{Aide : }on pourra introduire deux variables \texttt{x} et \texttt{y} prenant les valeurs de \texttt{a} et \texttt{b} avant l'entrée dans la boucle, avec la pré-condition $y\geqslant0$.
\vspace*{1.5em}
\end{minipage}

\Par

\textit{Note }: \og $a$\%$b$ \fg{} représente le reste de la division euclidienne de $a$ par $b$.

\begin{Remarque}
une propriété mathématique nous dit que si $a=bq+r$ alors $\PGCD(a,b)=\PGCD(b,r)$.
\end{Remarque}
\end{exo}

\begin{corrige}
\begin{questions}
\item \texttt{r} représente le reste de la division euclidienne de $a$ par $b$, donc\linebreak$0\leqslant r <b$ par définition mathématique. Or, \texttt{b}  devient \texttt{r} à chaque itération, donc \texttt{r} diminue à chaque itération. Comme \texttt{r} est un entier naturel, il existe une itération pour laquelle \texttt{r=0}, donc pour laquelle \texttt{b=0}, ce qui assure une sortie de la boucle.

\item Pré-condition : $y\geqslant0$. Considérons l'algorithme complété suivant:

\begin{algorithme}{}
a $>$ b deux entiers
x $\leftarrow$ a
y $\leftarrow$ b
r entier
Tant que b $>$ 0:
\quad r $\leftarrow$ a\%b
\quad a $\leftarrow$ b
\quad b $\leftarrow$ r
Fin du Tant que
\end{algorithme}

\Par

Posons alors:
\begin{center}
$P$ : \og $\text{pgcd}(a,b)=\text{pgcd}(x,y)$ et $b\geqslant0$. \fg{} 
\end{center}
\begin{itemize}
\item Avant l'entrée dans la boucle, $P$ est vraie.
\item Notons \texttt{a1}, \texttt{b1} et \texttt{r1} les valeurs de \texttt{a}, \texttt{b} et \texttt{r} à une certaine étape. 

Supposons que $P$ est vraie à cette étape; donc $\text{pgcd}(\texttt{a1},\texttt{b1})=\text{pgcd}(\texttt{x},\texttt{y})$ et $\texttt{b1}\geqslant0$.

Notons \texttt{a2}, \texttt{b2} et \texttt{r2} les valeurs de \texttt{a}, \texttt{b} et \texttt{r} lors de l'itération suivante.

Alors, \texttt{r2 = a1\%b1}, \texttt{a2=b1} et \texttt{b2=r2}.

D'après la propriété mathématique rappelée en énoncé, 
\begin{center}
pgcd(\texttt{a2},\texttt{b2}) = pgcd(\texttt{b1},\texttt{r2}) = pgcd(\texttt{a1},\texttt{a2}) = pgcd(\texttt{x},\texttt{y}).
\end{center}
De plus, \texttt{b2 $\geqslant$ 0} car \texttt{r2 $\geqslant$ 0}.

Ainsi, la propriété $P$ est vraie à cette étape; c'est donc un invariant de la boucle \og Tant que \fg.
\end{itemize}

La post-condition qui découle de ceci est que $\PGCD(\texttt{x},0)=\PGCD(\texttt{a},\texttt{b})$, et donc $x=\PGCD(a,b)$.
\end{questions}
\newpage
\end{corrige}

%%%

\begin{exo}{Palindrome}{Lycée Camille Jullian, Bordeaux}{2}{15} 
On considère l'algorithme suivant :

\begin{algorithme}{}
mot est une chaîne de caractères de longueur n
i $\leftarrow$ 0
j $\leftarrow$ n-1
p $\leftarrow$ Vrai
Tant que i $\leqslant$ j:
\quad Si mot[i] = mot[j]:
\qquad i $\leftarrow$ i+1
\qquad j $\leftarrow$ j-1
\quad Sinon:
\qquad p $\leftarrow$ Faux
\quad Fin du Si
Fin du Tant que
Afficher p
\end{algorithme}
\begin{questions}
\item Exécuter cet algorithme pour \texttt{mot = radar}. Quelle est la fonction de cet algorithme ?
\item Montrer que \texttt{d = j-i} est un variant de la boucle \og Tant que \fg.

En déduire que cette boucle se termine.

\item Quel est le coût de cet algorithme ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Utilisons un tableau de variables pour exécuter l'algorithme.
\begin{center}
\begin{tabular}{|C|*5{Zc|}}
\hline
i $\leqslant$ j et p = vrai & -- & vrai & vrai & vrai & faux\\\hline
mot[i] = mot[j] & -- & vrai & vrai & vrai & --\\\hline
i & 0 & 1 & 2 & 3 & --\\\hline
j & 4 & 3 & 2 & 1 & --\\\hline
p & vrai & vrai & vrai & vrai & --\\\hline
\end{tabular}
\end{center}

\Par

L'algorithme affiche la dernière valeur de \texttt{p}, c'est-à-dire ici \og vrai \fg.

Cet algorithme affiche donc si le mot est un palindrome (mot qui se lit de façon identique de gauche à droite et de droite à gauche) ou pas.

\item \texttt{d = j-i} représente la différence entre \texttt{i} et \texttt{j}. Or, à chaque itération, \texttt{i} est incrémentée (donc augmente) et \texttt{j} est décrémentée (donc diminue), ce qui implique que \texttt{d} diminue. Cette variable étant un entier (relatif), elle va valoir 0 lors d'une itération, puis $-1$, ce qui assure la sortie de la boucle \og Tant que \fg.

\item Le coût de cet algorithme est linéaire. En effet, le nombre d'itérations dépend directement de la longueur $n$ de la chaîne de caractères donc le nombre d'affectations et autres opérations logiques est proportionnel à~$n$.
\end{questions}
\end{corrige}

%%% 09
\newpage
\begin{exo}{Puissances de 2}{Lycée Turgot, Paris}{2}{15} 
Trouver un invariant de boucle dans l'algorithme suivant, puis en déduire la valeur affichée à la fin de son exécution.

\begin{algorithme}{}
n est un entier
p $\leftarrow$ 1
Pour i allant de 1 à n:
\quad p $\leftarrow$ 2*p
Fin du Pour
\end{algorithme}
\end{exo}

\begin{corrige}
Posons :
\begin{center}
$P$ : \og $p=2^i$ \fg{} 
\end{center}
\begin{itemize}
\item avant d'entrer dans la boucle itérative, $p=1=2^0=2^n$, donc  la propriété $P$ est vraie.
\item Notons $p_1$ et $i_1$ les valeurs de \texttt{p} et \texttt{i} lors d'une itération. Notons $p_2$ et $i_2$ les valeurs de ces mêmes variables à l'itération suivante. Alors:
\[
i_2=i_1+1\qquad\text{et}\qquad p_2=2\times p_1=2\times2^{i_1}=2^{i_1+1}=2^{i_2}.
\]
La propriété $P$ est donc vraie, ce qui montre que $P$ est un invariant de la boucle itérative.

Quand la boucle est finie, $i=n$ et $P$ est vraie, donc $p=2^n$.

L'algorithme permet donc de calculer la puissance de 2 lorsque l'exposant est égal à un entier $n$.
\end{itemize}
\newpage
\end{corrige}

%% 10

\begin{exo}{Contrôle de puissance}{Lycée Jean Macé, Niort}{3}{20} 
\begin{questions}
\item \'Ecrire un algorithme utilisant une boucle \og Tant que \fg permettant de\linebreak déterminer si un entier $n$ strictement positif donné est une puissance entière de 2. 
\item Montrer que la boucle \og Tant que \fg se termine.
\item Montrer que l'algorithme produit le résultat attendu.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Un algorithme possible est le suivant:
\begin{algorithme}{}
x est un nombre entier entré par l'utilisateur
p $\leftarrow$ Vrai
Si x\%2 = 1:
\quad p $\leftarrow$ Faux
Sinon:
\quad Tant que x\%2 = 0:
\qquad x $\leftarrow$ E(x/2) (partie entière de x/2)
\qquad n $\leftarrow$ n+1
\quad Fin du Tant que
\quad Si x $\neq$ 1:
\qquad p $\leftarrow$ Faux
\quad Fin du Si
Fin du Si
Afficher p
\end{algorithme}

\Par

Explications :
\begin{itemize}
\item on commence avant tout par tester si $x$ est pair (dans ce cas, $x\%2=0$). Si tel n'est pas le cas, le booléen \texttt{p} vaut \textit{Faux};
\item si $x$ est pair, on le divise par 2 autant de fois que possible (boucle \og Tant que \fg), c'est-à-dire tant que le résultat est pair;
\item la boucle terminée, si $x$ vaut 1, c'est que l'on a divisé par 2 tout le temps, et donc que $x$ est une puissance de 2. Sinon, $x$ n'est pas une puissance de 2, et le booléen \texttt{p} vaut alors \textit{Faux}.
\end{itemize}

\begin{Remarque}
la variable $n$ n'est pas utile au premier abord, mais elle nous servira pour trouver un invariant de boucle à la question 3.
\end{Remarque}

\item Un variant de boucle possible est le reste $r$ de $x$ dans sa division euclidienne par 2 ($r=x\%2$). En effet, le reste vaut 0 ou 1 dans une telle division et prend nécessairement la valeur 1 :
\begin{itemize}
\item soit quand $x$ n'est pas une puissance de 2 (le résultat de la division sera alors à un moment égal à un nombre impair plus grand que 1),
\item soit quand $x$ est une puissance de 2 (en divisant par 2 tout le temps, on arrive à un moment à $2\div2=1$ et là, le reste est égal à 1).
\end{itemize}

La boucle n'est donc pas infinie.

\item Avant d'entrer dans la boucle \og Tant que \fg, posons $a=x$ et la pré-condition \og $a$ est une puissance de 2 \fg.  Posons alors :
\begin{center}
$P$ : \og $a=2^m$, $x = a \div 2^n$ et $n\leqslant m$ \fg.
\end{center}

\newpage

Montrons que c'est un invariant de la boucle \og Tant que \fg{} :
\begin{itemize}
\item avant d'entrer dans la boucle, $x = a = a \div 2^0 = a \div 2^n$. De plus, $n=0\leqslant m$ car $m$ est un entier naturel.

Donc $P$ est vraie;

\item posons $x_1$ et $n_1$ les valeurs de $x$ et $n$ lors d'une itération où $P$ est vraie. Ainsi, $x_1=\dfrac{a}{2^{n_1}}$ et $n_1 < m$ (différent de $m$ car il faut qu'il y ait une autre itération).

Posons ensuite $x_2$ et $n_2$ les valeurs de ces mêmes variables à l'itération suivante. Alors, $n_2=n_1+1$ et:
\[
x_2 = \dfrac{x_1}{2} = \dfrac{1}{2}x_1=\dfrac{1}{2}\times\dfrac{a}{2^{n_1}}=\dfrac{a}{2^{n_1+1}}=\dfrac{a}{2^{n_2}}. \]
De plus,
\[
n_2=n_1+1<m+1\leqslant m.
\]
$P$ est donc vraie à cette étape.
\end{itemize}
Donc $P$ est un invariant de la boucle \og Tant que \fg. 

La boucle étant finie, \texttt{n} contient le nombre de fois que l'on a divisé \texttt{x} par 2 et \texttt{x} vaut 1, donc :
\[
1 = \dfrac{a}{2^n},\qquad\text{soit}\qquad a = 2^n.
\]
\end{questions}
\end{corrige}

%%%

\begin{exo}{Trouver l'invariant}{Lycée Sainte-Anne, Brest}{3}{20} 
Montrer que \og $z\times x^k = b^n$ et $k\geqslant0$ \fg est un invariant de la boucle de l'algorithme suivant, puis expliquer ce que fait cet algorithme.

\begin{algorithme}{}
n $>$ 0 est un entier
b est un réel
x $\leftarrow$ b
k $\leftarrow$ n
z $\leftarrow$ 1
Tant que k $\neq$ 0:
\quad Si k\%2 = 1:
\qquad z $\leftarrow$ z*x
\quad Fin du Si
\quad x $\leftarrow$ x*x
\quad k $\leftarrow$ E(k/2)
Fin du tant que
\end{algorithme}
\end{exo}

\begin{corrige}
Posons :
\begin{center}
$P$ : \og $z\times x^k = b^n$ et $k\geqslant0$ \fg.
\end{center}
\begin{itemize}
\item Avant d'entrer dans la boucle, $z\times x^k=1\times b^n=b^n$ et $k=n$ donc $k\geqslant n$.

$P$ est donc vraie.

\item Posons $z_1$, $x_1$ et $k_1$ les valeurs respectives de \texttt{z}, \texttt{x} et \texttt{k} lors d'une itération où $P$ est vraie. Alors,
\[
z_1\times x_1^{k_1}=b^n\qquad\text{et}\qquad k_1>0.
\]
($k_1\neq0$ car il faut qu'il y ait une autre itération)

À l'étape suivante, notons $z_2$, $x_2$ et $k_2$ les valeurs des mêmes variables. Alors,
\begin{itemize}
\item[--] si $k_1$ est impair ($k_1=2p_1+1$):
\[
z_2=z_1\times x_1
\]
et 
\[
x_2=x_1 \times x_1\qquad\text{et}\qquad k_2=E(k_1/2)=p_1.
\]
Dans ce cas, 
\[
z_2 \times x_2^{k_2} = \underbrace{z_1 \times x_1}_{=z_2} \times \big(x_1^2\big)^{p_1}=z_1 \times x_1 \times x_1^{2p_1}=z_1 \times x_1\times x_1^{k_1-1}=\underbrace{z_1\times x_1^{k_1}}_{=b^n}.
\]
\item[--] Si $k_1$ est pair ($k_1=2p_1$):
\[
x_2=x_1 \times x_1\qquad\text{et}\qquad k_2=E(k_1/2)=p_1.
\]
Dans ce cas,
\[
z_2 \times x_2^{k_2} = z_1 \times \big(x_1^2\big)^{p_1} = z_1 \times x_1^{2p_1} = z_1 \times x_1^{k_1}=b^n.
\]
\end{itemize} 
Dans les deux cas, $P$ est vraie.
\end{itemize}
Donc $P$ est bien un invariant de la boucle.

\Par

Quand la boucle se termine, $k=0$ et $P$ est vraie, donc $z\times x^0=b^n$, soit $z=b^n$.

L'algorithme calcule donc $b$ à l'exposant $n$.
\end{corrige}

\newpage 

\sectionnn{Conception d'algorithmes}

% NEW 2025

\begin{exo}{Fonction d'échange}{Lycée Richelieu, Versailles}{1}{10}
Étant donné un tableau \texttt{tab} et deux variables \texttt{m} et \texttt{n} contenant les indices de deux cases du tableau à permuter, écrire un algorithme d’une fonction \texttt{echange(tab, m, n)} qui échange les valeurs situées aux indices \texttt{m} et \texttt{n}, puis implémentez cet algorithme en Python.

\begin{Remarque}
cette fonction ne retourne rien car le tableau est modifié \textit{en place}, donc pas besoin de \texttt{return}.
\end{Remarque}
\end{exo}

\begin{corrige}
Un algorithme possible est le suivant:
\Par
\begin{algorithme}{}
tab : liste de valeurs
m, n : deux entiers

Si m $<$ len(tab) et n $<$ len(tab):
	temp $\leftarrow$ m
	m $\leftarrow$ n
	n $\leftarrow$ temp
Fin du Si
\end{algorithme}

\Par


Un implémentation possible en Python est alors la suivante:

\begin{listing}{}{07-echangeV1.py}\end{listing}

\Par

Il est à noter que Python permet la solution suivante:

\begin{listing}{}{07-echangeV2.py}\end{listing}
\newpage
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A COMPLETER


%%%

\sectionnn{Algorithmes gloutons}

\begin{exo}{Le problème du sac à dos}{Lycée Camille Jullian, Bordeaux}{2}{20} 
On dispose de $n$ objets $x_1$, ... , $x_n$, ayant chacun une valeur $v_i$ et une masse $m_i$, pour $1 \leqslant i \leqslant n$.

On possède un sac à dos ne pouvant supporter qu'une masse maximum $M$. On cherche à le remplir avec le plus d'objets possibles afin que la valeur totale de ces objets soit maximale.

\subsectionnn{Approche mathématique}

On note $\mu$ la masse totale des objets mis dans le sac qui satisfont nos conditions, et $V$ leur valeur totale.

\Par

Justifier les écritures : 
\[
\mu=\sum_{i=1}^{n}\delta_i m_i\qquad;\qquad V=\sum_{i=1}^n \delta_iv_i\;,
\]
où  $\delta_i\in\{0~;1\}$.

\subsectionnn{L'algorithme}

\begin{questions}
\item Quelles sont les conditions sur $V$ et $\mu$ ?
\item On souhaite trier les objets par ordre de priorité décroissante. 

Que cela signifie-t-il ?

\item Proposer alors un algorithme glouton répondant à notre problème, c'est-à-dire indiquant les objets à mettre dans le sac.
\end{questions}
\end{exo}

\begin{corrige}
\subsectionnn{Approche mathématique}
On passe en revue tous les objets $x_i$; si on met $x_i$ dans le sac alors la masse du contenu du sac augmente de $m_i$, sinon elle augmente de 0. On peut donc poser :
\[
\begin{cases}
\delta_i = 1 & \text{si $x_i$ est mis dans le sac},\\
\delta_i = 0 & \text{si $x_i$ n'est pas mis dans le sac}.
\end{cases}
\]
Ainsi, la masse totale des objets mis dans le sac est:
\[
\mu = \sum_{i=1}^{n}\delta_i m_i.
\]
Sur le même principe, la valeur totale $V$des objets mis dans le sac est:
\[
V = \sum_{i=1}^n \delta_iv_i.
\]

\subsectionnn{L'algorithme}

\begin{questions}
\item Le masse totale des objets doit être inférieure ou égale à $M$, d'où la première condition : $\mu \leqslant M$.

Il faut ensuite obtenir une valeur totale optimale, d'où la condition : $V$ optimale.

\item Un \og tri optimisé \fg est, dans notre problème, des objets   
triés selon leur valeur (de la plus grande jusqu'à la plus petite), puis leur masse (de la plus petite jusqu'à la plus grande).

Trier les objets d'abord selon leur masse croissante n'est pas nécessairement un bon choix car les objets légers peuvent ne pas valoir cher.

\item L'algorithme doit parcourir tous les objets triés selon les critères mentionnés précédemment, ajoutés dans le sac tant que la masse totale ne dépasse pas $M$. On peut alors considérer l'algorithme page suivante.

\Par\enlargethispage*{3em}

\textit{Explications :}

\begin{itemize}
\item on parcourt toutes les valeurs de \texttt{m} et \texttt{v} (ligne 1);
\item Si la somme de la masse totale précédente et de la masse de l'objet sur lequel nous sommes est inférieure ou égale à la masse totale possible $M$ (ligne 2) alors on indique que l'on prend l'objet ($\delta_i=1$, ligne 3) en mettant \og 1 \fg{} dans le tableau des coefficients; sinon (ligne 6), on indique que l'on ne prend pas l'objet ($\delta_i=0$, ligne 7);
\item à la sortie de la boucle itérative, on a un tableau de la forme \linebreak\texttt{d = [1,1,0,1,0,1]} indiquant quels sont les objets à  mettre dans le sac à dos (objets correspondant aux nombres 1), ainsi que la masse totale (stockée dans la variable \texttt{MT}) et la valeur totale (\texttt{VT}).
\end{itemize}

\newpage

\begin{algorithme}{}
MT $\leftarrow$ 0 (masse totale du contenu du sac)
VT $\leftarrow$ 0 (valeur totale du contenu du sac)
m = tableau des masses des objets
v = tableau des valeurs des objets
d = tableau des coefficients 
Pour i allant de 1 à n:\hfill(1)
\quad Si MT+m[i]$\leqslant$ M:\hfill(2)
\qquad d[i] $\leftarrow$ 1\hfill(3)
\qquad MT $\leftarrow$ MT + m[i]\hfill(4)
\qquad VT $\leftarrow$ VT + v[i]\hfill(5)
\quad Sinon:\hfill(6)
\qquad d[i] $\leftarrow$ 0\hfill(7)
\quad Fin du Si
Fin du Pour
\end{algorithme}
\end{questions}
\end{corrige}

%%% 13

\begin{exo}{Loueur de camions}{Lycée Henri Bergson, Angers}{3}{30} 
\NathanLiveVideo[\PictoVideo\ Retrouvez le corrigé de cet exercice en vidéo.]{loueur de camions}{https://media.prepamath.fr/IL1NSIch07ExLoueur}

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


Un loueur de camions reçoit des demandes de location d'un camion sous la forme $[d_i~;~f_i]$, où $d_i$ est la date du début de la location et $f_i$, la date de la fin de la location, $d_i$ et $f_i$ étant deux nombres de $\llbracket1~;365\rrbracket$.

Imaginer un algorithme glouton permettant de sélectionner au mieux les clients.
\end{exo}

\begin{corrige}
%\rput(-0.5,0.1){\nathanliveVidWithoutText}
La première chose à faire est de se demander sur quel(s) critère(s) nous allons réfléchir pour optimiser les locations. Pour que deux demandes de location soient possibles, il faut que les périodes ne se chevauchent pas (par exemple, $[2~;8]$ et $[7~;9]$ sont impossibles à satisfaire).

On va donc trier les périodes selon leur date de fin.

Prenons l'exemple de la demande suivante :
\begin{center}
\begin{tabular}{|L|*9{Zc|}}
\hline
Clients $i$ & 1&2&3&4&5&6&7&8&9\\
\hline
Débuts de périodes $d_i$ & 1 &2& 4& 1& 5& 8& 9& 13& 11\\
\hline
Fins de périodes $f_i$ & 8 &5 &7 &3 &9 &11& 10& 16& 14\\
\hline
\end{tabular}
\end{center}

Après avoir trié selon les dates de fins croissantes, on obtient :

\begin{center}
\begin{tabular}{|L|*9{Zc|}}
\hline
Clients $i$ & 4 &2& 3& 1& 5& 7& 6 &9& 8\\
\hline
Débuts de périodes $d_i$ & 1 &2 &4 &1 &5 &9 &8 &11& 13\\
\hline
Fins de périodes $f_i$ & 3& 5& 7 &8 &9 &10& 11 &14 &16\\
\hline
\end{tabular}
\end{center}

\Par

Ensuite, on satisfait les demandes possibles de la gauche vers la droite :

\begin{itemize}
\item la demande du client 4 est satisfaite;
\item celle du client 2 ne l'est pas car la date du début est inférieure à celle de la fin de la demande précédente;
\item celle du client 3 est satisfaite car la date du début est supérieure à celle de la demande précédente;
\item etc.
\end{itemize}
Les clients 4, 3, 7 et 9 voient alors leur demande satisfaite.

Un algorithme glouton est alors le suivant, après tri (donc sur le 2\ieme{} tableau dans l'exemple que nous avons pris):

\begin{algorithme}{}
c $\leftarrow$ liste des numéros de clients (4, 2, ..., 8 
\hspace*{6.5cm}pour notre exemple)
s $\leftarrow$ liste des numéros de clients à satisfaire
s[0] $\leftarrow$ c[0] (1\ier client satisfait)
fin $\leftarrow$ f[0]
Pour i allant de 1 à n-1:
\quad Si d[i] $\geqslant$ fin:
\qquad s[k+1] $\leftarrow$ c[i]
\qquad fin $\leftarrow$ f[i]
\quad Fin du Si
Fin du Pour
\end{algorithme}

\Par

Pour chaque client, on regarde si la date de début de période est supérieure ou égale à la date de fin de la période du dernier client satisfait. Si tel est le cas, ce client est ajouté à la liste des clients satisfaits et la variable \texttt{fin} prend la valeur de la date de fin de la période du client ajouté, pour servir de référence pour les clients suivants.
\end{corrige}

% NEW 2025

\begin{exo}{Deuxième valeur minimale\newexo}{Lycée Jean Macé, Niort}{3}{30}
On considère un tableau $T$ de $n$ nombres entiers $(n \geqslant 2)$. On souhaite écrire un algorithme permettant de trouver la \textbf{deuxième plus petite valeur} de ce tableau.

\begin{questions}
    \item Écrire un algorithme en pseudo-code qui détermine la deuxième plus petite valeur de $T$.
    \item Déterminer le coût de cet algorithme en fonction de $n$ dans le pire des cas.
    \item Modifier l'algorithme pour qu'il affiche également l'indice de la deuxième plus petite valeur.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Voici un exemple d'algorithme en pseudo-code qui détermine la deuxième plus petite valeur de $T$.

\begin{algorithme}{}
Entrée: un tableau $T$ de $n$ entiers $(n \geqslant 2)$ 
Sortie: la deuxième plus petite valeur du tableau $T$
min1 $\leftarrow+\infty$
min2 $\leftarrow+\infty$
Pour i allant de 0 à n-1 :
     Si T[i] $<$ min1 alors
         min2 $\leftarrow$ min1
         min1 $\leftarrow$ T[i]
     Sinon si T[i] $<$ min2 alors
         min2 $\leftarrow$ T[i]
Fin du Pour
Afficher "La deuxième plus petite valeur est", min2
\end{algorithme}

\item L'algorithme effectue une unique boucle sur les $n$ éléments du tableau. À chaque itération, un nombre constant de comparaisons et affectations est réalisé. Le coût total de l'algorithme est donc \textit{linéaire}, soit de l'ordre de $O(n)$.

\item Voici un algorithme qui affiche également l'indice de la deuxième plus petite valeur.

\begin{algorithme}{}
Entrée: un tableau $T$ de $n$ entiers $(n \geqslant 2)$
Sortie: la deuxième plus petite valeur du tableau $T$
	et son indice

min1 $\leftarrow+\infty$, ind1 $\leftarrow$ -1
min2 $\leftarrow+\infty$, ind2 $\leftarrow$ -1
Pour i allant de 0 à n-1 :
     Si T[i] $<$ min1 alors
         min2 $\leftarrow$ min1
         ind2 $\leftarrow$ ind1
         min1 $\leftarrow$ T[i]
         ind1 $\leftarrow$ i
     Sinon si T[i] $<$ min2 alors
        min2 $\leftarrow$ T[i]
        ind2 $\leftarrow$ i
Fin du Pour
Afficher "La deuxième plus petite valeur est", min2,
"à l'indice", ind2
\end{algorithme}

\Par

Cet algorithme conserve le même coût linéaire $O(n)$.
\end{questions}
\end{corrige}
\thumb
\AfficheCorrige
