[TP06] Exponentiation rapide

Soient deux nombres x∈Z et n∈N.

Une façon naïve de calculer xn serait de multiplier n fois x par lui-même.

Mais on peut faire bien plus efficace que cela !
Il suffit d'utiliser les équations de récurrence suivantes :

$\begin{align*} p(x,0) &= 1\\ p(x,n) &= p(x \cdot x,\frac{n}{2}) & \mbox{si $n$ est pair}\\ &= x \cdot p(x \cdot x,\frac{n-1}{2}) & \mbox{si $n$ est impair}\\ \end{align*}$

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

le cas de base,

comment traiter le cas de base,

comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} has not a valid extension. {} is too heavy.

Question 1: Exponentiation rapide récursive

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier expo.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def puiss_rec(x, n):
    """
    Exponentiation rapide par récursion
    pre: `n` >= 0
    post: retourne `x`^`n`
    """

return -1

 
return -1

Question 2: Nombre d'appels récursifs

Combien y a-t-il d'appels récursifs si n = 64 ?

Question 3: Complexité temporelle

Intuitivement, quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.

Note : de façon générale, on exprime toujours une complexité (temporelle ou spatiale) en fonction de la taille du problème traité.

Pour la grande majorité des algorithmes étudiés dans ce cours, la taille du problème est simplement le nombre de valeurs à mémoriser
dans la collection (une liste, un tableau, un arbre, un graphe, ...) qui contient les données et sur laquelle l'algorithme réalise un calcul.

Ici, la taille du problème est la puissance n à calculer puisque, logiquement, il peut y avoir plus ou moins d'opérations à faire selon la puissance considérée.
Ce n'est donc pas un hasard si nous dénotons par n la puissance à calculer puisque c'est la notation la plus courante pour exprimer la taille du problème traité.

$\Theta(\log(n))$

$\Theta(n)$

$\Theta(n^2)$

$\Theta(1)$

$\Theta(\sqrt{n})$

$\Theta(n^3)$

Question 4: Complexité temporelle de la méthode naïve

Comme énoncé au début de l'exercice, une façon naïve de calculer $x^n$ serait de multiplier $n$ fois $x$ par lui-même. Quelle est la complexité temporelle d'un tel algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

$\Theta(\log(n))$

$\Theta(1)$

$\Theta(\sqrt{n})$

$\Theta(n)$

$\Theta(n^2)$

$\Theta(n^3)$

Question 5: Faites vos jeux

Les deux approches étudiées dans cet exercice ont leurs propres qualités et défauts. Sélectionnez, parmi les propositions suivantes, les qualités de chacune. Sur base de vos réponses, quelle approche devriez-vous utiliser pour la puissance d'un nombre ?

Parce qu'il ne faut pas prévoir de cas de base, la complexité temporelle serait meilleure si je choisissais l'approche naïve

Parce qu'elle est plus simple à implémenter, je choisirais l'approche naïve

Parce que la complexité temporelle est plus petite, je choisirais l'approche récursive

Parce que la complexité spatiale est plus petite, je choisirais l'approche naïve

Author(s)	Vincent Branders, Pierre Dupont
Deadline	26/03/2025 14:00:00
Submission limit	No limitation

Information

Sign in