Alice déménage, malheureusement, elle s'est cassé le bras. Avec un plâtre, elle n'a plus qu'une main pour manipuler tous ses cartons... Elle va appeler ses amis à la rescousse.
Pourquoi ? Pour les ranger proprement et optimiser la place dans le camion !
Avant l'arrivée de ses amis, elle décide de remettre la main sur le carton qui contient les boîtes de gâteaux.
Recherche d'un carton en particulier
01° Mise en place : prendre les 24 cartons et les répartir au hasard sur votre table en les retournant de façon à ne pas pouvoir voir le numéro. Pourquoi ? Tout simplement car un ordinateur ne peut pas avoir une vue d'ensemble comme un humain. Il ne peut lire qu'une variable à la fois.
Début de l'activité
Vous êtes Alice (et vous n'avez qu'un bras valide en ce moment, n'oubliez pas !). Le carton des gâteaux est le carton numéro 9. Vous ne pouvez inspecter qu'un carton à la fois. Pour cela, vous avez uniquement le droit de retourner TOTALEMENT ALEATOIREMENT un carton à la fois :
Si c'est le bon, vous avez fini, bravo !
Sinon, il faut replacer le carton face cachée exactement au même endroit que là où vous l'avez pris et en tirer un nouveau de façon aléatoire.
Deux questions :
combien de cartons avez-vous dû regarder avant de trouver le bon ?
Quel est le problème qu'on rencontrerait si on avait 1000 cartons ?
...CORRECTION...
Potentiellement entre
1 carton (bravo, vous avez de la chance !)
beaucoup beaucoup de cartons : pas de chance et vous avez oublié quel carton vous avez déjà fouillé. Du coup, vous avez fouillé le même carton plusieurs fois sans vous en rendre compte !
Comme vous n'êtes pas venus ici pour jouer à Memory, et que nous voulons éviter de boucler à l'infini, nous allons plutôt ordonner nos cartons. Cela ne va rien changer à l'aspect "avoir de la chance" mais cela va grandement aider du côté sur l'aspect "être attentif".
Les cartons d'Alice, alignés cette fois
02° Prendre les cartons et les placer aléatoirement (face cachée) mais cette fois alignés les uns à côté des autres.
Vous devriez donc obtenir une ou deux lignes sur votre table.
Questions :
combien de cartons avez-vous dû regarder avant de trouver le carton portant le numéro 9 ?
en ayant beaucoup de chance, combien de recherches dans le meilleur des cas ?
en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas ?
en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas si on avait 1000 cartons plutôt que 24 ?
en n'ayant vraiment pas de chance, combien de recherches dans le pire des cas si on avait 1 million de cartons ?
...CORRECTION...
On retrouve presque le même cas qu'auparavant. Entre 1 et 24.
Mais dans le pire des cas, on aura 24 recherches au maximum, jamais plus. Il suffit de suivre l'ordre des cartons : plus moyen d'en louper un ou de chercher dans le même plusieurs fois de suite.
Dans le pire des cas, 1000 recherches pour mille cartons.
Dans le pire des cas, 1 000 000 de recherches pour un million de cartons.
03° Bob, l'ami d'Alice arrive. Il va pouvoir aider Alice à trouver le carton 14 qui contient les clés du camion pendant qu'Alice continue sa propre recherche.
On considère donc que les cartons sont alignés et fermés (votre carton est face cachéé).
donner les instructions précises (en français) qu'Alice doit donner à Bob pour chercher le carton numéro 14 en garantissant qu'il ne cherche jamais deux fois à l'intérieur du même carton ?
en appliquant ces instructions, combien de cartons avez-vous dû regarder pour savoir si le carton 14 existe (ou pas) ?
combien d'observations aurait-on dû faire si on avait 1000 cartons ?
combien d'observations aurait-on dû faire si on avait 1 million de cartons ?
On parle d'une action à coût CONSTANT lorsque le nombre d'opérations à faire est le même quelque soit le nombre de données à traiter. Notre recherche est-elle à coût CONSTANT ?
Pourquoi parle-t-on de coût LINEAIRE ?
...CORRECTION...
Deux solutions utilisant juste des phrases mais où on retrouve les outils de base de l'informatique. Si vous avez pensé à l'écrire ainsi, chapeau.
1er solution
Pour chaque carton (en commençant par celui de gauche), vérifier si ce carton est le bon. Si c'est le cas, ramener le carton immédiatement. Sinon, si ce carton n'est pas le dernier, passe au suivant.
2e solution
Commence par vérifier le premier carton. Tant qu'il reste des cartons à vérifier et que le carton actuel n'est pas le bon, passe au carton suivant.
3e solution
Prendre le premier carton
Lire et mémoriser son numero
TANT QUE vous n'avez pas trouvé le bon numero de carton et qu'il reste un carton à droite
Prendre le carton suivant
Lire et mémoriser son numero
SI c'est n'est pas le bon numero de carton
Reposer le carton face cachée
Fin SI
Fin TANT QUE
Transporter le carton portant le bon numero sur la table
Nombre d'essais
Le carton 14 n'existe pas ! On se retrouve donc dans le pire des cas.
Avec 24 cartons, il faut 24 ouvertures de cartons.
Avec 1000 cartons, il faut 1000 ouvertures de cartons.
Avec 1 million cartons, il faut 1 million d(ouvertures de cartons.
Coût constant ?
Non puisqu'on voit que plus il y a de cartons, plus il faudra agir avant de trouver.
Coût linéaire
On parle de coût LINEAIRE puisque le nombre d'opérations élémentaires dépend visiblement du nombre n de cartons à traiter.
Chargement des cartons
Le déménagement prend du temps car Alice veut que Bob charge le carton. Elle lui donne donc à chaque fois le numéro du carton qu'il faut maintenant ranger dans le camion mais Bob n'a jamais de chance... Le carton qu'il cherche est toujours le dernier dans sa recherche...
Ainsi, avec un ensemble de 24 cartons, la recherche de bon premier carton coûte 24. Une fois celui dans le camion, la recherche du bon carton suivant ne demandera que 23 recherches dans le pire des cas, ect...
04°
Questions
S'il n'y a que 6 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas.
S'il n'y a que 12 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas.
Avec nos 24 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas .
Pourquoi ne peut-il pas s'agir d'une action à coût CONSTANT ?
Pourquoi ne peut-il pas s'agir d'une action à coût LINEAIRE ?
...CORRECTION...
S'il n'y a que 6 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas.
On obtient 6+5+4+3+2+1 = 21 recherches.
Sinon, Python c'est bien aussi :
>>> somme = 0↲>>> for valeur in range(1, 7):↲
somme = somme + valeur↲↲>>> somme↲21
S'il n'y a que 12 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas.
On obtient 12+11+10+...3+2+1 = 78 recherches.
Avec nos 24 cartons, calculer le nombre d'opérations pour ce chargement de camion dans le pire des cas .
On obtient 24+23+22+...3+2+1 = 300 recherches.
Pourquoi ne peut-il pas s'agir d'une action à coût CONSTANT ?
Si le coût étant constant, nous aurions eu le même nombre d'opérations quelque soit le nombre de cartons.
Pourquoi ne peut-il pas s'agir d'une action à coût LINEAIRE ?
Si le coût était linéaire, en doublant les données, on doublerait approximativement le nombre d'opérations.
Or :
lorsque passe de 6 à 12 cartons (2 fois plus), on passe de 21 à 78 opérations (4 fois plus en gros).
lorsque passe de 12 à 24 cartons (2 fois plus), on passe de 78 à 300 opérations (4 fois plus en gros).
On constate donc qu'en doublant les données, on fait plus que quadruple les actions à faire.
Nous montrerons plus tard dans l'année que le coût de cette opération est quadratique : il dépend de n2.
Définition ALGORITHME : un algorithme est un ensemble fini(au sens "pas infini") d'instructions précises permettant de résoudre une classe de problèmes. L'algorithme doit être écrit sans ambiguïté, et être facilement transposable dans n'importe quel langage de programmation.
Le mot classe est ici important : on doit pouvoir résoudre un type de problèmes et pas un cas unique. Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.
De façon plus schématique, un algorithme reçoit des données en ENTREE, effectue des calculs sur ces données et produit une valeur de SORTIE.
ENTREE(S) → Algorithme → SORTIE
Comme vous pouvez le voir, cela ressemble fort à ce qu'on pourrait définir comme une fonction. Ce n'est pas un hasard, nous le verrons en Terminale.
Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.
On sépare réflexion et exécution.
La réflexion est utilisée par l'informaticien ou l'informaticienne lors de l'élaboration de l'algorithme.
Lors du déroulement de l'algorithme, l'ordinateur exécute. Point.
En réalité, cette définition est floue. Elle comporte beaucoup de non-dits. Nous verrons une définition plus formelle en Terminale.
Exemple de ce qui ne sera pas vu comme un algorithme : la multiplication de 5 par 4. C'est une cas unique. Pas de possibilité de modifier quoi que ce soit. Il s'agit juste d'une suite d'instructions.
Exemple de ce qui peut être vu comme un algorithme : la multiplication de a par b, a et b étant des nombres réels (on peut avoir 5*4, 15*99 ...). On pourrait en effet dire qu'on initialise un compteur à 0 et qu'on réalise une boucle a fois : on stocke dans le compteur la somme du compteur et de b.
Exemple : pour 3 x 8, on a donc compteur = 0 + 8 + 8 + 8 = 24.
Pour parvenir à comparer l'efficacité des algorithmes, on cherche souvent à voir comment l'algorithme va gérer l'augmentation des données à traiter.
2 Introduction à la notion de coût d'un algorithme
Définition
Le coût d'un algorithme exprime la façon dont l'algorithme réagit globalement à l'augmentation du nombre n de données à traiter.
On évalue souvent le coût dans le pire des cas car il borne le comportement de l'algorithme : s'il se comporte bien dans le pire des cas, c'est qu'à priori nous allons pouvoir l'utiliser.
Coût constant (noté 1 ou CST)
Si n*2 alors op inchangé
Si on modifie le nombre n de données, le nombre d'opérations élémentaires op reste le même.
Exemple
Avec n = 6 données, on a besoin de op = 5 opérations élémentaires.
Si n*2 (n = 12), alors op = 5.
Si n*4 (n = 24), alors op = 5.
Si n*8 (n = 48), alors op = 5.
C'est donc pas mal !
Coût linéaire (noté n)
Si n*2 alors op*2
Si on double le nombre n de données, on double le nombre op d'opérations élémentaires.
De façon plus détaillée,
si n est multiplié par 2, alors on multiple op par 2;
si n est multiplié par 3, alors on multiple op par 3;
si n est multiplié par 4, alors on multiple op par 4
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op*2 soit 5*2=10 opérations.
Si n*4 (24 données), on aura op*4 soit 5*4=20 opérations.
Si n*8 (48 données), on aura op*8 soit 5*8=40 opérations.
C'est un peu plus long que du coût constant.
Coût quadratique (noté n2)
Si n*2 alors op*(22)
Si on double le nombre n de données, on quadruple le nombre op d'opérations élémentaires.
De façon plus détaillée,
si n est multiplié par 2, alors on multiple op par 22;
si n est multiplié par 3, alors on multiple op par 32;
si n est multiplié par 4, alors on multiple op par 42
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op*22 soit 5*4=20 opérations.
Si n*4 (24 données), on aura op*42 soit 5*16=80 opérations.
Si n*8 (48 données), on aura op*82 soit 5*64=320 opérations.
Cela devient réellement de plus en plus grand lorsque les données deviennent importantes.
Coût polynomial (noté nk)
Si n*2 alors op*(2k)
Si on multiple par 2 le nombre n de données, on multiple par la constante 2k le nombre op d'opérations élémentaires.
De façon plus détaillée,
si n est multiplié par 2, alors on multiple op par 2k;
si n est multiplié par 3, alors on multiple op par 3k;
si n est multiplié par 4, alors on multiple op par 4k
...
On notera que le coût linéaire et le coût quadratique sont des coûts polynomiaux !
k=1 correspond au linéaire et
k=2 correspond au quadratique.
05° Voici un algorithme qui permet de demander des notes à un système et qui calcule la moyenne des notes qu'on nous a donné.
On considère qu'une affectation, un appel à demanderUneNote() et l'utilisation de Renvoyer sont des opérations élémentaires.
Questions
Déterminer le nombre d'opérations élémentaires nécessaires pour que l'algorithme notes() réponde.
S'agit-il d'un algorithme à coût constant ou à coût linéaire ?
Algorithme de notes(n)
somme ← 0
Le POUR ci-dessous permet de faire l'action n fois
POURx variant de 0 à (n-1)
note ← demanderUneNote()
on obtient une note valide
somme ← somme+note
on rajoute les notes au fur et à mesure
Fin POUR
Renvoyersomme
...CORRECTION...
On suppose que demanderUneNote() est une fonction à coût constant.
Faisons le bilan du nombre d'actions élémentaires :
1 opération élémentaire pour l'affectation à 0;
2*n opérations élémentaires pour la boucle : on la réalise n fois et elle contient 2 opérations élémentaires;
1 opération élémentaire pour Renvoyer
On a donc 2n + 2 opérations élémentaires pour un ensemble n de données.
Pour 10 données, on a besoin de 20 + 2 = 22 opérations : globalement x10.
Pour 100 données, on a besoin de 200 + 2 = 202 opérations : globalement x100.
Pour 1000 données, on a besoin de 2000 + 2 = 2002 opérations : globalement x1000.
Ces résulats montrent qu'il s'agit d'un algorithme à coût linéaire.
3 Algorithmique
L'algorithmique consiste à étudier des problèmes en vue de les résoudre à l'aide d'un algorithme le plus efficace possible.
On cherche donc :
à estimer la rapidité d'exécution de l'algorithme.
Cela revient à connaître le coût de l'algorithme.
à vérifier que la réponse éventuelle soit juste.
Cette vérification se nomme la preuve de correction.
à vérifier qu'il s'arrête bien sur n'importe quelle entrée fournie.
Cette vérification se nomme la preuve de terminaison.
Au tir à l'arc, Alice préfère planter la flèche à la main ! C'est plus précis.
Alors que la moitié du chargement est déjà parti, Alice se souvient de ses cours d'informatique : son prof d'informatique lui avait dit qu'on ne stocke jamais une donnée sans la trier si c'est possible. Elle décide donc de trier les cartons restants en fonction de leur numéro.
06° Exécuter ces actions :
Prendre au hasard 12 cartons parmi les 24.
Placer les cartons face visible.
Trier les cartons du plus petit au plus grand numéro.
Retourner les cartons face cachée pour cacher le numéro.
12 cartons : 12 recherches à faire pour trouver un carton précis dans le pire des cas.
Alice dit qu'elle peut maintenant faire bien mieux : elle peut trouver le bon carton au pire en 4 recherches.
Recherche dichotomique
07-A° Alice dit à Bob d'aller voir si le carton 14 existe et de le ramener si c'est le cas. Pour cela, il faut aller voir le carton du milieu (le 6e dans la séquence) et de regarder sa valeur. Comme ils sont classés par ordre de numéro, trois cas se présentent à vous :
Vous trouvez 14 juste à cette position : c'est bon, c'est fini.
Vous trouvez un numéro inférieur à 14 : cela veut dire que le numéro 14 ne peut plus être qu'à droite puisque les cartons sont classés.
Vous trouvez un numéro supérieur à 14 : cela veut dire que le numéro 14 ne peut plus être qu'à gauche.
Combien de cartons Bob va-t-il pouvoir mettre de côté en fouillant le carton du milieu ? Que doit faire Bob ensuite pour continuer sa recherche ?
...CORRECTION...
Il suffit de regarder la valeur qu'on y trouve. Si ce n'est pas 14, on pourra supprimer au moins la moitié des cartons restants.
On passe donc brutalement de 12 cartons à fouiller à 6 cartons en UNE étape.
Il faut aller voir ensuite le milieu des cartons restants : on passe alors de 6 cartons à 3 cartons.
Puis de 3 cartons à 1 carton.
Il suffit alors de regarder le carton restant.
On peut donc espérer trouver le bon carton (ou savoir qu'il n'existe pas) en 4 étapes plutôt qu'en 12.
07-B° Terminer votre recherche en comptant le nombre de cartons que vous avez dû fouiller pour trouver le carton 14 ou apprendre qu'il n'existe pas. Mieux ou moins bien que le coût linéaire.
...CORRECTION...
On a 12 cartons initialement.
1 recherche et on passe à 6 cartons à fouiller encore.
2 recherches et on passe à 3 cartons à fouiller encore.
3 recherches et on passe à 1 carton à fouiller encore.
4 recherches et on passe à 0 carton à fouiller. On a fini.
Il existe donc un coût qui se situe entre le coût constant et le coût linéaire. Il s'agit ici du coût logarithmique. Nous en parlerons beaucoup cette année.
4 - Recherche dichotomique
Elle s'effectue sur des données triées.
On fait une recherche en plein milieu des données.
Si on y trouve moins que ce qu'on cherche, on sait qu'il ne sert plus à rien de fouiller dans la partie gauche.
So on y trouve plus que ce qu'on cherche, on sait qu'il ne sert plus à rien de fouiller dans la partie droite.
A chaque étape, on divise donc le nombre de données par deux.
5 Coût logarithmique
Coût logarithmique base 2 (noté log2(n) ou lg(n)
si n*2 alors op+1
Si on multiple par 2 le nombre n de données, alors on augmente juste op de 1.
De façon plus détaillée,
si n est multiplié par 2, alors on augmente juste op de 1;
si n est multiplié par 4, alors on augmente juste op de 2;
si n est multiplié par 8, alors on augmente juste op de 3;
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op+1 soit 5+1=6 opérations.
Si n*4 (24 données), on aura op+2 soit 5+2=7 opérations.
Si n*8 (48 données), on aura op+3 soit 5+3=8 opérations.
Ce coût se situe donc entre CONSTANT et LINEAIRE.
Logarithmique base 2 et Python
Le calcul du logarithme base 2 du nombre de cartons va permettre de connaître le nombre maximale de fouilles à faire avant de n'avoir plus qu'un carton à fouiller.
Si vous fouillez ce dernier carte, on rajoute 1 à ce nombre, et on obtient le nombre de fouilles maximales à faire.
>>> from math import log2
>>> log2(1)
0.0Il faudra 1 fouille de cartons>>> log2(2)
1.0Il faudra 2 fouilles de cartons>>> log2(4)
2.0Il faudra 3 fouilles de cartons>>> log2(8)
3.0Il faudra 4 fouilles de cartons>>> log2(16)
4.0Il faudra 5 fouilles de cartons>>> log2(17)
4.087462841250339Il faudra 5 fouilles de cartons>>> log2(1000000)
19.931568569324174Il faudra 20 fouilles de cartons
Pourquoi ces valeurs ?
On peut voir la réponse fournie par le log2 comme le fait d'écrire le nombre sous forme d'une puissance de 2 et de ramener la valeur se situant en exposant.
Le camion est plein ! Elle a encore quelques affaires qui trainent et espère pouvoir les placer sur le toit de la voiture s'il reste de la place...
08° Récupérer uniquement les cartons numérotés de 1 à 12. Charger alors le toit au mieux : l'objectif est d'avoir la prise au vent la plus faible possible et donc de tasser pour avoir le moins de hauteur possible.
Une solution est meilleure qu'une autre si la hauteur totale sur le toit est plus petite qu'une autre. En cas d'égalité, on pourrait choisir de mettre en avant celle qui est la plus symétrique puis celle où les trous sont le plus à l'extérieur.
ATTENTION : Alice ne veut pas voir ses affaires détruites : il faudra donc que le H soit dans le bon sens. Pas question de casser des verres !
09° Y-a-t-il plusieurs solutions ? Comment pourrions-nous savoir que votre solution est "la" meilleure ?
...CORRECTION...
Il y a beaucoup de solutions : c'est bien ça le problème !
Pour savoir si on a la meilleure solution, il faudrait pouvoir toutes les tester. Mais ce n'est pas possible.
La seule manière de comparer les solutions est de considèrer que celle qui est la moins haute est meilleure que les autres. Une solution sans trou est certainement la meilleure parmi toutes.
Le problème, c'est qu'on a pas accès à toutes les solutions...
Pour vous montrer que le nombre de possibilités est important, nous allons nous limiter à choisir l'ordre de chargement des cartons dans le camion. Nous allons trouver bien plus que le nombre réel de possibilités, mais cela vous éclairera sur le fait que c'est ... beaucoup.
10° Combien de choix parmi les 12 cartons pour prendre le premier ? Combien de choix pour prendre le deuxième ? Le troisième ?
...CORRECTION...
12 pour le premier.
11 pour le deuxième.
10 pour le troisième...
11° Combien de possibilités de choix à tester ?
...CORRECTION...
Si on ne considère que l'ordre de chargement, on obtient 12*11*10*9*8*7*6*5*4*3*2*1, soit 479 001 600 de possibilités.
Ici, nous avons ce qu'on nomme une factorielle. Nous en reparlerons. C'est un des pires cas possibles : un coût factoriel.
On note ce calcul 12! et on le prononce factorielle 12.
Et cela vaut 12*11*10*9*8*7*6*5*4*3*2*1. Mais c'est plus facile à écrire 12!.
6 Bilan des coûts
Problème facile
Facile en informatique : peut répondre en un temps raisonnable.
Le coût constant (noté 1)
Le coût logarithmique (noté log n)
Le coût polynomial (noté nk)
Problème difficile
Difficile en informatique : temps de calcul déraisonnable.
Le coût exponentiel (noté kn) : avec un tel coût, on estime que l'algorithme n'est pas exploitable à grande échelle. Il va mettre trop de temps pour répondre.
Le coût factoriel (noté n!) : encore moins exploitable.
Il existe une catégorie entière de problèmes énormément complexes dits NP-complets, et ils posent problème.
L'exemple typique de ce type de problème est le problème du voyageur de commerce : un commercial doit passer par toutes les villes de son secteur. Il cherche à optimer son parcours de façon à ce qu'il prenne le moins de temps possible. Comment trouver la solution optimale ?
Voyageur de commerce - Domaine public - Original téléversé par Kapitän Nemo sur Wikipédia allemand. — https://www.cia.gov
Avec 15 villes, on peut énumérer tous les cas possibles et prendre le meilleur. Mais avec 20 000 villes à parcourir, on obtient un temps de calcul beaucoup trop grand pour être exploitable : les tracés routiers risquent d'avoir changé entre temps !
Caractéristiques des problèmes NP
Les propriétés de ces problèmes complexes particuliers sont les suivantes :
Pour un problème donné, vérifier qu'une proposition est bien une solution du problème est facile (en informatique, cela veut dire que le coût est moins qu'exponentiel).
Par contre, rechercher toutes les solutions possibles pour trouver la solution optimale est difficile (en informatique, cela veut dire que le coût est exponentiel ou plus). Cette recherche est donc possible en théorie mais non exploitable en pratique, sauf pour les problèmes aux données d'entrée très réduites.
Malgré énormément de recherche, personne n'a réussi à démontrer qu'il n'existe pas d'algorithme plus rapide pour trouver la solution optimale : il est donc possible qu'une telle solution existe, pas. On ne sait pas.
Il a été démontré que s'il existe un algorithme efficace sur l'un des problèmes NP-complets, il existe des solutions efficaces pour tous problèmes NP !
Une petite simplification de l'énoncé du problème le rend résolvable facilement...
12° Proposer un algorithme qui permettra de remplir le camion. Ne cherchez pas à obtenir LA solution mais à fournir une solution "acceptable" : le problème du remplissage du toit de la voiture est NP de toute façon.
C'est une notation que vous allez voir un peu plus tard. Elle signale que l'algorithme a un coût logarithmique base 2.
Fonctions réciproques
La fonction logarithme base X et la fonction exponentielle base X sont des fonctions réciproques.
Cela veut dire que si on applique l'une de ces fonctions sur l'autre, on va retrouver l'entrée de départ.
x → LOGARITHME → EXPONENTIELLE → x
x → EXPONENTIELLE → LOGARITMHE → x
>>> from math import log2
>>> x = 5
>>> log2(2**5)
5.0>>> 2**(log2(5))
4.999999999999999
Encore une fois : cela fonctionne en mathématique, mais comme on passe par les flottants, il faut falloir se méfier. Ici, la machine répond juste presque la bonne réponse...
Pourtant, parfois, cela marche exactement comme en math :
>>> from math import log2
>>> x = 8
>>> log2(2**8)
8.0>>> 2**(log2(8))
8.0
L'explication dans la leçon sur les flottants.
La fonction exponentielle des maths ?
Il s'agit d'une fonction exponentielle particulière qu'on note e(x).
Pourquoi particulière ? Car elle n'utilise pas un entier comme 2X, 3X...
Elle utilise une constante nommé le constante de Néper ou nombre d'Euler. On la note e.
Il s'agit comme pi d'un nombre qu'on ne peut pas écrire à l'aide d'une suite fini de chiffres.
Il vaut approximativement 2,71...
La fonction exponentielle revient donc à écrire e et à mettre x en exposant : ex.
>>> from math import e # on importe la constante
>>> e
2.718281828459045>>> from math import exp # on importe la fonction exponentielle exp
>>> x = 5
>>> e**5
148.4131591025766>>> exp(5)
148.4131591025766
log lg ln, c'est différent ?
Oui.
Lorsqu'on parle simplement de log, on parle du log dans une base précise mais laquelle ? Si c'est rien n'est précisé, cela dépend du contexte.
En informatique, si on note juste log, on parle du log2.
En physique, si on note juste log, on parle du log10.
En informatique, on utilise également parfois la notation lg qui correspond donc à log2.
Reste la notation ln qui correspond au logarithme népérien qui vous allez voir en mathématique.
Il s'agit du logarithme réciproque de la fonction exponentielle utilisant e.
ln(en) = n.
(eln(n)) = n.
C'est ln est donc un alias de la fonction loge...
Activité publiée le 04 11 2020
Dernière modification : 05 11 2020
Auteur : ows. h.
