2.5 Repr´ esentation des nombres en machine
45
L’efficacit´ e signifie que la complexit´ e du calcul (c’est-` a-dire la quantit´ e
d’op´ erations et la taille de m´ emoire requise) n´ ecessaire pour maˆ ıtriser l’erreur
est aussi petite que possible.
Ayant rencontr´ e plusieurs fois dans cette section le terme algorithme, nous ne
pouvons nous dispenser de donner une description intuitive de ce dont il s’agit.
Par algorithme, nous entendons une d´ emarche qui d´ ecrit, ` a l’aide d’op´ erations
´ el´ ementaires, toutes les ´ etapes n´ ecessaires ` a la r´ esolution d’un probl` eme sp´ ecifique. Un algorithme peut `
a son tour contenir des sous-algorithmes. Il doit
avoir la propri´ et´ e de s’achever apr` es un nombre fini d’op´ erations ´ el´ ementaires.
Celui qui ex´ ecute l’algorithme (une machine ou un ˆ etre humain) doit y trouver
toutes les instructions pour r´ esoudre compl` etement le probl` eme consid´ er´ e (` a
condition que les ressources n´ ecessaires ` a son ex´ ecution soient disponibles).
Par exemple, l’assertion “un polynˆ ome du second degr´ e admet deux racines
dans le plan complexe” ne d´ efinit pas un algorithme, tandis que la formule
fournissant les racines est un algorithme (pourvu que les sous-algorithmes
requis pour l’ex´ ecution correcte de toutes les op´ erations aient ´ et´ e ´ egalement
d´ efinis).
Enfin, la complexit´ e d’un algorithme est une mesure de son temps d’ex´ ecution. Calculer la complexit´ e d’un algorithme fait donc partie de l’analyse de
l’efficacit´ e d’une m´ ethode num´ erique. Plusieurs algorithmes, de complexit´ es
diff´ erentes, peuvent ˆ etre employ´ es pour r´ esoudre un mˆ eme probl` eme P . On
introduit donc la notion de complexit´ e d’un probl` eme qui est d´ efinie comme la
complexit´ e de l’algorithme qui a la complexit´ e la plus petite parmi ceux qui
r´ esolvent P . La complexit´ e d’un probl` eme est typiquement mesur´ ee par un
param` etre directement associ´ e ` a P . Par exemple, dans le cas du produit de
deux matrices carr´ ees, la complexit´ e du calcul peut ˆ etre exprim´ ee en fonction
d’une puissance de la taille n de la matrice (voir [Str69]).
2.5 Repr´ esentation des nombres en machine
Toute op´ eration qu’effectue un ordinateur (“op´ eration machine”) est entach´ ee
par des erreurs d’arrondi. Elles sont dues au fait qu’on ne peut repr´ esenter
dans un ordinateur qu’un sous-ensemble fini de l’ensemble des nombres r´ eels.
Dans cette section, apr` es avoir rappel´ e la notation positionnelle des nombres
r´ eels, nous introduisons leur repr´ esentation machine.
2.5.1 Le syst` eme positionnel
Soit une base fix´ ee β ∈ N avec β ≥ 2, et soit x un nombre r´ eel comportant un
nombre fini de chiffres x k avec 0 ≤ x k < β pour k = −m, . . . , n. La notation
conventionnelle
x β = (−1)
s [x n x n−1 . . . x 1 x 0 .x −1 x −2 . . . x −m ] , x n = 0 ,
(2.26)
45
L’efficacit´ e signifie que la complexit´ e du calcul (c’est-` a-dire la quantit´ e
d’op´ erations et la taille de m´ emoire requise) n´ ecessaire pour maˆ ıtriser l’erreur
est aussi petite que possible.
Ayant rencontr´ e plusieurs fois dans cette section le terme algorithme, nous ne
pouvons nous dispenser de donner une description intuitive de ce dont il s’agit.
Par algorithme, nous entendons une d´ emarche qui d´ ecrit, ` a l’aide d’op´ erations
´ el´ ementaires, toutes les ´ etapes n´ ecessaires ` a la r´ esolution d’un probl` eme sp´ ecifique. Un algorithme peut `
a son tour contenir des sous-algorithmes. Il doit
avoir la propri´ et´ e de s’achever apr` es un nombre fini d’op´ erations ´ el´ ementaires.
Celui qui ex´ ecute l’algorithme (une machine ou un ˆ etre humain) doit y trouver
toutes les instructions pour r´ esoudre compl` etement le probl` eme consid´ er´ e (` a
condition que les ressources n´ ecessaires ` a son ex´ ecution soient disponibles).
Par exemple, l’assertion “un polynˆ ome du second degr´ e admet deux racines
dans le plan complexe” ne d´ efinit pas un algorithme, tandis que la formule
fournissant les racines est un algorithme (pourvu que les sous-algorithmes
requis pour l’ex´ ecution correcte de toutes les op´ erations aient ´ et´ e ´ egalement
d´ efinis).
Enfin, la complexit´ e d’un algorithme est une mesure de son temps d’ex´ ecution. Calculer la complexit´ e d’un algorithme fait donc partie de l’analyse de
l’efficacit´ e d’une m´ ethode num´ erique. Plusieurs algorithmes, de complexit´ es
diff´ erentes, peuvent ˆ etre employ´ es pour r´ esoudre un mˆ eme probl` eme P . On
introduit donc la notion de complexit´ e d’un probl` eme qui est d´ efinie comme la
complexit´ e de l’algorithme qui a la complexit´ e la plus petite parmi ceux qui
r´ esolvent P . La complexit´ e d’un probl` eme est typiquement mesur´ ee par un
param` etre directement associ´ e ` a P . Par exemple, dans le cas du produit de
deux matrices carr´ ees, la complexit´ e du calcul peut ˆ etre exprim´ ee en fonction
d’une puissance de la taille n de la matrice (voir [Str69]).
2.5 Repr´ esentation des nombres en machine
Toute op´ eration qu’effectue un ordinateur (“op´ eration machine”) est entach´ ee
par des erreurs d’arrondi. Elles sont dues au fait qu’on ne peut repr´ esenter
dans un ordinateur qu’un sous-ensemble fini de l’ensemble des nombres r´ eels.
Dans cette section, apr` es avoir rappel´ e la notation positionnelle des nombres
r´ eels, nous introduisons leur repr´ esentation machine.
2.5.1 Le syst` eme positionnel
Soit une base fix´ ee β ∈ N avec β ≥ 2, et soit x un nombre r´ eel comportant un
nombre fini de chiffres x k avec 0 ≤ x k < β pour k = −m, . . . , n. La notation
conventionnelle
x β = (−1)
s [x n x n−1 . . . x 1 x 0 .x −1 x −2 . . . x −m ] , x n = 0 ,
(2.26)