Mathématiques et algorithmique

1. Ce bloc de code a pour effet d'afficher 15.
2. Il calcule la somme des \(n\) premiers entiers naturels non nuls.

3. Il y a 3 assignations avant d'entrer dans la boucle. À chaque tour de boucle, il y a 1 comparaison, 2 additions et 2 assignations. Pour compter tout ça, on peut donc s'y prendre comme suit.

   # entrée :
   n = 5
   # instructions :
   k = 1
   somme = 1
   compteur = 3
   while k < n:
       k = k + 1
       somme = somme + k
       compteur = compteur + 5
   # sortie :
   print(somme)
   print(compteur)
   

4. On a \(T(5)=3+4\cdot 5=23\text{.}\)
5. On a \(T(n)=3+5(n-1)=5n-2\text{.}\)
6. Il s'agit d'une complexité linéaire.

1. Cela renvoie \(2\text{,}\) comme on peut le vérifier avec Python Tutor.
2. Cela renvoie \(1\text{,}\) comme on peut le vérifier avec Python Tutor.
3. Cela renvoie \(5\text{,}\) comme on peut le vérifier avec Python Tutor.

4. Cette fonction renvoie la position de la première apparition de x dans liste.

   Si x n'y figure pas, elle renvoie la longueur de la liste.

5. Avant la boucle, il y a 2 assignations. À chaque tour de boucle, il y a 2 comparaisons, 1 addition et 1 assignation. Dans le pire des cas, on a donc \(T(n)=2+n\cdot 4=4n+2\text{.}\)

1. Voici les étapes de l'algorithme :

   \begin{align*} 3^{45}&=3\cdot\left(3^2\right)^{22},\\ &=3\cdot\left(3^4\right)^{11},\\ &=3\cdot 3^4\cdot\left(3^8\right)^5,\\ &=3\cdot 3^4\cdot 3^8\cdot\left(3^{16}\right)^2,\\ &=3\cdot 3^4\cdot 3^8\cdot 3^{32}. \end{align*}

2. Cela prend 5 multiplications pour calculer

   \begin{align*} &3^2=3\cdot 3=9,\\ &3^4=3^2\cdot 3^2=81,\\ &3^8=3^4\cdot 3^4=6\,561,\\ &3^{16}=3^8\cdot 3^8=43\,046\,721,\\ &3^{32}=3^{16}\cdot 3^{16}=1\,853\,020\,188\,851\,841, \end{align*}

   et 3 de plus pour calculer

   \begin{align*} 3^{45}&=3\cdot 3^4\cdot 3^8\cdot 3^{32},\\ &=3\cdot 81\cdot 6\,561\cdot 1\,853\,020\,188\,851\,841,\\ &=2\,954\,312\,706\,550\,833\,698\,643. \end{align*}

   Cela fait donc un total de 8 multiplications.

3. On a

   \begin{align*} 45&=32+13,\\ &=32+8+5,\\ &=32+8+4+1,\\ &=1\cdot 2^5+1\cdot 2^3+1\cdot 2^2+1\cdot 2^0,\\ &=1\cdot 2^5+0\cdot 2^4+1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0. \end{align*}

   L'écriture en binaire de \(45\) est donc \(101101\) et les puissances de \(2\) qui apparaissent, à savoir \(1,4,8\) et \(32\text{,}\) sont les exposants utiles de la décomposition

   \begin{equation*} 3^{45}=3\cdot 3^4\cdot 3^8\cdot 3^{32}. \end{equation*}

4. Notons

   \begin{equation*} M:=\begin{bmatrix}1&1\\1&0\end{bmatrix}. \end{equation*}

   Comme \(M^{45}=M\cdot M^4\cdot M^8\cdot M^{32}\text{,}\) on doit d'abord calculer les puissances de \(M\) suivantes :

   \begin{equation*} M^2=\begin{bmatrix}2&1\\1&1\end{bmatrix}, \end{equation*}
   \begin{equation*} M^4=\begin{bmatrix}5&3\\3&2\end{bmatrix}, \end{equation*}
   \begin{equation*} M^8=\begin{bmatrix}34&21\\21&13\end{bmatrix}, \end{equation*}
   \begin{equation*} M^{16}=\begin{bmatrix}1\,597&987\\987&610\end{bmatrix}, \end{equation*}
   \begin{equation*} M^{32}=\begin{bmatrix}3\,524\,578&2\,178\,309\\2\,178\,309&1\,346\,269\end{bmatrix}. \end{equation*}

   Maintenant \(M^{45}=M\cdot M^4\cdot M^8\cdot M^{32}\) donne

   \begin{equation*} M^{45}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}5&3\\3&2\end{bmatrix}\begin{bmatrix}34&21\\21&13\end{bmatrix}\begin{bmatrix}3\,524\,578&2\,178\,309\\2\,178\,309&1\,346\,269\end{bmatrix}, \end{equation*}

   d'où

   \begin{equation*} M^{45}=\begin{bmatrix}8&5\\5&3\end{bmatrix}\begin{bmatrix}34&21\\21&13\end{bmatrix}\begin{bmatrix}3\,524\,578&2\,178\,309\\2\,178\,309&1\,346\,269\end{bmatrix}, \end{equation*}

   puis

   \begin{equation*} M^{45}=\begin{bmatrix}377&233\\233&144\end{bmatrix}\begin{bmatrix}3\,524\,578&2\,178\,309\\2\,178\,309&1\,346\,269\end{bmatrix}, \end{equation*}

   et finalement

   \begin{equation*} M^{45}=\begin{bmatrix}1\,836\,311\,903&1\,134\,903\,170\\1\,134\,903\,170&701\,408\,733\end{bmatrix}. \end{equation*}

