Y a-t-il des sujets dans CS théorique qui sont plus sur les mathématiques pures?

11

Je suis un étudiant diplômé en informatique théorique, et en particulier en algorithmes d'approximation. Je trouve maintenant que je suis plus intéressé par les mathématiques pures (je peux le dire parce que je semble avoir plus aimé les cours de mathématiques que les cours CS). Je voudrais demander s'il y a des domaines de l'informatique théorique qui sont à peu près des mathématiques pures (pour être plus précis, un domaine qui intéresse les mathématiques pures en soi sans considérer les applications en CS), ou si je dois envisager un interrupteur majeur. Je suis déjà depuis deux ans et demi dans le programme, donc je ne sais pas si un changement serait une bonne idée à ce stade.

La seule chose que j'ai pu trouver était une théorie mineure des graphes, en parcourant les listes d'acceptation des meilleures conférences. Mais cela ne compte pas pour moi comme un «domaine» sur lequel je peux me concentrer.

reference-request soft-question Scientificlens
la source

3

Tout domaine de l'informatique impliquant des mathématiques pures est susceptible d'être davantage motivé par l'informatique que par les mathématiques pures. Considérez les cycles hamiltoniens: quoi de plus pur que de se soucier des cycles traversant les sommets d'un graphe entier? Si cela a des liens avec la logique, n'est-ce pas encore plus excellent du point de vue des mathématiques pures? Pourtant, comment pourriez-vous être plus enraciné dans CS que d'envisager HAMCYCLE?

Niel de Beaudrap

5

"Je peux dire cela parce que je semble avoir davantage aimé les cours de mathématiques": je ne pense pas que cela donne une assez bonne idée de ce qui vous dérange dans TCS afin de répondre à votre question. Il y a beaucoup de choses qui intéressent à la fois les communautés TCS et mathématiques, mais les questions posées sont généralement un peu différentes. De plus, je ne comprends pas pourquoi la théorie des graphes mineurs n'est pas un domaine sur lequel vous pouvez vous concentrer?

Sasho Nikolov

5

En tout cas, quelques idées: intégrations métriques; Analyse de Fourier sur les groupes abéliens finis; Chaînes de Markov sur un espace d'états discret / fini.

Sasho Nikolov

quelque peu liés Exemples de mathématiques «non

vzn

Concernant le risque de basculement, Academia stack Exchange serait peut-être plus adapté?

Clément

12

Voici trois autres champs qui correspondent à vos critères.

Théorie des catégories . Ceci est clairement intéressant pour la plupart des domaines de mathématiques pures, mais a également été très influent dans la théorie des langages de programmation (fonctionnels, séquentiels).
Logique , en particulier théorie des preuves. Les liens avec l'informatique sont trop nombreux pour être nommés, mais la logique n'est pas seulement un riche domaine de mathématiques pures, mais le fondement des mathématiques.
La théorie des nombres , la "reine des mathématiques", jugée dépourvue d'applications ... jusqu'à l'arrivée de la cryptographie.

Martin Berger
la source

note re logic see esp descriptive complexité theory (wikipedia)

vzn

