Étiquette : logarithme

Et donc, c’est quoi un logarithme ?

Publié le par Balise14 commentaires

Je soupçonne que je vais avoir besoin, dans ma série d’articles d’informatique théorique, de logarithmes. Pourquoi ? Parce que c’est une des fonctions « utiles » lorsque l’on parle de complexité algorithmique. Donc, pour être sûr que tout le monde soit sur la même page, je fais un cours de rattrapage sur les logarithmes. Les gens qui ont de mauvais souvenirs de leurs maths de lycée ont probablement aussi de mauvais souvenirs des logarithmes, et pourtant, les logarithmes, c’est chouette.

En parlant de logarithmes, je ne sais pas comment ils ont été introduits dans vos cours de maths respectifs ; pour ma part, je suis à peu près sûre qu’on me l’a défini à partir de l’intégrale de la fonction inverse. RESTE ICI, C’EST PAS CE QUE JE VAIS FAIRE. Enfin pas tout de suite. Je vais commencer par essayer de donner une intuition du bidule.

arbre

Considérons la figure que je viens d’insérer avec brio dans mon billet. Je suis partie d’un point, à partir de ce point j’ai fait deux branches, au bout desquelles j’ai ajouté un point ; sur chacun de ces points, j’ai ajouté deux branches, au bout desquelles j’ai ajouté un point, et ainsi de suite. J’aurais pu continuer comme ça longtemps, conceptuellement – je vais avoir des problèmes de place et des problèmes de fatigue (ça va être pénible très vite d’ajouter des ptits points), mais conceptuellement, je pense qu’on peut tous imaginer un arbre comme celui-ci avec autant de niveaux qu’on le souhaite.  Supposons aussi, parce qu’on fait de l’informatique, que la « racine » de l’arbre (le tout premier point que j’ai ajouté sur ma figure) soit au niveau 0. Si je « retourne » l’arbre, ça peut avoir une certaine logique, c’est le « rez-de-chaussée », et le niveau suivant est le « premier étage ». Supposons maintenant que je veuille compter le nombre de « feuilles » de mon arbre, c’est-à-dire le nombre de points que j’ai sur le dernier niveau de mon arbre.

Il est assez clair que le nombre de feuilles dépend du niveau auquel j’arrête mon arbre, et qu’il augmente à chaque niveau. Si je m’arrête au niveau 0, j’ai 1 feuille. Si je m’arrête au niveau 1, je multiplie ça par deux (parce que je fais deux branches), ça fait 2. Si je m’arrête au niveau 2, je multiplie le nombre de feuilles du niveau 1 par deux encore, ça fait 4. Et à chaque niveau, je prends le nombre de feuilles du niveau précédent et je le multiplie encore par deux. Au niveau 3, j’aurai donc 2*2*2 = 8 feuilles et, au niveau 4, 2*2*2*2 = 16 feuilles. Pour connaître le nombre de feuilles au niveau numéro n, où n est le numéro de mon niveau, je fais n multiplications de 2 par lui-même, ce qui s’écrit 2^n (et se lit « deux à la puissance n »).

Supposons à présent que je ne veuille pas connaître le nombre de feuilles correspondant à un niveau, mais le nombre de niveaux correspondant à un nombre de feuilles donné. Par exemple, j’ai 2 feuilles : ça correspond au niveau 1. 16 feuilles : ça correspond au niveau 4. Si j’en ai 32, ça correspond au niveau 5. Et si j’ai 128 feuilles, ça correspond au niveau 7. Bon, évidemment, ça se complique un peu si j’ai, mettons, 20 feuilles. 20 feuilles, ça correspond à un niveau « 4 et des poussières » – j’ai dessiné jusqu’au niveau 4, j’ai commencé à dessiner le niveau 5, et j’ai eu la flemme de finir. Cette opération, qui est l’opération réciproque de l’opération précédente, c’est un logarithme. Je dis que c’est l’opération réciproque, parce qu’elle me permet de « défaire » l’opération précédente. Je prends un nombre n, j’en prends la puissance de 2, ça me donne 2^n, et si je reprends le logarithme de ça, j’ai

\log(2^n)= n

De la même manière, si j’ai un nombre n, que j’en prends le logarithme, et que j’en reprends la puissance de 2, j’ai

2^{\log n} = n

Bon, c’est bien gentil, tout ça, mais qu’est-ce qu’il se passe, si au lieu de faire deux branches à chaque étape, j’en fais 3 ? Selon le même raisonnement que précédemment, au niveau n, j’ai 3*3*…*3 feuilles, c’est à dire 3^n. Et, bon, ben de la même manière, je peux définir un logarithme qui soit la réciproque de ce 3^n. Mais, bon, je veux pouvoir les distinguer – donc je mets la puissance à laquelle ils correspondent en indice, comme ceci :

\log_2, \log_3

avec

3^{log_3 n} = n

et

\log_3(3^n) = n

