Notation mathématique et code

Ce qui suit s'adresse surtout aux programmeuses et programmeurs qui débutent et n'ont pas encore nécessairement fait de mathématiques post-secondaires. Pour les autres, c'est peut-être un peu léger (outre quelques trucs ici et là). Soyez-en averti(e)s!

Il arrive assez souvent, surtout au niveau collégial (et ça se comprend), qu'on me demande ce que signifient certaines notations mathématiques, et comment elles peuvent se traduire en code à proprement dit. Ce qui suit donne quelques exemples de traduction d'une notation à l'autre.

Les sommations

Un exemple typique est la sommation, par exemple $\sum\limits_{i=1}^{n}f(i)$ . Le sigma majuscule $\Sigma$ signifie en général somme, alors il faut alors voir dans cette écriture une répétitive avec variable de cumul, ou encore un cumul récursif. Il est fréquent qu'une variable soit utilisée pour marquer les valeurs qui nous intéressent (un compteur, en quelques sortes), et ces variables sont fréquemment nommées $i,j,k$.

Quand vous voyez $\sum\limits_{i=1}^{n}f(i)$ , ce qu'il faut comprendre est :

• Somme, manifestement
• Pour $i$ allant de $1$ à $n$ inclusivement
• Se la valeur résultant de l'évaluation de $f(i)$

Par exemple, si $f(i)=i$ (fonction identité), alors $\sum\limits_{i=1}^{n}f(i)$ correspond à $f(1)+f(2)+ \ldots +f(10)$ donc $1+2+ \ldots +10$ , donc $55$ . On pourrait alors simplement écrire $\sum\limits_{i=1}^{n}i$ pour exprimer la même chose.

En programmation

Prenant un exemple concret, et en évitant de se préoccuper de débordements ou d'erreurs (pour que le tout reste simple), on pourrait exprimer $\sum\limits_{i=1}^{n}i$ comme suit :

int somme_valeurs(int n) {
   int cumul = 0;
   for(int i = 1; i <= n; ++i)
      cumul += i;
   return cumul;
}

Notez que cumul a été initialisé à 0, qui la valeur neutre pour l'addition. Une écriture alternative avec fonction récursive serait :

int somme_valeurs(int n) {
   return n == 1? 1 : n + somme_valeurs(n-1);
}

Un mathématicien aurait probablement écrit quelque chose comme $f(n) = \left\{ \begin{array}{l l} 1 & \quad \text{si $n=1$}\\ n+f(n-1) & \quad \text{sinon}\\ \end{array} \right.$ ou simplement $f(n)=\sum\limits_{i=1}^{n}i$ bien entendu. C'est une écriture compacte et concise, qui fait abstraction des types de données dans bien des cas, et qui convient au travail des humains (pour un travail plus formel, il peut arriver que les types soient requis et que cette notation demande d'être enrichie).

Lorsque la valeur de $n$ est connue à la compilation, il est possible (en C++) d'évaluer la somme à la compilation, par récursivité; dans ce cas, la pile n'est pas sollicitée à l'exécution et le résultat est on ne peut plus efficace, étant calculé d'avance – au prix bien sûr d'une compilation plus lente, rien n'étant gratuit. Ceci peut se faire à l'aide de métaprogrammation à l'aide de templates :

template <int N>
   struct SommeValeurs {
      enum { value = N + SommeValeurs<N-1>::value };
   };
template <>
   struct SommeValeurs<1> {
      enum { value = 1 };
   };

...ou encore (depuis C++ 11) avec des expressions constantes généralisées :

constexpr int somme_valeurs(int n) {
   return n == 1? 1 : n + somme_valeurs(n-1);
}

Les deux versions métaprogrammées ci-dessus génèrent des constantes à la compilation lorsque la valeur de n (ou N) est elle-même connue à la compilation.

De manière générale, C++ offre un algorithme standard nommé std::accumulate(), de la bibliothèque <numeric>, qui exprime précisément la fonctionnalité d'une accumulation, par exemple une somme. La fonction accumulate() prend trois ou quatre paramètres, selon les cas d'utilisation, soit :