Je ne suis pas sûr que la théorie des catégories (en particulier telle qu'elle est utilisée en CS) soit intéressante pour la plupart des domaines mathématiques au niveau de la recherche, même si elle est utilisée comme langue de base dans plusieurs domaines. Par exemple, bien que la théorie des catégories apparaisse clairement au niveau de la recherche dans (certaines) géométries algébriques et théorie de la représentation, ce type de théorie des catégories est très différent de celui utilisé en informatique, pour autant que je sache.

Joshua Grochow

1

@JoshuaGrochow C'est en partie vrai, mais c'est en partie parce que c'est un travail en cours. Il y a des indices alléchants qui pointent vers une intégration plus profonde: (1) les fondations univalentes de Voevodsky tentent d'unifier les idées de chemin dans la théorie de l'homotopie avec des preuves en logique; (2) les théories houillères des nombres réels par Pavlovic et al; (3) fondements catégoriques de la mécanique quantique, voir par exemple "Physique, topologie, logique et calcul: une pierre de Rosette" par Baez et Stay.

Martin Berger

9

Oui: la théorie des graphes, la géométrie informatique, la théorie de la complexité, la combinatoire sont les choses sur lesquelles je recherche en CS. Les espaces vectoriels et la théorie des mesures pourraient également être utiles dans l'apprentissage machine théorique.

Il y a beaucoup plus de mathématiques pures utilisées dans le CS théorique, mais elles ne font pas la une des journaux aussi souvent que l'IA et l'apprentissage automatique, c'est pourquoi vous n'en entendez pas beaucoup parler.

Personnellement, je suis passé à CS de la physique et des mathématiques pures (oui, comme les mathématiques de type algèbre abstraite), et je ne cesse de trouver des problèmes intéressants.

Keng
la source

1

Et j'ajouterais la géométrie discrète à cette liste.

Sariel Har-Peled

7

La théorie de la complexité géométrique est extrêmement «mathématique» et nombre de ses principaux chercheurs sont davantage des mathématiciens. voir par exemple Théorie de la complexité géométrique: une introduction aux géomètres / Landsberg
La théorie des groupes est connectée au TCS de nombreuses manières profondes, par exemple dans l'étude du mot problème, des isomorphismes et de l'indécidabilité. voir par exemple LE MOT PROBLÈME ET LE PROBLÈME D'ISOMORPHISME POUR LES GROUPES / Stillwell
certaines théories des automates sont très mathématiques, par exemple la connexion de semigroupes à des transducteurs à états finis, etc. voir par exemple les fondements mathématiques de la théorie / broche des automates

vzn
la source

2

Pourquoi les citations autour de "mathématique"?

Joshua Grochow

dans certains domaines, il peut être difficile de différencier le contenu "(T) CS" de "mathématique" comme le pose la question, la fin de cette phrase devrait être "les principaux chercheurs sont [presque] plus de mathématiciens que d'informaticiens"; les deux domaines se mélangent lentement à bien des égards, cela peut être vu au cours du 20e siècle et il continue / augmente au 21e siècle. une fusion en cours probablement digne d'un livre entier et certains se rapprochent (par exemple Davis, Engines of Logic: Mathematicians and the Origin of the Computer ).

vzn

La question était assez claire à cet égard: "un domaine qui intéresse les mathématiques pures à lui seul sans tenir compte des candidatures à CS." Cela est certainement vrai pour beaucoup, sinon la plupart, des questions mathématiques soulevées dans GCT.

Joshua Grochow

Voici une autre référence similaire concernant l'indécidabilité dans la théorie des groupes et les problèmes de mots. TURING MACHINES TO WORD

PROBLEMS

7

$\mathbb{B}$ $\mathbb{F}_2$

Par exemple, on utilise des semi - groupes (également les groupes jouent également un rôle important) et de nombreux résultats sur les semi-groupes finis au cours des dernières années étaient à l'origine motivés par la théorie des automates. Les semi - anneaux sont également utilisés (plutôt que les anneaux): par exemple, le semirage tropical a d'abord été introduit dans la théorie des automates avant d'être utilisé en géométrie tropicale , un nouveau domaine réussi en mathématiques. D'autres sujets liés aux automates incluent la théorie de la logique et des modèles finis (pensez au théorème de l'arbre de Rabin), la topologie, la dualité et les espaces (quasi) uniformes et certaines théories des nombres (notamment pour les questions traitant des systèmes de numération et des séries de puissances formelles), la théorie des probabilités ( notamment les chaînes de Markov) et la théorie des jeux.

J.-E. Épingle
la source

B

$\mathbb{B}$

B^{*}

$\mathbb{B}^*$

7

Pour en dire un peu plus sur la théorie de la complexité géométrique (GCT): il s'agit de l'application de la géométrie algébrique et de la théorie de la représentation à un programme à long terme pour résoudre P contre NP. Les questions soulevées dans GCT ont tendance à être des questions mathématiques profondes, dont certaines remontent à plus de 100 ans aux pionniers de la géométrie algébrique et de la théorie de la représentation - apparemment n'ayant rien à voir avec le calcul, mais via GCT on voit qu'elles sont en fait intimement liées avec la complexité de calcul - et d'autres qui soulèvent de nouvelles questions et idées en mathématiques pures (encore une fois, la géométrie algébrique et la théorie de la représentation).

Joshua Grochow
la source

4

Pas tout à fait un sujet théorique de CS mais utilise de nombreux résultats de CS théorique: vous pouvez être intéressé par la vérification logicielle dont le but est de s'assurer qu'un programme fait ce qu'il est censé faire, et rien d'autre. Parmi les différentes techniques de ce sujet, certaines sont particulièrement orientées mathématiques. De nombreux systèmes critiques, en avionique / spatial / nucléaire notamment, ont été prouvés de cette façon pour s'assurer qu'ils sont exempts de bogues.

De nombreux domaines mathématiques sont impliqués: logique, théorie des preuves, théorie des automates, théorie des ensembles, ...

la source

Y a-t-il des sujets dans CS théorique qui sont plus sur les mathématiques pures?

Réponses: