Usages des structures algébriques en informatique théorique

67

Je suis un praticien en logiciel et j'écris une étude sur les structures algébriques à des fins de recherche personnelle et j'essaie de produire des exemples d'utilisation de ces structures en informatique théorique (et, dans une moindre mesure, dans d'autres sous-domaines de l'informatique). .

Sous la théorie des groupes, j'ai rencontré des monoïdes syntaxiques pour les langages formels et des monoïdes de trace et d'historique pour l'informatique parallèle / simultanée.

Du point de vue de la théorie des anneaux, je suis tombé sur des cadres de semiring pour le traitement de graphes et l’analyse basée sur le semiring.

Je n'ai pas encore trouvé d'utilisation de structures algébriques à partir de la théorie des modules dans mes recherches (et j'aimerais le faire).

Je suppose qu'il existe d'autres exemples et que je ne cherche tout simplement pas le bon endroit pour les trouver.

Quels sont d'autres exemples de structures algébriques des domaines énumérés ci-dessus que l'on trouve couramment en informatique théorique (et dans d'autres sous-domaines de l'informatique)? Sinon, quelles revues ou autres ressources pouvez-vous recommander qui pourraient couvrir ces sujets?

GEL
la source
12
Cela semble plutôt vaste. Toutes sortes de structures algébriques (groupes, anneaux, semirings, semigroupes, champs) apparaissent en informatique théorique, et il est suffisamment répandu pour que vous ayez du mal à trouver un sous-composant spécifique. N'oubliez pas non plus les champs finis pour le hachage et de nombreuses autres méthodes de prise d'empreinte aléatoire.
Suresh Venkat
3
Peut-être que tout ce qui peut être représentable a une utilisation en informatique!
vs

Réponses:

46

Mon impression est que, dans l'ensemble, l'algèbre traditionnelle est un peu trop spécifique pour être utilisée en informatique. Les informaticiens utilisent donc soit des structures plus faibles (et donc plus générales), soit généralisent les structures traditionnelles afin de les adapter à leurs besoins. Nous utilisons également beaucoup la théorie des catégories, que les mathématiciens ne considèrent pas comme faisant partie de l’algèbre, mais nous ne voyons pas pourquoi. Nous trouvons que la réglementation des mathématiques traditionnelles en "algèbre" et en "topologie" comme des branches séparées est gênante, voire inutile, car l'algèbre est généralement du premier ordre alors que la topologie a une chance de traiter des aspects d'ordre supérieur. Ainsi, les structures utilisées en informatique ont une algèbre et une topologie mélangées. En fait, je dirais qu'elles tendent davantage vers la topologie que l'algèbre. L'intégration du raisonnement en "algèbre" et en "logique" est une autre division inutile de notre point de vue, car l'algèbre traite des propriétés équationnelles alors que la logique traite également de tous les autres types de propriétés.

Pour revenir à votre question, les semi-groupes et les monoïdes sont utilisés assez intensément dans la théorie des automates. Eilenberg a écrit une collection en deux volumes , dont le second est presque entièrement en algèbre. On me dit qu'il prévoyait quatre volumes mais son âge ne permettait pas de terminer le projet. Jean-Eric Pin dispose d'une version modernisée d'une grande partie de ce contenu dans un livre en ligne . Les automates sont des "modules monoïdes" (également appelés actions monoïdes ou "actes"), qui se situent au bon niveau de généralité en informatique. Les modules en anneau traditionnels sont probablement trop spécifiques.

La théorie du réseau était une force majeure dans le développement de la sémantique dénotationnelle. La topologie a été mélangée à la théorie du réseau lorsque des informaticiens, conjointement avec des mathématiciens, ont développé des réseaux continus puis les ont généralisés à des domaines . Je dirais que la théorie des domaines est la propre mathématique de l'informaticien, à laquelle les mathématiques traditionnelles n'ont aucune connaissance.

L'algèbre universelle est utilisée pour définir les spécifications algébriques des types de données . Une fois arrivés là-bas, les informaticiens ont immédiatement constaté la nécessité de traiter des propriétés plus générales: les équations conditionnelles (également appelées clauses de Horn équationnelles) et les propriétés logiques du premier ordre, en utilisant toujours les mêmes idées d’algèbre universelle. Comme vous le remarquerez, l'algèbre se fond maintenant dans la théorie des modèles.

La théorie des catégories est la base de la théorie des types. Alors que les informaticiens inventent sans cesse de nouvelles structures pour traiter divers phénomènes informatiques, la théorie des catégories est un cadre très réconfortant dans lequel placer toutes ces idées. Nous utilisons également des structures activées par la théorie des catégories, qui n'existent pas dans les mathématiques "traditionnelles", telles que les catégories de foncteurs. En outre, l'algèbre revient dans l'image d'un point de vue catégorique sur l'utilisation des monades et des théories algébriques des effets . Les coalgebras , qui sont les duals des algèbres, trouvent également beaucoup d'applications.

Ainsi, il existe une vaste application de "l'algèbre" en informatique, mais ce n'est pas le genre d'algèbre que l'on trouve dans les manuels d'algèbre traditionnels.

Note complémentaire : Il existe un sens concret dans lequel la théorie des catégories est algèbre. Le monoïde est une structure fondamentale en algèbre. Il consiste en un opérateur de "multiplication" binaire, associatif et ayant une identité. La théorie des catégories généralise ce en associant « types » aux éléments du monoïde, . Vous pouvez "multiplier" les éléments que lorsque les types correspondent: si un : X Y et b : Y Z puis un b : X Z . Par exemple, n × nune:XYune:XYb:YZuneb:XZn×nles matrices ont une opération de multiplication qui en fait un monoïde. Cependant, les matrices (où m et n peuvent être différents) forment une catégorie. Les monoïdes sont donc des cas particuliers de catégories qui ont un seul type. Les anneaux sont des cas spéciaux de catégories additives qui ont un seul type. Les modules sont des cas spéciaux de foncteurs où les catégories source et cible ont un type unique. Bientôt. La théorie des catégories est une algèbre typée dont les types la rendent infiniment plus applicable que l'algèbre traditionnelle.m×nmn

Uday Reddy
la source
24
Les théoriciens des catégories considèrent l'algèbre comme faisant partie de la théorie des catégories. Les algébristes pensent que la théorie des catégories fait partie de l'algèbre. Les logiciens pensent qu'ils sont tous les deux fous.
Jeff E
4
il y a beaucoup d'interaction entre la topologie et l'algèbre en mathématiques pures ...
Sasho Nikolov
16
C'est une bonne réponse, mais je pense que vos commentaires sur "la réglementation" et la "culture en silo" sont trompeurs. La raison pour laquelle algèbre, topologie et logique vous semblent unifiées est que, pour les questions qui vous intéressent , les parties de ces sujets qui vous concernent sont très étroitement liées. Mais si, par exemple, vous essayiez de classer des variétés à 4 dimensions sur des nombres complexes, vous percevriez rapidement l'utilité des distinctions traditionnelles établies par les mathématiciens. Tout dépend du problème que vous essayez de résoudre.
Timothy Chow
3
Personnellement, je suis toujours totalement perplexe devant à peu près n'importe quelle inférence de votre culture de la recherche en mathématiques et en informatique. Comme @TimothyChow l'a fait remarquer, différents sous-champs ont été développés pour traiter différents types de problèmes et, par conséquent, différents outils ont été développés. Là où il est judicieux d’apporter des outils de différents sous-domaines, et les gens l’ont compris, il y a interaction. Il ne devrait pas être difficile de trouver des exemples, par exemple dans des notes de cours sur l’algèbre des mensonges.
Sasho Nikolov
3
en ce qui concerne l'informatique, il y aurait moins de silo. Personnellement, je ne sais pas pourquoi les chercheurs en PL ont besoin de toute cette machinerie lourde, à quoi ils servent, quel problème ils résolvent avec, et pourquoi devrais-je m'en soucier? C’est peut-être ma propre ignorance, mais je doute que la plupart des théoriciens de la complexité et des algorithmiques connaissent les réponses à ces questions ...
Sasho Nikolov
23

Mon application préférée de la théorie des groupes dans TCS est le théorème de Barrington. Vous pouvez trouver une exposition de ce théorème sur le blog de la complexité et l'exposition de Barrington dans la section commentaires de cet article.

Dai Le
la source
2
+1: et beaucoup le considèrent comme l’un des résultats les plus surprenants de la théorie de la complexité. :)
Kaveh
15