L’indice de mon logarithme, on appelle ça la « base » du logarithme. J’en profite pour faire une petite remarque sur le logarithme en base 10 (c’est aussi valable pour les autres bases, au moins entières, de logarithmes, mais je ne rentre pas là-dedans). Il est très facile d’avoir une évaluation « à la louche » du logarithme en base 10 d’un nombre. C’est le nombre de chiffres du nombre en question, moins 1. On a \log_{10}(10) = 1, \log_{10}(100) = 2 (parce que 10^2 = 100); tous les nombres entre 10 et 100 ont un logarithme en base 10 entre 1 et 2. De la même manière, on peut estimer que le logarithme en base 10 de 14578 est entre 4 et 5. Pour voir ça, il suffit de voir que 14578 est compris entre 10000 = 10^4 et 100000 = 10^5, ce qui permet de conclure sur la valeur du logarithme. (Je passe un certain nombre de choses sous le tapis ici, en particulier les raisons qui font qu’on peut effectivement conclure ça.)

Bon, cela dit, maintenant que j’ai défini des bases de logarithme, qu’est-ce qui m’empêche d’utiliser des bases « exotiques » pour mes logarithmes ? La réponse est « rien ». Je peux définir un logarithme en base 3.5 (qui correspond à la puissance à laquelle j’élève 3.5 pour obtenir le nombre dont je prends le logarithme en base 3.5), \frac 5 3 (qui correspond à la puissance à laquelle j’élève \frac 5 3 pour obtenir le nombre dont je prends le logarithme en base \frac 5 3), ou même \pi (qui correspond à… bon, ça ira, peut-être) si ça me chante. C’est moins « intuitif » si je considère mon explication avec les arbres et le nombre de niveaux (parce que c’est difficile de faire \pi branches), mais en considérant la réciproque des fonctions puissance, ça me paraît raisonnablement clair.

La question suivante qu’on peut se poser, c’est si tous ces logarithmes en différentes bases ont un lien entre elles, ou plus exactement si on peut les exprimer d’une façon commune. La réponse est « oui ». C’est ici que j’introduis le logarithme népérien, aussi appelé logarithme naturel, dénoté \ln. Le logarithme népérien est un logarithme en base e \approx 2.71828. On peut exprimer n’importe quel logarithme dans n’importe quelle base a comme ceci :

\log_a(x) = \frac{\ln x}{\ln a}

Ce qui veut aussi dire qu’on peut passer d’un logarithme d’une base a à un logarithme d’une base b comme ça :

\log_a(x) = \frac{\ln x}{\ln a} = \frac{\ln x}{\ln b} \times \frac{\ln b}{\ln a} = \frac{\ln b}{\ln a}\log_b(x)

(Et oui, c’est typiquement le genre de chose que j’ai dans mon formulaire d’examen, parce que je me souviens jamais dans quel sens c’est !)

L’important à retenir, ici, c’est que tous les logarithmes sont égaux « à une constante près » ; ils ont le même « comportement asymptotique » (j’introduis les termes ici, mais je ferai un billet spécifique sur le sujet, parce que c’est un peu long à expliquer). C’est intéressant dans le domaine qui nous préoccupe ici, parce qu’on s’intéresse surtout à l’estimation des comportements « à une constante près » quand on parle de temps d’exécution ou d’occupation mémoire d’un algorithme. Encore une fois, j’y reviendrai – prenez ça comme un « spoiler » des prochains épisodes 🙂

J’en arrive à la relation entre le logarithme népérien et la fonction inverse. Formellement, on écrit que

\ln(x) = \int_1^x \frac 1 t \text{d}t

Et voilà ce que ça veut dire, graphiquement :

log

La courbe rouge est la courbe de la fonction x \mapsto 1/x. La zone grise correspond ici à l’intégrale de 1 à 6 ; l’aire de cette zone est égale à ln(6). Et on peut représenter le logarithme népérien de n’importe quelle valeur (supérieure à 1) par l’aire de la surface située entre l’axe des x et la courbe x \mapsto 1/x, prise entre 1 et cette valeur. Remarquons au passage que cette aire est égale à 1 lorsqu’on la considère entre 1 et e, e étant la base du logarithme népérien (parce que ln(e) = 1).

Et pour finir, une propriété intéressante de la fonction logarithme : on peut écrire (dans n’importe quelle base du logarithme)

\log(a \times b) = \log(a) +\log (b)

\log(a/b) = \log(a) - \log(b)

En tant que réciproque de la fonction puissance, c’est assez clair de voir ça. Étant entendu que si deux puissances d’un même nombre sont égales, alors l’exposant l’est aussi, on a d’une part :

2^{\log_2(a \times b) } = a \times b

et d’autre part

2^{\log_2 a + \log_2 b} = 2^{\log_2 a}\times 2^{\log_2 b} = a \times b

On peut dériver la deuxième égalité de la même manière – hop, exercice 😛

Notons au passage que c’est à cause de ce genre de propriété que les logarithmes ont été utilisés au départ. Si on a une grosse table avec plein de correspondances « nombre/logarithme », et qu’on veut multiplier deux nombres facilement, on regarde dans la table les logarithmes des deux nombres, on les ajoute (ce qui est vachement plus facile que de les multiplier), et on regarde la valeur correspondante du logarithme (on utilise la table dans l’autre sens) pour avoir la valeur des deux nombres initiaux multipliés. Historiquement, ce genre de tables est apparu au XVIIe siècle (on remerciera M. Napier) pour faciliter les calculs astronomiques ; la règle à calcul fonctionne également sur ce principe ; et tout ça n’a été détrôné que par l’arrivée, plutôt récente, des machines à calculer et des calculatrices…

Bref, les logarithmes, c’est cool. Et j’espère que vous en êtes à présent aussi persuadés que moi 🙂