Branche de l'informatique théorique orientée algèbre

33

J'ai une base très forte en algèbre, à savoir

  • algèbre commutative,
  • algèbre homologique,
  • théorie des champs,
  • théorie des catégories,

et j'apprends actuellement la géométrie algébrique.

Je suis un étudiant en mathématiques avec une tendance à passer à l'informatique théorique. En gardant à l'esprit les domaines mentionnés ci-dessus, quel domaine serait le domaine le plus approprié en informatique théorique vers lequel basculer? Autrement dit, dans quel domaine la théorie et la maturité mathématique obtenues en poursuivant les domaines susmentionnés peuvent-elles être utilisées à son avantage?

spaceman_spiff
la source
1
L'étude des champs est-elle considérée comme faisant partie de l'algèbre? Il y en a sur math.se qui ne pense pas.
Alancalvitti
1
Il est offert dans de nombreux instituts ici comme deuxième cours d'algèbre de niveau et de nombreux livres célèbres sur l' algèbre comme Dummit et l' algèbre abstraite de Foote comprend un contenu significatif sur la théorie déposée ...
spaceman_spiff

Réponses:

24

La géométrie algébrique est fortement utilisée dans la théorie de la complexité algébrique et en particulier dans la théorie de la complexité géométrique. La théorie de la représentation est également cruciale pour ce dernier aspect, mais elle est encore plus utile lorsqu'elle est associée à la géométrie algébrique et à l'algèbre homologique.

Joshua Grochow
la source
15

Votre connaissance de la théorie des champs serait utile en cryptographie, tandis que la théorie des catégories est très utilisée dans la recherche sur les langages de programmation et les systèmes de dactylographie, deux domaines étroitement liés aux fondements des mathématiques.

Martin Berger
la source
11

La théorie des champs et la géométrie algrebrique seraient utiles pour les sujets liés aux codes de correction d'erreur, aussi bien dans le contexte classique que dans l'étude de codes localement décodables et du décodage de listes. Je pense que cela remonte au travail sur les codes de Reed-Solomon et Reed-Muller, qui ont ensuite été généralisés aux codes géométriques algébriques. Voir, par exemple, ce chapitre de livre sur la théorie classique du codage des codes géométriques algébriques, ce bref aperçu des codes décodables localement et ce célèbre article sur le décodage par liste de Reed-Solomon et, plus généralement, les codes géométriques algébriques.

Sasho Nikolov
la source
7

Certains problèmes liés à la théorie de l’apprentissage informatique, à l’apprentissage automatique et à la vision par ordinateur peuvent être résolus au moyen de l’algèbre commutative et de la géométrie algébrique. Par exemple, la convergence de l'algorithme de propagation des croyances, un algorithme de transmission de message pour l'inférence bayésienne, peut être formulée en termes de caractérisation de la variété affine de systèmes d'équations polynomiales .

Carlos Eduardo Cancino Chacón
la source
6

Avez-vous pensé à regarder l'algèbre informatique? Axiom est un système de calcul algébrique dans lequel le système de types est modélisé d'après la théorie des catégories (ou algèbre universelle, selon votre vue). Il existe deux autres dérivés d'Axiom FriCAS et OpenAxiom .

Si vous êtes intéressé par la théorie des catégories, le système de types peut être une chose à examiner.

