Nombres, puissance et logarithme
Les nombres, les puissances et les logarithmes constituent l'un des fondements des mathématiques utilisées en informatique. Ces notions interviennent dans pratiquement tous les domaines de la programmation, qu'il s'agisse de l'analyse des algorithmes, de la cryptographie, de l'intelligence artificielle, du traitement d'images, des simulations numériques ou encore de la compression de données. Elles permettent de décrire la croissance d'un algorithme, de manipuler des très grands nombres, d'exprimer des phénomènes exponentiels ou de résoudre des problèmes impliquant des puissances.
En informatique, les puissances sont omniprésentes. Les ordinateurs fonctionnent en base 2, les capacités mémoire sont généralement exprimées sous forme de puissances de deux, les algorithmes récursifs utilisent fréquemment des divisions successives, tandis que la complexité de nombreux algorithmes fait intervenir les fonctions logarithmiques. Une bonne compréhension de ces notions est donc indispensable pour tout programmeur souhaitant maîtriser les aspects mathématiques de l'algorithmique.
Les ensembles de nombres
Les mathématiques distinguent plusieurs catégories de nombres.
Les principales sont :
| Ensemble | Symbole | Description |
|---|---|---|
| Nombres naturels | ℕ | Entiers positifs utilisés pour compter (0, 1, 2, 3, ...). |
| Nombres entiers | ℤ | Nombres naturels auxquels s'ajoutent les entiers négatifs (..., -2, -1, 0, 1, 2, ...). |
| Nombres rationnels | ℚ | Nombres pouvant s'écrire sous la forme d'une fraction a/b. |
| Nombres réels | ℝ | Ensemble contenant les nombres rationnels et irrationnels. |
| Nombres complexes | ℂ | Nombres composés d'une partie réelle et d'une partie imaginaire. |
En programmation, ces ensembles correspondent généralement à différents types numériques proposés par les langages de programmation.
Les puissances
Une puissance représente une multiplication répétée d'un même nombre.
La notation générale est :
| an |
où :
- a est appelée la base ;
- n est appelé l'exposant.
Par exemple :
|
23 = 2 × 2 × 2 = 8 102 = 100 54 = 625 |
Les puissances permettent d'écrire très simplement des nombres extrêmement grands ou extrêmement petits.
Les propriétés des puissances
Les puissances possèdent plusieurs propriétés importantes.
Produit de deux puissances
Lorsque la base est identique :
| am × an = am+n |
Exemple :
|
23 × 22 = 25 = 32 |
Quotient de deux puissances
| am / an = am-n |
Exemple :
|
27 / 24 = 23 = 8 |
Puissance d'une puissance
| (am)n = amn |
Exemple :
|
(32)4 = 38 |
Produit élevé à une puissance
| (ab)n = anbn |
Exemple :
|
(2×3)2 = 22×32 = 36 |
Exposant nul
Toute base non nulle élevée à la puissance zéro vaut :
| a0 = 1 |
Exemple :
| 150 = 1 |
Exposant négatif
Un exposant négatif correspond à l'inverse d'une puissance positive.
| a-n = 1 / an |
Exemple :
| 2-3 = 1/8 |
Cette propriété est fréquemment utilisée dans les calculs numériques.
Les puissances de deux
En informatique, les puissances de deux jouent un rôle fondamental.
Quelques valeurs importantes :
| Puissance | Valeur |
|---|---|
| 20 | 1 |
| 21 | 2 |
| 22 | 4 |
| 23 | 8 |
| 24 | 16 |
| 25 | 32 |
| 26 | 64 |
| 27 | 128 |
| 28 | 256 |
| 210 | 1 024 |
| 216 | 65 536 |
| 232 | 4 294 967 296 |
| 264 | 18 446 744 073 709 551 616 |
Ces valeurs sont utilisées pour :
- la taille des registres ;
- les capacités mémoire ;
- les systèmes de fichiers ;
- les masques binaires ;
- les adresses mémoire.
- Les logarithmes
Le logarithme est l'opération inverse de la puissance.
Autrement dit, si :
| ax = b |
alors :
| loga(b)=x |
Autrement dit, le logarithme répond à la question :
« Quelle puissance faut-il appliquer à la base a pour obtenir b ? »
Par exemple :
| 25 = 32 |
donc :
| log2(32)=5 |
Les principaux logarithmes
Les plus utilisés sont :
| Nom | Notation | Base |
|---|---|---|
| Logarithme décimal | log(x) | 10 |
| Logarithme naturel | ln(x) | e |
| Logarithme binaire | log2(x) | 2 |
En informatique, le logarithme binaire est de loin le plus courant.
Les propriétés des logarithmes
Les logarithmes possèdent plusieurs propriétés importantes.
Produit
|
log(ab) = log(a)+log(b) |
Quotient
|
log(a/b) = log(a)-log(b) |
Puissance
|
log(an) = n log(a) |
Changement de base
Lorsqu'un langage de programmation ne fournit pas directement le logarithme dans la base désirée, on utilise :
|
log_b(x) = log(x) / log(b) |
Cette formule permet de calculer un logarithme dans n'importe quelle base.
Les logarithmes en algorithmique
Les logarithmes apparaissent très fréquemment dans l'analyse des algorithmes.
Par exemple :
| Complexité | Exemple |
|---|---|
| O(log n) | Recherche binaire |
| O(n log n) | Tri fusion, tri rapide (cas moyen), tri par tas |
| O(log2 n) | Certains algorithmes géométriques |
| O(log log n) | Structures de données spécialisées |
Le logarithme mesure généralement le nombre de divisions successives par deux.
Par exemple :
|
1024 ↓ 512 ↓ 256 ↓ 128 ↓ 64 ↓ 32 ↓ 16 ↓ 8 ↓ 4 ↓ 2 ↓ 1 |
Il faut 10 divisions pour atteindre 1.
Ainsi :
| log2(1024)=10 |
Les puissances dans les langages de programmation
Selon les langages, les puissances sont calculées de différentes façons.
Quelques exemples :
| Langage | Exemple |
|---|---|
| C | pow(2,8) |
| C++ | std::pow(2,8) |
| Java | Math.pow(2,8) |
| C# | Math.Pow(2,8) |
| Python | 2 ** 8 ou pow(2,8) |
| JavaScript | 2 ** 8 ou Math.pow(2,8) |
| Pascal | Power(2,8) (Delphi/Free Pascal) |
Les logarithmes sont généralement disponibles dans les bibliothèques mathématiques standard.
Applications
Les puissances et les logarithmes sont utilisés dans de nombreux domaines :
- analyse des algorithmes ;
- cryptographie ;
- compression de données ;
- intelligence artificielle ;
- probabilités ;
- traitement d'images ;
- calcul scientifique ;
- statistiques ;
- théorie des graphes ;
- réseaux informatiques ;
- apprentissage automatique (Machine Learning).
Ils interviennent également dans la représentation des nombres à virgule flottante, les arbres binaires équilibrés, les tables de hachage et de nombreux algorithmes de recherche.
Avantages
L'utilisation des puissances et des logarithmes présente plusieurs avantages :
- elle simplifie l'écriture des très grands nombres ;
- elle permet de décrire efficacement la croissance des algorithmes ;
- elle facilite la résolution de nombreuses équations ;
- elle est indispensable en cryptographie et en calcul scientifique ;
- elle constitue l'un des fondements de l'analyse de complexité.
Remarque
Les puissances et les logarithmes sont omniprésents en informatique. Une simple capacité mémoire de 16 Go représente 234 octets, une clef cryptographique RSA de 2 048 bits repose sur les propriétés des puissances et de l'arithmétique modulaire, tandis que les performances de nombreux algorithmes sont évaluées à l'aide de fonctions logarithmiques. La maîtrise de ces notions constitue donc une étape essentielle avant l'étude de l'analyse des algorithmes, de la théorie des nombres, des structures de données et des méthodes de calcul avancées utilisées dans les langages de programmation modernes.