• Le début de la séquence source pour le cumul
• La fin de la séquence source pour le cumul
• La valeur initiale du cumul (typiquement, le neutre de l'opération utilisée, mais ça dépend des applications), et
• Lorsque l'opération d'accumulation n'est pas une somme, il est possible de suppléer une autre opération. Un exemple sera présenté un peu plus bas

Un exemple d'appel à accumulate() pour faire la somme des entiers de 1 à 10 inclusivement serait :

#include <numeric>
#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   int vals[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   cout << accumulate(begin(vals), end(vals), 0) << endl;
}

En utilisant un foncteur pour générer les valeurs, on obtiendrait quelque chose comme :

#include <numeric>
#include <iostream>
#include <iterator>
template <class T>
   class Sequence {
   public:
      using value_type = T;
      using pointer = T*;
      using reference = T&
      using difference_type = std::ptrdiff_t;
      using iterator_category = std::forward_iterator_tag;
   private:
      value_type cur_ {};
   public:
      Sequence() = default;
      Sequence(const value_type& init) : cur_{ init } {
      }
      value_type operator()() const {
         return cur_;
      }
      Sequence& operator++() {
         ++cur_;
         return *this;
      }
      Sequence operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      bool operator==(const Sequence &seq) const {
         return cur_ == seq.cur_;
      }
      bool operator!=(const Sequence &seq) const {
         return !(*this == seq);
      }
      value_type operator*() const {
         return cur_;
      }
   };
template <class T>
   Sequence<T> sequence(const T &val) {
      return { val };
   }
int main() {
   using namespace std;
   cout << accumulate(sequence(1), sequence(11), 0) << endl;
}

Notez ici que la fin est sequence(11), car sequence(10) fait partie de la séquence à couvrir.

accumulate(Sequence{ 1 }, Sequence{ 11 }, 0)

De prime abord, une sommation est de complexité linéaire $O(n)$ dans la mesure où l'opération à réaliser $n$ fois est de complexité linéaire. Ainsi, la complexité de $\sum\limits_{i=1}^{n}f(i)$ sera $O(n \times O(f))$ en écrivant $O(f)$ la complexité algorithmique de $f$ bien entendu. D'ailleurs, cette dernière sommation s'exprimerait, avec une λ, de la manière suivante :

#include <numeric>
#include <algorithm>
int f(int); // peu importe sa définition
int main() {
   using namespace std;
   int vals[] = { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, [](int so_far, int i) {
      return so_far + f(i);
   });
   // ... etc.
}

Comme on peut le voir, le quatrième paramètre passé à accumulate() est une fonction binaire recevant la valeur du cumul jusque là, la nouvelle valeur à accumuler, et retournant le résultat d'une étape du cumul (un cumul partiel).

Par défaut, l'opération reçoit a et b et retourne a+b, sans plus. On pourrait expliciter ce fait ainsi, avec une fonction :

#include <numeric>
#include <algorithm>
int somme(int a, int b) {
   return a + b;
}
int main() {
   using namespace std;
   int vals[] { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, somme);
   // ... etc.
}

... ou avec un foncteur :

#include <numeric>
#include <algorithm>
struct Somme {
   int operator()(int a, int b) const {
      return a + b;
   }
};
int main() {
   using namespace std;
   int vals[] = { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, Somme{});
   // ... etc.
}

...qui pourrait avantageusement être générique, d'ailleurs, et s'appliquer à une plus grande classe de problèmes :

#include <numeric>
#include <algorithm>
struct Somme {
   template <class T>
      T operator()(const T &a, const T &b) const {
         return a + b;
      }
};
int main() {
   using namespace std;
   int vals[] { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, Somme{});
   // ... etc.
}

...ou encore avec une λ :

