28 - Exos Coûts
Pensez à garder une trace de votre travail, soit sous forme papier, soit en remplissant la copie numérique.
1 - Coûts "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 32.
- Que se passe-t-il lorsque la valeur fournie est multipliée par 2 par rapport à un cas déjà calculé ?
...CORRECTION...
✎ 02° On considère qu'un programme est à coût logarithmique (log2). Avec 40 données, il a fallu 12 opérations basiques pour répondre au problème. Combien d'opérations faut-il globalement pour répondre au problème avec 80 données à traiter ?
...CORRECTION...
Coût logarithmique base 2 : si on double les données, on rajoute une opération à coût constant.
Avec 80 données, il faudra donc 13 opérations.
Avec 160 données, il faudra donc 14 opérations.
✎ 03° On considère qu'un programme est à coût linéaire. Avec 40 données, il a fallu 12 opérations basiques pour répondre au problème. Combien d'opérations faut-il globalement pour répondre au problème avec 80 données à traiter ?
...CORRECTION...
Coût linéaire : si on double les données, on double globalement le nombre d'opérations.
Avec 80 données, il faudra donc 24 opérations.
✎ 04° On considère qu'un programme est à coût quadratique. Avec 40 données, il a fallu 12 opérations basiques pour répondre au problème. Combien d'opérations faut-il globalement pour répondre au problème avec 80 données à traiter ?
Même question avec 160 données.
...CORRECTION...
Coût quadratique : si on double les données, on quadruple globalement le nombre d'opérations.
Avec 80 données, il faudra donc 4*12 = 48 opérations.
Avec 160 données (4 fois plus que 40), il faudra donc 16*12 = 192 opérations.
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
- ...
Ainsi, passer de 10 données à 20 données correspond au même facteur que passer de 10 milliards de données à 20 milliards de données.
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.
...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 :
- En passant de 4 à 8 données, le facteur est 256/16 = 16.
- En passant 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
Question
- 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.
- En passant de 4 à 8 données, le facteur est 40320/24 = 1680.
- En passant de 8 à 16 données, le facteur est 20922789888000/40320 = 518918400.
Le facteur augmentant visiblement plus rapidement qu'avec l'exponentielle 2, on peut en déduire qu'il s'agit d'un cas encore 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.
$${\sqrt{x^2}}=x$$
$${(\sqrt{x})^{ 2}}=x$$
>>> 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 :
$${\log_{2}{2^x}}=x$$
$${2^{\log_{2}{x}}}=x$$
Si on allège l'écriture en notant simplement log plutôt que log2 :
$${\log{2^x}}=x$$
$${2^{\log{x}}}=x$$
FIN
Activité publiée le 17 11 2023
Dernière modification : 17 11 2023
Auteur : ows. h.