Les groupes, les anneaux, les champs et les modules sont omniprésents dans la topologie informatique. Voir en particulier le travail [ex: 1 ] de Carlsson et Zomorodian sur l'homologie persistante (multidimensionnelle), qui consiste à définir des modules gradués sur des domaines idéaux principaux.

Jeffε
la source
@JeffE, liens, s'il vous plaît.
Scaaahu
1
@ Jeffe, mon commentaire n'était pas destiné à être offensant. Oui, je sais comment Google. Mon point était: y at-il un article particulier écrit par Carlsson et Zomorodian, qui serait en quelque sorte une vue d’ensemble de l’homologie persistante? S'il y en a un, merci de nous le faire savoir. Merci.
scaaahu
Je suggère de commencer avec cet article . (Désolé, mon commentaire précédent n'était pas appelé.)
Jeffε
@JeffE, compris, exactement ce que je cherchais. Merci.
Scaaahu
14

Voici une très belle utilisation pratique: un algorithme de calcul de la connectivité graphique (tiré de FOCS2011 ). Pour calculer la connectivité s-> t d'un graphe, les auteurs proposent un algorithme qui assigne des vecteurs aléatoires avec des entrées tirées d'un champ fini aux arêtes de s, puis construit des vecteurs similaires pour toutes les arêtes du graphe en prenant des variables aléatoires. combinaisons linéaires, et enfin découvrir la connectivité en calculant le rang des vecteurs résultants assignés aux bords de t.

Aaron Roth
la source
Merci pour le pointeur et la vue d'ensemble! C'était de FOCS 2011: dx.doi.org/10.1109/FOCS.2011.55
András Salamon Le
12

Les treillis et les points fixes sont à la base de l'analyse et de la vérification de programmes. Bien que les résultats avancés de la théorie du réseau soient rarement utilisés car nous nous intéressons à des problèmes d’algorithme tels que l’informatique et l’approximation de points fixes, la recherche sur la théorie du réseau a un objectif différent (connexions à la topologie, théorie de la dualité, etc.). Les premiers documents d’interprétation abstraite utilisent la théorie de base du réseau. Le travail de Roberto Giacobazzi et de ses collaborateurs utilise des résultats plus avancés.

En informatique distribuée, une famille célèbre de résultats d'impossibilité a été dérivée en utilisant des méthodes de topologie algébrique (Voir le travail de Maurice Herlihy et Nir Shavit).

[Edit: Voir Applications de la topologie à l'informatique .]

Vijay D
la source
12

L'algèbre universelle est un outil important pour étudier la complexité des problèmes de satisfaction de contraintes.

Par exemple, la conjecture de dichotomie indique que, grosso modo, un problème de satisfaction de contrainte sur un domaine fini est soit NP-complet, soit résolvable en temps polynomial. Notez que, selon le théorème de Ladner, il existe des problèmes dans NP qui ne sont ni dans P, ni dans NP-complet, à moins que P = NP, de sorte que la conjecture dit que les CSP ont la particularité d'avoir une dichotomie que ne possèdent pas les classes de complexité plus grandes. Cela expliquerait également pourquoi la plupart des problèmes que nous rencontrons dans la pratique peuvent être classés en NP-complet ou en P.

Les dichotomies ont été prouvées dans plusieurs cas particuliers, par exemple les CSP du domaine binaire (Schaefer) et les CSP du domaine ternaire (Bulatov), ​​et les homomorphismes en graphes non dirigés (Hell et Nesetril). Mais le cas général est assez ouvert. L'une des principales lignes d'attaque est l'algèbre universelle. Très grossièrement (et je ne suis certainement pas un expert en cela!), On définit un polymorphisme de CSP comme une fonction du domaine du CSP qui laisse toutes les contraintes satisfaites satisfaites s’il est appliqué à chaque variable. L'ensemble des polymorphismes d'un CSP en capture en quelque sorte la complexité. Par exemple, si un CSP A admet tous les polymorphismes d'un CSP B, alors A est un temps polynomial réductible à B. L'ensemble des polymorphismes forme une algèbre, dont la structure semble utile pour concevoir des algorithmes / montrer des réductions. Par exemple, si l'algèbre de polymorphisme d'un CSP est idempotente et admet le type unaire, alors le CSP est NP-complet. L'idempotence est une hypothèse simplificatrice qui peut être faite plus ou moins sans perte de généralité. Montrer qu'un CSP dont l'algèbre est idempotente et n'admet pas le type unaire peut être résolu en temps polynomial prouvera la conjecture de dichotomie.

Voir l'enquête de Bulatov: http://www.springerlink.com/content/a553847g6h673k05/ .

Sasho Nikolov
la source
11

Voici deux applications d'une partie différente de TCS.

Les semirings sont utilisés pour modéliser les annotations dans les bases de données (en particulier celles nécessaires pour la provenance), et souvent aussi pour les structures d'évaluation dans la satisfaction des contraintes valorisées. Dans ces deux applications, les valeurs individuelles doivent être combinées ensemble de manière à aboutir naturellement à une structure de semiring, avec une associativité et une opération de semiring réparties sur l’autre. En ce qui concerne votre requête sur les modules, aucun des deux monoïdes n’a un inverse dans ces applications, en général.

András Salamon
la source
10

Les anneaux, les modules et les variétés algébriques sont utilisés dans la correction des erreurs et, plus généralement, dans la théorie du codage.

Plus précisément, il existe un schéma de correction d'erreur abstrait (codes de géométrie algébrique) qui généralise les codes de Reed-Solomon et les codes du reste chinois. Le système consiste essentiellement à prendre vos messages comme provenant d'un anneau R et à les encoder en prenant ses résidus modulo dans R différents idéaux différents. Sous certaines hypothèses sur R, on peut prouver que cela constitue un code correct de correction d'erreur.

Dans le monde du décodage par liste, un article récent de Guruswami décrit une méthode linéaire-algébrique de décodage par liste de codes de Reed-Solomon pliés, qui présente la propriété intéressante que tous les messages candidats se trouvent dans un sous-espace affine de dimension réduite de l'espace de message. . On peut construire des ensembles évasifs de sous-espace , des ensembles qui sont presque aussi grands que l’espace tout entier, mais ont une petite intersection avec chaque sous-espace affine de faible dimension. Si l'on restreint les messages provenant d'un ensemble évasif de sous-espace à l'intérieur de l'espace de message, le schéma de Guruswami fournit un algorithme garantissant la taille de la liste. Jusqu'à présent, Dvir et Lovett ont donné la seule construction explicite d'ensembles évasifs de sous-espace dans leur prochain article du STOC, Ensembles évasifs de sous-espace et construisez l’ensemble en prenant une variété affine spécifique (et en prenant son produit cartésien avec lui-même).

Alan Guo
la source
6

Découvrez la théorie de Ramsey - fondamentalement, une généralisation significative du principe du casier qui est à la base de beaucoup d’automates et de la théorie du langage formel (ou devrais-je dire, le principe du casier est le cas le plus simple de la théorie de Ramsey). Il dit fondamentalement que même les structures très désordonnées s'avèrent nécessairement contenir beaucoup d'ordre si elles sont suffisamment grandes. Pour un petit exemple juste au-delà du principe de casier, notez que si vous prenez six personnes, alors trois d’entre elles se connaissent ou trois ne se connaissent pas.

Ce document semble être un bon point de départ pour établir des liens avec l’informatique, mais vous pouvez en rechercher davantage sur Google. Il est plus combinatoire qu'algébrique dans sa nature fondamentale, mais a de nombreuses applications en algèbre et en CS théorique.

Découvrez également l'histoire de l'inventeur, Frank Ramsey - un polymathe remarquable qui a apporté des contributions fondamentales, voire révolutionnaires en économie et en philosophie, ainsi que des mathématiques, dont beaucoup n'ont été appréciées que beaucoup plus tard, avant de mourir à l'âge de 26 ans - il suffit de penser! En fait, le théorème original de Ramsey, la base de la théorie de Ramsey, était un simple lemme dans un article ayant un objectif plus vaste en logique mathématique.

David Lewis
la source
2
C’est une matière classique de combinatoire extrême, je me demande où voyez-vous le lien avec l’algèbre? (Je ne conteste pas que la théorie de Ramsey est source de problèmes et de théorèmes importants)
Sasho Nikolov
SUNEk> =2nwUNE+neSw=Xvous1...vousnyX,yUNE*vous¯je=e
Je ne conteste pas la pertinence de la théorie de Ramsey, encore moins de la théorie des graphes, pour tcs. Je dis que le PO interrogé sur les applications de l'algèbre et la théorie de Ramsey n'est pas quelque chose d'associé d'habitude avec l'algèbre, autant que je sache. mais puisque vous semblez avoir une certaine connexion théorie de Ramsey -> algèbre -> tcs en tête, vous pouvez peut-être ajouter cela à votre réponse
Sasho Nikolov
@Sasho - Si vous voulez dire que Ramsey Theory n'est pas un sujet d'algèbre, ma réponse est donc déformée, alors vous avez raison à 100%. Je m'excuse pour ma réponse. Je suppose que mon esprit a tendance à dépasser les frontières disciplinaires et sous-disciplinaires assez facilement. Mais c'est pire que cela - Ramsey Theory n'est en aucun cas une "structure algébrique". S'il vous plaît n'hésitez pas à downvote ma réponse. Cordialement.
David Lewis
Bien que peut-être logique de voter à la baisse, j’adore la combinatoire extrême, je ne vais donc pas: :) Au fait, je suis certain que certains phénomènes de type ramsey se produisent avec des structures algébriques, peut-être même à des "densités" plus basses, en raison de la symétries, alors vous me donnez une idée d'une question
Sasho Nikolov
5

L'utilisation de la théorie des groupes facilite l'analyse de tout problème présentant beaucoup de symétrie. Un exemple serait de trouver des algorithmes pour des choses comme le cube de rubic. Bien que je ne connaisse pas les détails, je suis sûr que prouver que le nombre de Dieu est 20 nécessite une taille théorique sérieuse en groupe. Dans un contexte différent, les solveurs pratiques pour le problème d'isomorphisme de graphe, tel que Nauty, utilisent le groupe d'automorphisme du graphe.

Shitikanth
la source
En outre, les algorithmes pour l'isomorphisme de graphe [Luks '81; Babai - Luks '82] avec les garanties les plus connues (c'est-à-dire, fonctionne en théorie, mais peut être inefficace en pratique) utilise énormément la théorie des groupes, invoquant même la classification de groupes simples finis.
Joshua Grochow
5

Zp

Pratyush Mishra
la source
1
Si je comprends bien, la cryptographie moderne utilise d’autres structures algébriques (corps finis, anneaux et autres structures), qui abandonne progressivement la théorie des nombres pour se concentrer davantage sur les réseaux, les codes de correction d’erreur et les problèmes «résistants aux quantiques».
Josh
1

En programmation fonctionnelle, les abstractions de problèmes les plus générales et les plus élégantes sont souvent de nature algébrique (ou de catégorie théorique): monoïdes, semirings , foncteurs, monades, algèbres F , coalgebras F, etc. Quelques résultats classiques (par exemple, le Yoneda Lemma) ont un contenu et une utilité calculatoires.

Il existe également la théorie des types d'homotopie, qui interprète la théorie des types dans un cadre topologique algébrique (en quelque sorte).

XRQ
la source