Sommes courantes en informatique

Somme de Gauss : 1 + 2 + 3 + … + n #

La somme

1 + 2 + 3 + … + n

Simplifie à

n(n+1) / 2.

Notez que cette quantité est Θ(n²).

Ce raccourci apparaît fréquemment dans [l’analyse d’algorithmes][1] comme le tri par insertion ou le tri par sélection.

Les nombres de la forme n(n+1)/2 sont appelés [les nombres triangulaires][2].

[1] : https://www.wikiod.com/fr/algorithm/debuter-avec-lalgorithme [2] : https://en.wikipedia.org/wiki/Triangular_number

Somme d’une suite géométrique : r^0 + r^1 + r^2 + … #

La somme de la série géométrique

r⁰ + r¹ + r² + … + r^n-1

Dans le cas où r ≠ 1, se simplifie en (rⁿ - 1) / (r - 1). Si r < 1, cette somme est bornée par le haut par 1 / (1 - r).

Si r = 1, cette somme est rn.

Sommes de nombres de Fibonacci #

Les nombres de Fibonacci sont définis de manière inductive comme

• F₀ = 0
• F₁ = 1
• F_n+2 = F_n + F_n+1

La somme des n+1 premiers nombres de Fibonacci est donnée par

F₀ + F₁ + F₂ + … + F_n = F_{n +2} - 1.

Cette sommation apparaît, entre autres, dans l’analyse des tas de Fibonacci, où elle est utilisée pour fournir une limite inférieure sur le nombre de nœuds dans chaque arbre du tas.

Sommes des Puissances de Deux : 1 + 2 + 4 + 8 + 16 + … #

La somme

2⁰ + 2¹ + 2² + … + 2^n-1

se simplifie en 2ⁿ - 1. Cela explique pourquoi la valeur maximale pouvant être stockée dans un entier 32 bits non signé est 2³² - 1.

Sommes des poteaux de clôture #

On considère ici des sommes de la forme

une + b + une + b + … une

contre.

une + b + une + b + … b

Pour visualiser ces sommes, imaginez un tronçon de clôture alternant poteaux et lisses. Trois scénarios sont possibles.

1. Imaginez une section de clôture avec des poteaux à chaque extrémité, reliés par des rails. n rails nécessitent n+1 poteaux. A l’inverse p poteaux sont reliés par p-1 rails.

   |—|—|—|

2. Imaginez une section de clôture avec un poteau à une extrémité, mais un rail ouvert à l’autre. n rails nécessitent n poteaux.

   |—|—|—

   or

   —|—|—|

3. Imaginez une section de clôture avec des rails ouverts aux deux extrémités. n rails nécessitent n-1 poteaux. A l’inverse, p poteaux sont reliés par p+1 rails.

   —|—|—

Des calculs comme celui-ci surviennent dans des situations telles que la mise en page d’objets graphiques où les tailles des objets doivent être additionnées et les espaces entre les objets doivent également être additionnés. Dans de telles situations, il est important de savoir si l’intention est ou non d’avoir des espaces à chaque extrémité.

La largeur totale d’une telle clôture sera toujours:

(largeur du poteau) x (nombre de poteaux) + (largeur du rail) x (nombre de rails)

Mais il faut faire preuve de prudence dans le calcul du nombre de poteaux et du nombre de rails afin d’éviter une erreur dite off-by-one. Les erreurs de ce genre sont courantes.

Sommes des réciproques : 1/1 + 1/2 + 1/3 + 1/4 + … #

La sommation

1/1 + 1/2 + 1/3 + 1/4 + … + 1/n

est égal au nième [numéro harmonique][1], noté H_n. Le nième nombre harmonique obéit aux inégalités

ln ( n + 1 ) & et ; H<s_o &le ; ( ln n ) +

et donc H_n = Θ(log n). Les nombres harmoniques apparaissent souvent dans l’analyse des algorithmes, le tri rapide aléatoire étant un exemple particulièrement intéressant.

[1] : https://en.wikipedia.org/wiki/Harmonic_number

Sommes des carrés réciproques : 1/1 + 1/4 + 1/9 + 1/16 + 1/25 + … #

La sommation

1/1 + 1/4 + 1/9 + 1/16 + …

vers l’infini converge vers π² / 6, et donc toute sommation de la forme

1/1 + 1/4 + 1/9 + 1/16 + … + 1/n²

est &Thêta;(1).