Semianneau

Semianneau : encyclopédie mathématiques

Cet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.

Aller à : Navigation, Rechercher

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, un semi-anneau, ou un demi-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.

Remarque: un anneau se construit de façon similaire à partir d'un groupe additif et d'un monoïde multiplicatif mais il n'a pas besoin du dernier axiome car l'absorption du zéro se déduit de l'inversibilité de la somme.

[modifier] Domaines de prédilection

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.

[modifier] Exemples

Le demi-anneau le plus simple est celui des booléens: $(\{0, 1\}, \vee, \wedge, 0, 1)$ où $\vee$ et $\wedge$ sont OU et ET respectivement.
Le plus naturel est peut-être celui des entiers positifs 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; 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 semi-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 semi-anneau.