Dans cette section, on s’intéresse au codage binaire d’un entier. Pour cela on propose l’algorithme $\mathcal{A}$ ci-dessous. Cet algorithme utilise le type vecteurBooleen. On suppose que si v est un vecteurBooleen, alors l(v) retourne sa longueur (nombre de coordonnées) et v[i] permet d’accéder (de modifier, ou même de créer) sa i-ème coordonnée, avec $0 \leq i \leq l(v)$. La méthode vecteurVide() crée un vecteur booléen vide.

Algorithme $\mathcal{A}$

Entree :
	k un entier
Sortie :
	un vecteurBooleen
variables :
	n,i deux entiers entiers
	v un vecteurBooleen
debut A
	n ← k; i ← 0; v ← vecteurVide()
	TANT QUE ( n >= 1) FAIRE
		SI (n MOD 2 = 0) ALORS
			v[i] ← 0
		SINON v[i] ← 1
		FIN SI
		n ← n DIV 2; i++
	FIN TANT QUE
	RETOURNER v
fin A

1. Montrer que l'algorithme $\mathcal{A}$ se termine. Pour cela vous utiliserez un variant, lequel ?
2. L'objectif de l'algorithme $\mathcal{A}$ c'est de retourner un vecteur booléen contenant les chiffres de l'entrée $k$ écrite en binaire. Par définition, si v est ce vecteur, on doit avoir : $$k=\underset{i=0}{\overset{l(v)-1}{\sum}}v[i]2^i$$On va montrer que le vecteur v résultat de l'algorithme $\mathcal{A}$ vérifie bien cette égalité. Pour cela, on va montrer par récurrence sur $i$ l'existence d'un invariant. On note $n_i$ la valeur de $n$ au début de la $i$-ième itération. Soit alors $$I(i)=2^i\times n_i+\underset{j=0}{\overset{i-1}{\sum}}v[j]\times2^j$$ Montrer que $I$ est un invariant, c'est à dire qu'il est constant pour tout $i$ lors de l'algorithme. Votre preuve se fera par récurrence sur $i$.
3. Supposons que $k$ est une puissance de $2$ avec $k=2^p$ où $p$ est un entier positif. En déduire que le nombre d'itérations de $\mathcal{A}$ est exactement égal à $p+1$.
4. On admettra que si $2^{p-1} \leq k < 2^p$ alors le nombre d'itérations de l'algorithme est égal à $p$. En déduire la complexité de l'algorithme.

Soit l'algorithme suivant (le type VecteurBooleen est défini dans la première partie).

Algorithme $\mathcal{B}$.

Entrees :
	x un entier
	v un vecteurBooleen
Sortie :
	un réel
debut B
	R ← 1; u ← x
	pour (i ← 0 à l(v)-1) faire
		si v[i]=1 alors 
			R ← R*u
		fin si
		u ← u*u
	fin pour
	retourner R
fin B

1. Appliquer l'algorithme aux entrées suivantes en donnant bien l'évolution des variables R et u.
2. $(3, [1, 1])$
3. $(\frac{1}{2}, [0, 0, 1])$
4. $(2, [1,0,1])$
5. À votre avis, que fait cet algorithme ?
6. Montrer simplement que l'algorithme se termine.
7. On suppose que l'algorithme $\mathcal{B}$ est correct. Donner la complexité de l'algorithme en fonction de l(v), en utilisant la notation de Landau $\Theta$. On supposera que l'opération de multiplication par $2$ est une opération élémentaire.

Soit l'algorithme ci-dessous.

Algorithme $\mathcal{C}$.

Entrees :
	x un réel
	k un entier
Sortie :
	reel
Variable :
	vecteurBooleen v
debut C
	v ← A(k)
	retourner B(x ,v)
fin

Expliquer sans prouver la correction, pour l'algorithme $\mathcal{C}$ calcul bien $x^k$. Déduire des deux sections précédentes la complexité de l'algorithme en fonction de $k$.