#include <numeric>
#include <algorithm>
int f(int); // peu importe sa définition
int main() {
   using namespace std;
   int vals[] = { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, [](int a, int b) {
      return a + b;
   });
   // ... etc.
}

...mais en général, on utilisera ici le comportement par défaut (pourquoi refaire ce qui fonctionne déjà?).

Les produits

Les accumulations ne se limitent pas aux sommes. Une autre forme d'accumulation qui est souvent rencontrée en pratique, suffisamment pour mériter sa propre notation, est le produit. La notation mathématique est d'exprimer le produit de $f(i)$ pour $i$ allant de $1$ à $n$ inclusivement sous la forme $\prod\limits_{i=1}^{n}f(i)$ . La factorielle de $n$, ou $n!$, peut donc s'exprimer comme $\prod\limits_{i=1}^{n}i$ .

Les éléments de la notation d'un produit sont les mêmes que ceux d'une somme. Conséquemment, référez-vous à cette section pour des détails.

En programmation

Tout comme dans le cas d'une somme, il est possible d'exprimer un produit comme une répétitive. Prenant un exemple concret, et en évitant de se préoccuper de débordements ou d'erreurs (pour que le tout reste simple), on pourrait exprimer $\prod\limits_{i=1}^{n}i$ comme suit :

int produit_valeurs(int n) {
   int cumul = 1;
   for(int i = 1; i <= n; ++i)
      cumul *= i;
   return cumul;
}

Notez que cumul a été initialisé à 1, qui la valeur neutre pour la multiplication. Une écriture alternative avec fonction récursive serait :

int produit_valeurs(int n) {
   return n == 1? 1 : n * produit_valeurs(n-1);
}

Les remarques sur la récursivité dans les langages impératifs, présentées plus haut, s'appliquent ici aussi.

Un mathématicien aurait probablement écrit quelque chose comme $f(n) = \left\{ \begin{array}{l l} 1 & \quad \text{si $n=1$}\\ n \times f(n-1) & \quad \text{sinon}\\ \end{array} \right.$ ou simplement $f(n)=\prod\limits_{i=1}^{n}i$ bien entendu.

Lorsque la valeur de $n$ est connue à la compilation, il est possible (en C++) d'évaluer la somme à la compilation, par récursivité. Ceci peut se faire à l'aide de métaprogrammation à l'aide de templates :

template <int N>
   struct ProduitValeurs {
      enum { value = N * ProduitValeurs<N-1>::value };
   };
template <>
   struct ProduitValeurs<1> {
      enum { value = 1 };
   };

...ou encore (depuis C++ 11) avec des expressions constantes généralisées :

constexpr int produit_valeurs(int n) {
   return n == 1? 1 : n * produit_valeurs(n-1);
}

Les deux versions métaprogrammées ci-dessus génèrent des constantes à la compilation lorsque la valeur de n (ou N) est elle-même connue à la compilation.

L'algorithme standard std::accumulate(), peut être utilisé ici aussi. Un exemple d'appel à accumulate() pour faire le produit des entiers de 1 à 10 inclusivement serait, avec une λ :

#include <numeric>
#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   int vals[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   cout << accumulate(begin(vals), end(vals), 1, [](int a, int b) {
      return a * b;
   }) << endl;
}

En utilisant un foncteur comme Sequence (plus haut) pour générer les valeurs, on obtiendrait quelque chose comme :

#include <numeric>
#include <iostream>
// ...
int main() {
   using namespace std;
   cout << accumulate(sequence(1), sequence(11), 1, [](int a, int b) {
      return a * b;
   }) << endl;
   // ... ou encore, si vous utilisez CTAD...
   cout << accumulate(Sequence{ 1 }, Sequence{ 11 }, 1, [](int a, int b) {
      return a * b;
   }) << endl;
}

Notez ici que la fin est sequence(11) car sequence(10) fait partie de la séquence à couvrir.

