30 - Exos Coûts
Pensez à garder une trace de votre travail, soit sous forme papier, soit en remplissant la copie numérique.
1 - Coûts qualifiés de "Facile"
✎ 01° Evaluer à l'aide de Python les expressions suivantes pour bien comprendre le principe de la fonction fournie.
>>> from math import log2
>>> log2(4)
2
>>> log2(8)
3
>>> log2(16)
4
>>> log2(32)
5
Question
- Comment se nomme-t-elle en français ?
- Expliquer pourquoi log2(32) vaut 5.
- Que se passe-t-il lorsque la valeur fournie est multipliée par 2 par rapport à un cas déjà calculé ?
...CORRECTION...
- Comment se nomme-t-elle en français ?
- Expliquer pourquoi log2(32) vaut 5.
- Que se passe-t-il lorsque la valeur fournie est multipliée par 2 par rapport à un cas déjà calculé ?
Il s'agit de la fonction logarithme base 2.
La fonction log2() renvoie l'exposant X du nombre lorsqu'on l'écrit sous forme 2X.
Puisque 32 = 25, on aura log2(32) = log2(25) = 5.
On obtient simplement un résultat plus grand de 1 :
log2(32) = log2(25) = 5
log2(64) = log2(26) = 6
✎ 02° On considère qu'un programme est à coût logarithmique (log2).
Avec 40 données, il faut 12 opérations basiques pour répondre au problème.
Combien d'opérations faut-il globalement pour répondre au problème si on passe à 80 données puis à 160 données ?
...CORRECTION...
Coût logarithmique base 2 : si on double les données, on rajoute une opération à coût constant. Donc :
40 données, 12 opérations.
80 données, 13 opérations.
160 données, 14 opérations.
✎ 03° On considère qu'un programme est à coût linéaire.
Avec 40 données, il faut 12 opérations basiques pour répondre au problème.
Combien d'opérations faut-il globalement pour répondre au problème si on passe à 80 données puis à 160 données ?
...CORRECTION...
Coût linéaire : si on double les données, on double globalement le nombre d'opérations.
40 données, 12 opérations.
80 données, 24 opérations (12*2).
160 données, 48 opérations (24*2).
✎ 04° On considère qu'un programme est à coût quadratique.
Avec 40 données, il faut 12 opérations basiques pour répondre au problème.
Combien d'opérations faut-il globalement pour répondre au problème si on passe à 80 données puis à 160 données ?
...CORRECTION...
Coût quadratique : si on double les données, on quadruple globalement le nombre d'opérations.
40 données, 12 opérations.
80 données, 48 opérations (12*4).
160 données, 192 opérations (48*4).
A connaître par coeur pour le DS
Dans le cadre des fonctions polynomiales, lorsque les données doublent, les actions sont multipliées par un facteur constant :
- Linéaire, données x2, actions x2
- Quadratique, données x2, actions x4
- Cubique, données x2, actions x8
- ...
2 - Coûts "Difficile"
✎ 05° Utiliser Python pour calculer l'exponentielle 2 de 4, de 8 et de 16. Expliquer pourquoi cette croissance n'est ni linéaire, ni même polynomiale.
>>> 2**4
?
>>> 2**8
?
>>> 2**16
?
...CORRECTION...
>>> 2**4
16
>>> 2**8
256
>>> 2**16
65536
Cette croissance n'est pas linéaire puisqu'en multipliant l'entrée par deux, on fait croitre la valeur par bien plus que 2 à chaque fois.
La croissance n'est pas polynomiale car on obtient pas un facteur constant à chaque fois qu'on multiplie par deux :
- De 4 à 8 données, le facteur est 256/16 = 16.
- De 8 à 16 données, le facteur est 65536/256 = 256.
✎ 06° Evaluer à l'aide de Python les expressions suivantes pour bien comprendre le principe de la fonction fournie.
>>> from math import factorial
>>> 4 * 3 * 2 * 1
24
>>> factorial(4)
24
>>> 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
40320
>>> factorial(8)
40320
>>> factorial(16)
20922789888000
Questions
- Comment se nomme-t-elle en français ?
- A quoi voit-on qu'il ne s'agit clairement pas d'une croissance linéaire, ni d'autre croissance polynomiale quelconque ?
- Est-ce pire ou mieux qu'exponentielle en terme d'algorithme ?
...CORRECTION...
Il s'agit de la fonction factorielle.
Il ne s'agit pas d'une fonction linéaire puisque qu'on ne multiplie pas les actions par deux en multipliant les données par deux.
D'ailleurs le facteur ne reste même pas constant en multipliant par deux : il augmente au fur et à mesure que les nombres de données augmente.
- De 4 à 8 données, le facteur est 40320/24 = 1680.
- De 8 à 16 données, le facteur est 20922789888000/40320 = 518918400.
Le facteur augmentant plus rapidement qu'avec l'exponentielle 2 : c'est un cas pire que l'exponentielle.
3 - Fonctions réciproques
✎ 07° Evaluer les expressions suivantes pour répondre aux questions. La fonction sqrt() correspond à la racine carrée.
>>> from math import sqrt
>>> (sqrt(25))**2
25.0
>>> (sqrt(1250))**2
1250.0
>>> sqrt(25**2)
25.0.
>>> sqrt(1250**2)
1250.0
Question
Pourquoi dit-on que la fonction carré et la fonction racine carrée sont réciproques ?
...CORRECTION...
On constate que l'utilisation de l'une des fonctions sur le résultat de l'autre revient à retrouver l'entrée de départ.
>>> (sqrt(25))**2
25.0
>>> (sqrt(1250))**2
1250.0
>>> sqrt(25**2)
25.0.
>>> sqrt(1250**2)
1250.0
Deux fonctions sont réciproques lorsque l'utilisation successive de l'une des fonctions sur l'autre compense les effets et qu'on revient à la valeur de base.
>>> from math import sqrt
>>> sqrt(5**2)
5.0
Remarque : attention au domaine de définition. Ici, il faut que x soit positif.
✎ 08° Evaluer les expressions suivantes pour répondre aux questions.
>>> from math import log2
>>> log2(2**32)
32.0
>>> log2(2**64)
64.0
>>> 2**(log2(32))
32
>>> 2**(log2(64))
64
Question
Pourquoi peut-on dire que la fonction logarithme 2 et la fonction exponentielle 2 sont des fonctions réciproques ?
...CORRECTION...
On constate que l'utilisation de l'une des fonctions sur le résultat de l'autre revient à retrouver l'entrée de départ.
>>> log2(2**32)
32.0
>>> log2(2**64)
64.0
>>> 2**(log2(32))
32
>>> 2**(log2(64))
64
Deux fonctions sont réciproques lorsque l'utilisation successive de l'une des fonctions sur l'autre compense les effets et qu'on revient à la valeur de base.
On peut donc écrire de façon générale :
Si on allège l'écriture en notant simplement log plutôt que log2 :
FIN
Activité publiée le 17 11 2023
Dernière modification : 17 11 2023
Auteur : ows. h.