Semianneau (encyclopédie mathématiques)

Ne doit pas être confondu avec semi-anneau d'ensembles.

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: contrairement à ce qui se passe avec les anneaux, on ne peut démontrer à partir des autres axiomes que 0 est un élément absorbant.

[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.
Les dioïdes sont des semi-anneaux particuliers.

[modifier] Bibliographie

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)

Semianneau

[modifier] Domaines de prédilection

[modifier] Exemples

[modifier] Bibliographie

Rechercher

Menu

Espace membre

Changer d'île