1. Si on ne tient compte que du nombre de multiplications impliquées, on obtient la fonction qui suit.

   def complexitePuissanceRecursive(n):
       if n == 1:
           return 0
       elif n % 2 == 0:
           return 1 + complexitePuissanceRecursive(n / 2)
       else:
           return 2 + complexitePuissanceRecursive((n - 1) / 2)
   

2. Après évaluation du bloc précédent, la commande print(complexitePuissanceRecursive(45)) affiche bien 8.
3. Grâce au code précédent, on trouve \(T(10\,000)=17\text{.}\)
4. C'est bien vrai car \(\log_2(10\,000)-1\approx 12{,}3\) et \(2\log_2(10\,000)\approx 26{,}6\text{.}\)

La décomposition binaire de \(47\) donne 5 morceaux non nuls :

Celle de \(48\) n'en donne que 2 :

Dans les deux cas, il y a 5 produits matriciels à effectuer pour déterminer \(M^2,M^4,M^8,M^{16}\) et \(M^{32}\text{,}\) puis 4 autres por calculer

et seulement 1 autre pour calculer

C'est donc le calcul de \(M^{47}\) qui nécessite le plus de produits matriciels lorsqu'on applique l'algorithme d'exponentiation rapide.

1. Le plus petit nombre de chiffres non nuls possible est \(1\text{,}\) lorsque \(n=2^d\) est une puissance de \(2\text{.}\)
2. Le plus grand nombre de chiffres non nuls possible est \(d+1\text{,}\) lorsque \(n=2^d+2^{d-1}+\cdots+2+1\) précède une puissance de \(2\text{.}\)

3. Ce minimum est atteint dans le cas où \(n=2^d\) est une puissance de \(2\text{.}\) Il faut alors \(d\) multiplications puisqu'il faut calculer \(x^2,\ldots,x^{2^d}\text{.}\)

4. Ce maximum est atteint dans le cas où \(n=2^d+2^{d-1}+\cdots+2+1\) précède une puissance de \(2\text{.}\) Il faut alors \(d\) multiplications pour calculer d'abord \(x^2,\ldots,x^{2^d}\text{,}\) et \(d\) multiplications pour calculer ensuite

   \begin{equation*} x^n=x\cdot x^2\cdots x^{2^{d-1}}\cdot x^{2^d}. \end{equation*}

   Cela prend donc \(2d\) multiplications en tout.

5. On déduit des deux questions précédentes l'encadrement

   \begin{equation*} d\le T(n)\le 2d. \end{equation*}

   Par ailleurs, on a

   \begin{equation*} 2^d\le n< 2^{d+1} \end{equation*}

   d'où

   \begin{equation*} d\le\log_2(n)< d+1 \end{equation*}

   par croissance de la fonction \(\log_2(x)\text{,}\) et il en découle que \(d\) est égal à la partie entière de \(\log_2(n)\)

   \begin{equation*} d=\lfloor\log_2(n)\rfloor, \end{equation*}

   ce qui achève la démonstration.

Exécutez l'algorithme de Horner à la main pour calculer \(P(3)\text{.}\)

1. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&4\\ \text{Étape 1 :}&valeur&=&7+3\cdot 4=19\\ \text{Étape 2 :}&valeur&=&2+3\cdot 19=59 \end{array} \end{equation*}

   Donc \(P(3)=59\text{.}\)

2. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&4\\ \text{Étape 1 :}&valeur&=&-7+3\cdot 4=5\\ \text{Étape 2 :}&valeur&=&-2+3\cdot 5=13 \end{array} \end{equation*}

   Donc \(P(3)=13\text{.}\)

3. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&-5\\ \text{Étape 1 :}&valeur&=&0+3\cdot(-5)=-15\\ \text{Étape 2 :}&valeur&=&2+3\cdot(-15)=-43\\ \text{Étape 3 :}&valeur&=&-1+3\cdot(-43)=-130 \end{array} \end{equation*}

   Donc \(P(3)=-130\text{.}\)

1. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&4\\ \text{Étape 1 :}&valeur&=&7+(-2)\cdot 4=-1\\ \text{Étape 2 :}&valeur&=&2+(-2)\cdot (-1)=4 \end{array} \end{equation*}

   Donc \(P(-2)=4\text{.}\)

2. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&4\\ \text{Étape 1 :}&valeur&=&-7+(-2)\cdot 4=-15\\ \text{Étape 2 :}&valeur&=&-2+(-2)\cdot (-15)=28 \end{array} \end{equation*}

   Donc \(P(-2)=28\text{.}\)

3. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&-5\\ \text{Étape 1 :}&valeur&=&0+(-2)\cdot(-5)=10\\ \text{Étape 2 :}&valeur&=&2+(-2)\cdot 10=-18\\ \text{Étape 3 :}&valeur&=&-1+(-2)\cdot(-18)=35 \end{array} \end{equation*}

   Donc \(P(-2)=35\text{.}\)

1. \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&7\\ \text{Étape 1 :}&valeur&=&2+2\cdot 7=16\\ \text{Étape 2 :}&valeur&=&4+2\cdot 16=36\\ \text{Étape 3 :}&valeur&=&5+2\cdot 36=77\\ \text{Étape 4 :}&valeur&=&9+2\cdot 77=163 \end{array} \end{equation*}

   Donc \(P(2)=163\text{.}\)

2. Le quotient est

   \begin{equation*} Q(x)=7x^3+16x^2+36x+77 \end{equation*}

   et le reste vaut

   \begin{equation*} R(x)=163. \end{equation*}

3. Les coefficients du quotient correspondent aux quatre premières valeurs calculées par l'algorithme de Horner.

   Le reste est égal à la cinquième valeur, c'est-à-dire \(P(2)\text{.}\)

1. L'algorithme de Horner pour évaluer \(P(3)\) donne

   \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&1\\ \text{Étape 1 :}&valeur&=&7+3\cdot 1=10\\ \text{Étape 2 :}&valeur&=&-2+3\cdot 10=28 \end{array} \end{equation*}

   Donc le quotient est \(Q(x)=1\cdot x+10=x+10\) et le reste vaut \(R(x)=28\text{.}\)

2. L'algorithme de Horner pour évaluer \(P(2)\) donne

   \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&1\\ \text{Étape 1 :}&valeur&=&-5+2\cdot 1=-3\\ \text{Étape 2 :}&valeur&=&6+2\cdot(-3)=0\\ \text{Étape 3 :}&valeur&=&0+2\cdot 0=0 \end{array} \end{equation*}

   Donc le quotient est \(Q(x)=1\cdot x^2+(-3)\cdot x+0=x^2-3x\) et le reste vaut \(R(x)=0\text{.}\)

3. L'algorithme de Horner pour évaluer \(P(-4)\) donne

   \begin{equation*} \begin{array}{lcl} \text{Étape 0 :}&valeur&=&2\\ \text{Étape 1 :}&valeur&=&1+(-4)\cdot 2=-7\\ \text{Étape 2 :}&valeur&=&0+(-4)\cdot(-7)=28\\ \text{Étape 3 :}&valeur&=&7+(-4)\cdot 28=-105 \end{array} \end{equation*}

   Donc le quotient est \(Q(x)=2\cdot x^2+(-7)\cdot x+28=2x^2-7x+28\) et le reste vaut \(R(x)=-105\text{.}\)

En prenant l'entier le plus proche du nombre calculé, on trouve :

1. \(F_{14}=377\text{;}\)
2. \(F_{15}=610\text{;}\)
3. \(F_{16}=987\text{;}\)
4. \(F_{40}=102\,334\,155\text{;}\)
5. \(F_{100}=3{,}542\,248\,481\,792\,631\times 10^{20}\text{.}\)

Les quatre premiers calculs sont conformes aux valeurs fournies par OEIS.

Suite aux erreurs d'arrondis dues à la présence de \(\sqrt{5}\text{,}\) le cinquième calcul ne fournit que les 14 premiers chiffres exacts de

qu'on avait calculé à l'exercice 1.4.12.

En prenant le premier coefficient de la matrice

1. \(M^{13}\text{,}\) on trouve \(F_{14}=377\text{;}\)
2. \(M^{14}\text{,}\) on trouve \(F_{15}=610\text{;}\)
3. \(M^{15}\text{,}\) on trouve \(F_{16}=987\text{;}\)
4. \(M^{39}\text{,}\) on trouve \(F_{40}=102\,334\,155\text{;}\)
5. \(M^{99}\text{,}\) on trouve \(F_{100}=3\,736\,710\,778\,780\,434\,371\text{.}\)

Les quatre premiers calculs sont conformes aux valeurs fournies par OEIS.

Suite aux erreurs de manipulations de matrices dont les coeffficients deviennent trop grands, le cinquième calcul est totalement faux et très loin de

qu'on avait calculé à l'exercice 1.4.12. Cela prend donc autre chose que cette utilisation de NumPy pour implémenter l'exponentiation matricielle rapide de façon à réellement battre l'approche itérative de ce dernier.

Pour aller plus loin sans erreur, on peut utiliser Sage, par exemple.