A quoi servent les groupes, les monoïdes et les anneaux dans les calculs de base de données?

Pourquoi une entreprise comme Twitter serait-elle intéressée par les concepts algébriques tels que les groupes, les monoïdes et les anneaux? Voir leur dépôt sur github: twitter / algebird .

Tout ce que j'ai pu trouver c'est:

Implémentations de Monoids pour des algorithmes d'approximation intéressants, tels que le filtre de Bloom , HyperLogLog et CountMinSketch . Celles-ci vous permettent de penser à ces opérations sophistiquées, comme les nombres, et de les additionner dans hadoop ou en ligne pour produire des statistiques et des analyses puissantes.

et dans une autre partie de la page GitHub:

Il a été développé à l'origine dans le cadre de l'API matricielle de Scalding, dans laquelle les matrices avaient des valeurs qui étaient des éléments de monoïdes , de groupes ou de bagues . Par la suite, il était clair que le code avait une application plus large dans Scalding et sur d’autres projets sur Twitter.

Quelle pourrait être cette application plus large? sur Twitter et pour l'intérêt général?

Il semble que les agrégations de composition de bases de données aient une structure monoïde.

Même question sur Quora: quel est l'intérêt de Twitter pour l'algèbre abstraite (avec algebird)?

J'ai des antécédents en mathématiques mais je ne suis pas informaticien. Il serait bon d’avoir des utilisations «réelles» de monoïdes et de semi-groupes. Celles-ci sont normalement considérées comme des constructions théoriques inutiles et sont ignorées dans de nombreux cours d'algèbre abstraite (faute de quelque chose d'intéressant à dire).

La réponse principale est qu’en exploitant la structure de semi-groupes, nous pouvons construire des systèmes qui parallélisent correctement sans connaître l’opération sous-jacente (l’utilisateur promet une associativité).

En utilisant Monoids, nous pouvons tirer parti de la clarté (nous traitons beaucoup de matrices clairsemées, où presque toutes les valeurs sont égales à zéro dans certains Monoid).

En utilisant les anneaux, nous pouvons faire la multiplication de matrice sur des choses autres que des nombres (ce que nous avons fait à l'occasion).

Le projet algebird lui-même (ainsi que l'historique des problèmes) explique assez clairement ce qui se passe ici: nous construisons de nombreux algorithmes pour l'agrégation de grands ensembles de données, et l'exploitation de la structure des opérations nous permet de gagner du côté des systèmes. (ce qui est généralement le problème lorsque vous essayez de produire des algorithmes sur des milliers de nœuds).

Résolvez les problèmes de système une fois pour chaque semigroupe / monoïde / groupe / sonnerie et vous pourrez ensuite brancher n'importe quel algorithme sans avoir à penser à Memcache, Hadoop, Storm, etc.

Les monoïdes sont omniprésents dans la programmation, mais la plupart des programmeurs ne les connaissent pas.

• Opérations numériques telles que l'addition et la multiplication.
• Multiplication matricielle.
• Fondamentalement, toutes les structures de données de type collection forment des monoïdes, où l'opération monoïdale est une concaténation ou une union. Cela inclut des listes, des ensembles, des cartes de clés de valeurs, divers types d’arbres, etc.
• $A$$A\to A$$A$$A$

$a\cdot b$$a$$b$

Comme les monoïdes sont si généraux, ils permettent d’écrire des fonctions très génériques. Par exemple, le repliement d'une structure de données peut être exprimé en tant que mappage de chacun de ses éléments sur un monoïde, puis en utilisant l'opération monoïdale pour les combiner en un seul résultat.

$\underbrace{a\cdot\ldots\cdot a}_{n-\mbox{times}}$$O(\log n)$

• exponentiation rapide des nombres;
• $O(\log n)$
• $O(1)$$O(\log(\min(n_1,n_2)))$
• etc.

Pour plus d'exemples, voir Exemples de monoids / semigroupes en programmation .

Un problème important dans les systèmes de fichiers distribués ( DFS ) est de générer des fichiers à partir de blocs distribués. La zone du code d'effacement de la théorie de l'information et de l'algèbre (groupes, anneaux, algèbre linéaire, ...) est largement utilisée dans les systèmes de fichiers distribués à tolérance de pannes, par exemple dans le système de stockage HDFS RAID (Hadoop Based File System). Les entreprises de réseaux sociaux et de cloud reposent largement sur DFS. Elles ont donc besoin de personnes maîtrisant parfaitement l'algèbre et Erasure Code pour concevoir des systèmes plus performants et performants (comme les codes de Reed-Solomon , etc.).

C'est aussi une bonne affiche pour leur application (algèbre) dans le stockage en nuage: Nouveaux codes pour le stockage en nuage

Si votre question est

Quels sont des exemples de groupes, monoïdes et anneaux dans le calcul?

$+$$\min$$\cdot$$+$

Bien que cela puisse paraître théorique d'un point de vue algébrique, cela nous permet d'utiliser des bibliothèques d'algèbre linéaire très fortement optimisées pour les problèmes de graphes. BLAS combinatoire est une de ces bibliothèques.

L'ensemble des mots sur un alphabet fini ainsi que la concaténation forment le monoïde libre . Par conséquent, le champ entier du langage formel peut être vu à travers la lentille algébrique, et il est parfois enseigné de la sorte.$(\Sigma^*, \cdot)$

En contrepartie, des considérations sur les langages formels ont donné l’ analyseur Earley qui peut être étendu pour analyser des semirings . Ceci est utile dans le traitement du langage naturel et d'autres domaines utilisant des modèles stochastiques pour les langues (formelles).

J'ai des antécédents en mathématiques, mais je ne suis pas informaticien. Il serait bon d’avoir des utilisations «réelles» de monoïdes et de semi-groupes. Celles-ci sont normalement considérées comme des constructions théoriques inutiles et sont ignorées dans de nombreux cours d'algèbre abstraite (faute de quoi dire d'intéressant).

Il y a trop trop intéressant à dire. Cependant, il s'agit davantage d'un sujet de mathématiques et de combinatoire discrètes que d'algèbre abstraite et d'analyse, du moins pour les sujets moins triviaux. Il y a aussi la question de savoir combien vous devez savoir sur un certain sujet avant de pouvoir dire à quelqu'un d'autre que ce serait un sujet mathématique intéressant lié aux monoïdes et aux semi-groupes. Par exemple, je trouve les sujets suivants (liés aux semigroupes) intéressants:

• semigroupes finis et théorie de Krohn-Rhodes
• symétries partielles, semi-groupes inverses, groupoïdes et quasi-cristaux
• semirings et géométrie tropicale
• commandes partielles et fonctions Möbius
• fonctions sous-modulaires et décompositions (de type Dulmage-Mendelsohn)

Est-ce que j'en sais beaucoup sur chacun de ces sujets? Probablement pas. Il y a aussi beaucoup plus de sujets mathématiques liés aux monoïdes et aux semi-groupes, dont certains sont plus internes à la théorie même des semi-groupes (comme les relations de Green), d'autres sont plus généraux et ne sont pas spécifiques aux semi-groupes (semi-groupes universels, théorèmes d'homomorphisme et d'isomorphisme, structures de quotient congruences), mais aussi important d’un point de vue mathématique. Les sujets que j'ai cités ci-dessus ont pour la plupart des applications «réelles», mais il existe d'autres sujets connexes qui ont également des applications «réelles».

Ce qui précède n’est pas une réponse à la vraie question, mais seulement l’adresse "... sont normalement considérés comme des constructions théoriques inutiles ... par manque de tout élément intéressant à dire ...". Alors, j'ai énuméré quelques points "intéressants", affirmé que ceux-ci ont principalement des applications "réelles", et maintenant, Hi-Angel demande un peu d'informations sur ces applications. Mais comme "il y a un peu trop d'intéressant à dire", n'attendez pas trop de cette information: le théorème de Krohn-Rhodes est un théorème de décomposition pour les semi-groupes finis. Ses applications impliquent l'interprétation du produit sous forme de couronne comme une sorte de composition (de transducteurs) en relation avec la théorie des automates et des langages normaux,Mark V Lawson: deux cours magistraux et des documents de base contenaient (404 maintenant) de bons documents sur les semigroupes inverses . La base de leurs applications est leur connexion au semi - groupe inverse symétrique , c’est-à-dire à l’ensemble des bijections partielles d’un ensemble. On peut aussi commencer par les caractérisations algébriques de base des semi-groupes inverses, mais cette approche risque de négliger les connexions aux ordres partiels qui sont importants pour de nombreuses applications. Un jour, je devrai bloguer à propos d'une application spécifique des semi-groupes inverses en tant que "hiérarchie" utilisée pour compresser les mises en page de semi-conducteurs. Des applications de semirings ont déjà été décrites dans les autres réponses (et la géométrie tropicale nous mènerait loin de l'informatique). Comme les monoïdes et les semi-groupes sont également liés aux commandes partielles, des sujets aussi intéressants que les fonctions de Möbius décrites dans Combinatorics: The Rota Way sont également liés. Et puis, des sujets comme Matrix et Matroids for System Analysis, comme la décomposition de Dulmage-Mendelsohn, deviennent liés, ce qui était l'une de mes motivations pour étudier la théorie du réseau (et les structures hiérarchiques cachées).