De manière générale, une produit est de complexité linéaire, $O(n)$, dans la mesure où l'opération à réaliser $n$ fois est de complexité linéaire. Ainsi, la complexité de $\prod\limits_{i=1}^{n}f(i)$ sera $O(n \times O(f))$ avec $O(f)$ la complexité de la fonction $f$ bien sûr. D'ailleurs, cette dernière sommation s'exprimerait, avec une λ, de la manière suivante :

#include <numeric>
#include <algorithm>
int f(int); // peu importe sa définition
int main() {
   using namespace std;
   int vals[] { 1,2,3,4,5,6,7,8,9,10 }; // par exemple
   int res = accumulate(begin(vals), end(vals), 0, [](int so_far, int i) {
      return so_far * f(i);
   });
   // ... etc.
}

Autres accumulations

Il existe d'autres accumulations amusantes à évaluer. Les expressions mathématiques usuelles suivent; à titre d'exercice, essayez de les exprimer par des répétitives ou (mieux!) par des appels à accumulate(). Ci-dessous, considérez $v$ comme étant un tableau et $n$ comme étant le nombre de ses éléments (j'ai pris la notation C où les indices vont de $0$ à $n-1$ inclusivement).

Évidemment, il existe habituellement des algorithmes standards pour les calculs les plus usités (dont ceux proposés ici). Ainsi, bien qu'il soit instructif de réaliser ces exercices, je vous invite fortement à lire la documentation de vos outils de prédilection et de privilégier les outils standards dans la mesure du possible (par exemple, avec la bibliothèque standard, il existe un algorithme nommé std::min_element() qui sera probablement plus efficace que votre version « maison » d'un algorithme identifiant la valeur minimale d'une séquence).

Notations non-indicées

Il arrivera aussi fréquemment que l'on voit apparaître en notation mathématique une écriture sans indice telle que $f(S)=\bigcup\limits_{e \in S}f(e)$ . On lira alors « union ensembliste de $f(e)$ pour tous les éléments $e$ pris de l'ensemble $S$ ». Ici, traiter $S$ comme un ensemble (ou une collection, au sens plus large) est un raccourci, et tout conteneur dont il est possible de parcourir les éléments un à un ferait l'affaire.

Pour traduire cette écriture en code, en supposant (pour simplifier l'explication, car on pourrait aller très loin dans la généralisation et l'abstraction ici) que l'on opère sur un std::vector<T> en entrée, qu'on retourne un std::vector<T> en sortie, et que F prenne en paramètre un T et retourne un T, on pourrait écrire ceci :

#include <numeric>
#include <algorithm>
template <class T, class F>
   std::vector<T> union_resultats(const std::vector<T> &v, F f) {
      using namespace std;
      return accumulate(begin(v), end(v), vector<T>{}, [&](vector<T> w, T &&elem) {
         if (find(begin(w), end(w), elem) == end(w))
            w.emplace_back(elem);
         return w;
      });
   }

Notez que, puisque nous représentons ici une union ensembliste, nous nous assurons à chaque insertion de ne pas créer de duplicats. Il existe des conteneurs (std::set, en particulier) pour lesquels ce comportement est implicite.

Lectures complémentaires

Quelques liens pour enrichir le propos.

• Pour des conseils de programmation dite « scientifique » sous Linux, un texte de 2013 : http://functionspace.org/articles/4/Getting-started-with-Scientific-Programming
• En 2014, Marius Bancila décrit les principaux algorithmes de <numeric> : http://codexpert.ro/blog/2014/04/18/generic-numeric-algorithms-in-header-numeric/
• Depuis C++ 11, plus besoin de calculer « manuellement » la distance euclidienne $\sqrt{x^2+y^2}$entre deux nombres, en risquant de mal gérer les cas de débordements, car la fonction std::hypot() fait maintenant partie du standard. À ce sujet, voir ce texte de 2014 : http://cpp.indi.frih.net/blog/2014/08/tippet-no-need-to-square-sum-and-sqrt-manually-anymore/
• Notation mathématique et code Python, par Amit Chaudhary en 2019 : https://amitness.com/2019/08/math-for-programmers/