[TP06] Exponentiation rapide

Soient deux nombres $x \in \mathbb{Z}$ et $n \in \mathbb{N}$. Une façon naïve de calculer $x^n$ 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écurrences 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

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.

$\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, je choisirais 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	27/03/2024 14:00:00
Submission limit	No limitation

Information

Sign in