Demi-anneau

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Semi-anneau)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec semi-anneau d'ensembles.

En mathématiques, un demi-anneau, ou un semi-anneau, est une structure algébrique (E, +, \times, 0, 1) telle que

  • (E, +, 0) constitue un monoïde commutatif;
  • (E, \times, 1) forme un monoïde;
  • \times est distributif par rapport à +;
  • 0 est absorbant pour le produit, autrement dit: pour tout x \in E : x \times 0 = 0 \times x = 0.

Un demi-anneau est commutatif quand son produit est commutatif. Parfois on distingue les demi-anneaux et les demi-anneaux unifères : dans ce cas, la structure multiplicative n'est qu'un demi-groupe, donc ne possède pas nécessairement un élément neutre. En général, on demande aussi que 0\ne1.

Remarque: contrairement à ce qui se passe avec les anneaux, on ne peut démontrer à partir des autres axiomes que 0 est un élément absorbant.

Domaines de prédilection[modifier | modifier le code]

Les demi-anneaux se retrouvent souvent en :

  • recherche opérationnelle : les graphes ont des poids dans un demi-anneau ; le produit est associé à l'accumulation de valeur le long d'un chemin et la somme correspond à la façon de composer plusieurs chemins ;
  • théorie des langages et des automates : la concaténation des (ensembles de) chaînes pour en fabriquer d'autres est le produit et l'union des (ensembles de) chaînes est la somme.

Exemples[modifier | modifier le code]

  • Le demi-anneau le plus simple est celui de l'algèbre de Boole : (\{0, 1\}, \vee, \wedge, 0, 1)\vee et \wedge sont OU et ET respectivement.
  • Le plus naturel est peut-être celui des entiers naturels avec l'addition et la multiplication: (\mathbb{N}, +, \times, 0, 1).
  • L'ensemble des entiers naturels étendu à \infty de façon habituelle (toute somme avec \infty donne \infty ; tout produit avec \infty donne \infty, sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: (\mathbb{N} \cup \{\infty\}, \min, +, \infty, 0) est connu sous le nom de demi-anneau tropical nommé ainsi en l'honneur de son promoteur Imre Simon; il est au cœur des algorithmes de calcul de plus court chemin dans un graphe : les poids sont additionnés le long des chemins et devant plusieurs chemins, on prend le coût minimal.
  • (\mathbb{N} \cup \{\infty\}, \max, \min, 0, \infty) est le demi-anneau sous-jacent au calcul du flux maximum d'un graphe: dans une séquence d'arcs, celui de poids minimal impose son flux et devant plusieurs séquences, on prend le flux maximal.
  • L'ensemble des parties d'un ensemble E muni de l'union et de l'intersection est un demi-anneau. Les deux lois sont distributives l'une par rapport à l'autre, l'élément neutre de l'union est l'ensemble vide, celui de l'intersection est l'ensemble E. Les deux lois sont commutatives et forment avec E les deux monoïdes requis. C'est une algèbre de Boole et donc un treillis.
  • Tout treillis distributif est un demi-anneau.
  • Les dioïdes sont des demi-anneaux particuliers.

Bibliographie[modifier | modifier le code]

  • Michel Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux, Paris, Lavoisier Tec et Doc,‎ 2002, 414 p. (ISBN 978-2-7430-0489-7)