Dans Axiom, chaque "élément" (par exemple, "1", "5 * x ** 2 + 1") est un élément d'un domaine. Un "domaine" est un objet Axiom déclaré membre d'une catégorie particulière (par exemple, Integer, Polynomial (Integer). Une catégorie Axiom est un objet Axiom déclaré comme membre du symbole distinctif "Category" (par exemple, Ring, Polynomial (TOUR)).

Il existe un réseau d'héritage pour l'héritage multiple parmi les catégories. Par exemple, la catégorie Monad hérite de SetCategory, Monoid de Monad, Group de Monoid, etc., etc.

Il existe également un polymorphisme d'ordre supérieur, un peu similaire aux génériques en Java.

Plusieurs actions au sein d'Axiom peuvent être considérées comme des foncteurs, mais ce serait plutôt compliqué d'entrer ici!

Si vous souhaitez simplement utiliser Axiom sans vous soucier de la théorie des catégories, en tant qu'utilisateur final typique, un système de calcul symbolique est exactement le logiciel idéal pour examiner différentes algèbres.

Nic Doye
la source
5

Voici une réponse intéressante, mais personne n’a mentionné que chaque langue est naturellement associée à une structure monoïde via la relation de congruence de Nérode-Myhill.LX

Les personnes suivantes ont utilisé cette vue algébrique dans le cas des langages normaux: Samuel Eilenberg sur la théorie des automates, Jean Berstel , Jean-Eric Pin , Marcel Schützenberg et la théorie de Krohn-Rhodes .

De plus, il existe une algèbre non triviale impliquée dans le travail autour de la conjecture de Cerny , dont la plupart est plutôt combinatoire. Mais plus récemment, j'ai vu plus de choses faites avec l'algèbre linéaire, la théorie des anneaux et la théorie de la représentation, je pense au travail de Benjamin Steinberg et Jorge Almeida .

Soit dit en passant, la théorie des semigroupes, des monoïdes et des groupes peut vous convenir, mais la théorie des catégories et la théorie de l'homotopie ne sont pas beaucoup utilisées dans ce domaine. Mais il est peut-être intéressant de noter que S. Eilenberg a été l’un des pères fondateurs de la théorie des catégories, alors même qu’il était avant d’être impliqué dans la théorie des automates.

StefanH
la source
Il pourrait également être intéressant d’examiner les langues des arbres plutôt que les langues des mots. Le problème ouvert persiste depuis longtemps: caractériser le pouvoir expressif de la logique de premier ordre sur les arbres en termes d'objet algébrique associé (mentionné dans "Quelques problèmes ouverts dans les automates et la logique" dans ACM SIGLOG News). Pour des lectures plus approfondies, je recommanderai des articles de Mikołaj Bojańczyk et Howard Straubing.
Bartosz Bednarczyk
4

La thèse de Brent Yorgey , même s'il ne s'agit que d'un brouillon, fait un travail remarquable pour expliquer pourquoi vos intérêts sont pertinents pour le SDC.

Voici le discours de Joyal en avril dernier sur des documents connexes.

Chad Brewbaker
la source
12
Je ne sais pas ce que sont les coutumes ici, mais sur Stack Overflow, cette réponse serait probablement supprimée sous forme de réponse en lien uniquement très bientôt. Voulez-vous s'il vous plaît fournir un résumé de la façon dont le lien répond à la question, pas seulement ce qu'il fait? Les liens ont tendance à se rompre avec le temps et sans lien, votre réponse serait presque inutile.
Palec
1
Ne t'inquiète pas. Je me suis écrit un rappel pour le mettre à jour avec sa version finale.
Chad Brewbaker
4
@ChadBrewbaker Mais, toujours, votre réponse est essentiellement deux liens. Même si vous promettez de maintenir ces liens à jour (ce qui est un objectif noble et très apprécié, mais sûrement voué à l'échec), c'est une mauvaise réponse.
David Richerby le
3

Je ne sais pas si vous avez envisagé l'industrie, mais la société Ayasdi fait un travail remarquable en appliquant beaucoup d'homotopie et d'autres méthodes topologiques appliquées à la science des données. Ils mélangent beaucoup de théorie avec des applications. Fondamentalement, pour voir ce qu’ils font, consultez le site Web de Stanford Comptop. (La majorité des gens sont venus de là).

mathDR
la source
2

En plus de ce que tout le monde a dit (je suppose que la plus grande application de ces branches est bien dans les systèmes de types):

  • La théorie du réseau et les ordres partiels en général sont assez appliqués pour l'analyse du comportement de systèmes répartis et pour l'analyse de flux de données dans les compilateurs.
  • J'ai également vu des connexions Galois appliquées à l'apprentissage automatique (notamment la classification de texte: la connexion Galois entre des sous-ensembles de sommets gauche et droit d'un graphe document / mot bipartite permettait d'accélérer considérablement un algorithme).
jkff
la source
1

Les liens entre l’algèbre et l’informatique théorique sont très forts. Nic Doye a déjà mentionné Computer Algebra, mais il n’a pas explicitement inclus la théorie des systèmes de réécriture, qui est une partie essentielle de Computer Algebra, avec des applications dans la résolution automatique d’équations et le raisonnement automatique. Les systèmes de réécriture de chaînes constituent un sous-domaine important, avec des applications dans la théorie des groupes de calcul. Vérifiez le livre "String Rewriting Systems", de Ronald Book et Friedrich Otto, par exemple.

Il existe également un lien entre la théorie des graphes et l'algèbre, qui inclut par exemple la théorie spectrale bien développée des graphes et des réseaux complexes, ainsi que la théorie des symétries de graphes (graps de Cayley, graphes de sommet-transitif et autres types de graphes symétriques). , qui sont fortement utilisés comme modèles pour les réseaux d’interconnexion dans les ordinateurs parallèles). Consultez le livre "The Algebraic Graph Theory" de Chris Godsil et Gordon Royle pour un aperçu des différents sujets.

Manolito Pérez
la source
0

Découvrez la situation en vision par ordinateur. Il existe de nombreux sujets, en particulier de type algorithmique, pour lesquels les trois premiers domaines que vous avez énumérés sont très utiles.

Martin Peters
la source