Pourquoi aller à l'informatique théorique / à la recherche?

36

Je commence actuellement à l'université [informatique] et nous avons beaucoup d'occasions de commencer par la recherche. Avant de trouver ce site Web, je n'avais pas l'intention de continuer sur cette voie [je voulais travailler avec l'IA, probablement le développeur de jeu.], Mais maintenant je peux [ou j'ai besoin] de faire un choix.

Pouvez-vous me convaincre de rejoindre ce "monde"? Quels "segments" puis-je suivre? Existe-t-il des sujets sur lesquels un informaticien ou un chercheur travaille?

JulioC
la source
18
Nous sommes honorés que le site vous ait déjà incité à réfléchir à la théorie! Et vous êtes au bon endroit, si vous voulez savoir sur quoi travaille un informaticien théorique ... continuez à lire et vous le saurez!
Ryan Ryan
6
Cela devrait être un wiki de la communauté.
Dave Clarke
Je viens juste de me joindre aujourd’hui et j’ai eu la même question ... j’ai fait mon ingénierie en électronique, mais au collège, j’ai commencé à ressentir une inclination pour la CS ... Je n’ai jamais eu une introduction formelle à Theory, mais je suis heureux d’avoir trouvé ce site ... @ Júlio Souza, merci d'avoir posé cette question. Je vais surveiller cela à partir d'aujourd'hui :)
Alan Turing Le
@supercooldave l'a changé en wiki de communauté.
Juillet
Epilogue: JulioC est devenu développeur de logiciels.
domotorp

Réponses:

32

Je peux relater mes raisons en tant qu'étudiant préparant une licence aux programmes d'études supérieures du SDC cet hiver (il reste donc très peu de temps!).

  • Il y a la beauté. Ce n'est pas quelque chose que je peux expliquer (et j'ai vu d'autres mathématiciens ne pas l'expliquer). C'est comme "jaune". Si vous ne l'avez pas vu, je ne suis pas sûr de pouvoir vous dire ce que c'est. Mais depuis que la théorie vous intéresse, je suppose que vous en faites peut-être l'expérience.
  • Il y a l'universalité. L'universalité au-delà de la thèse de Church-Turing . TCS étudie les phénomènes de haut niveau et de bas niveau dans l’information - c’est la "physique" de l’information. Et puisque l’information est qualitativement atomique , la théorie de l’information a des choses à dire sur la physique (mon professeur de QM m’a dit précisément qu’il adorait la théorie de l’information). Tout cela étant dit, il se situe quelque part entre les mathématiques pures et l'ingénierie. Il a la capacité et la souplesse voulues pour contribuer directement aux deux, et directement aux deux. Pourtant, il combat sur sa propre frontière.
  • Il y a la portée. Cela a été laissé entendre dans la balle précédente. L'informatique trouve son chemin dans de nombreuses applications différentes - tout le monde, du DHD aux startups, s'y intéresse. Vous ne serez pas aussi affamé pour un financement que celui de Mathématiques pures. (Vous serez toujours toujours affamé pour le financement.)
  • Voilà le défi. Jetez un coup d'œil à une liste de problèmes non résolus en informatique théorique (et cherchez à les comprendre jusqu'à la fin de l'enquête). Ils sont très difficiles - voici quelques raisons pour lesquelles . Nous ne comprenons vraiment pas le SDC - la plupart de nos preuves se résument à de plus en plus de preuves. Il reste tellement de travail à faire!
Ross Snider
la source
19

En effet, décider de faire de la recherche en informatique théorique est une question de choix. Mais même en parcourant les questions sur ce site (comme vous l'avez probablement déjà fait), j'espère vous donner une idée de l'ampleur, de la portée et de la beauté du domaine. Je ne sais même pas par où commencer pour vous diriger vers des sources que vous pouvez lire pour apprécier le type de travail des théoriciens, mais il y a une question sur ce même site qui pourrait vous intéresser, à mon avis.

La question est:

Paul Erdos a parlé du "livre" où Dieu conserve la preuve la plus élégante de chaque théorème mathématique. Cela a même inspiré un livre (qui, à mon avis, en est à sa quatrième édition): Proofs from the Book.

Si Dieu avait un livre similaire pour les algorithmes, quel (s) algorithme (s) pensez-vous être candidat (s)?

Il y a actuellement 64 réponses à cette question, couvrant des algorithmes pour les petits problèmes, les gros problèmes, les énigmes et les mathématiques profondes. Je crois fermement que si vous ne faisiez que parcourir cette liste et en savoir plus sur l'un des algorithmes qui attirent votre attention, vous en apprendreriez beaucoup sur ce que font les informaticiens théoriques et pourquoi nous le faisons.

Bonne chance !

Suresh Venkat
la source
16

Si nombre d’entre nous sont allés à la recherche, c’est parce que nous repoussons les limites de ce qui est connu à la fois intellectuellement enrichissant et agréable. Faire de la recherche nous donne également une liberté presque sans précédent pour travailler sur des problèmes que nous trouvons significatifs et intéressants, et cela nous met constamment au défi (ce dont nous jouissons).

TCS (par opposition à d'autres domaines) est une étude mathématique de l'informatique. Vous pouvez travailler sur l'aspect théorique de nombreux domaines différents, des systèmes distribués à l'apprentissage automatique. Le choix entre TCS et d’autres domaines de l’informatique dépend de vos goûts et de vos capacités. Si vos intérêts et capacités naturels résident davantage dans la programmation ou la conception de systèmes que dans l'analyse mathématique, alors vous ne devriez peut-être pas vous lancer dans le TCS. D'autre part, si vos compétences et vos intérêts se situent davantage dans les aspects mathématiques, vous devriez alors envisager le SDC.

En outre, vous ne devez pas toujours choisir un domaine parmi tous les autres. Beaucoup de gens travaillent sur des problèmes à la fois théoriques et pratiques. Ceci est courant, par exemple, dans l’apprentissage automatique, où nous concevons et analysons d’abord des algorithmes (souvent de la théorie), puis nous les testons dans le monde réel (conception expérimentale, applications, etc.).

Un bon moyen de comprendre ce que vous voulez faire est de prendre des cours dans de nombreux domaines différents, et peut-être d'essayer à la fois l'industrie et la recherche pendant vos étés. À la fin de vos études, vous aurez probablement une bonne idée de ce que vous voulez faire.

Lev Reyzin
la source
J'aime beaucoup les maths, mais j'aime la programmation. Peut-être que je pourrais trouver un moyen de travailler avec les deux «côtés» en même temps, comme l'apprentissage automatique [qui se situe dans le domaine de l'IA, n'est-ce pas?]. L'année prochaine, je vais m'inscrire à des cours de mon université tels que l'IA et l'analyse d'algorithme qui peuvent m'aider.
Juillet
L'apprentissage automatique (du moins de mon point de vue) n'est pas un sous-domaine de l'IA, même s'il existe un certain chevauchement. Grosso modo, l'IA se concentre sur la résolution des problèmes normalement résolus par l'homme. L'apprentissage automatique se concentre sur le développement d'algorithmes et de systèmes qui modifient le comportement lorsqu'ils voient des données. Il y a donc clairement un chevauchement entre les deux domaines, mais ils sont loin d'être identiques. L’apprentissage automatique donne clairement aux gens l’occasion de faire de la théorie et de la programmation, mais je suis sûr que ce n’est pas le seul sous-domaine de la CS pour lequel c’est vrai.
Lev Reyzin
11

La théorie des langages de programmation est amusante pour les jeunes et les moins jeunes. C'est appliquer la logique au monde réel. Venez vous joindre à la parade !!

Plus sérieusement, pour moi, la théorie du langage de programmation est intéressante pour les raisons suivantes:

  • impact perçu sur le monde réel: les nombreux systèmes de types utilisés en Haskell et dans d'autres langages fonctionnels, issus d'idées purement logiques (System F), ont une influence considérable sur le développement de langages tels que Java (ses génériques horribles, fermetures) et Scala (le langage moderne). jour où théorie-rencontre-terrain de pratique).

  • beauté: de nombreux outils utilisés dans la théorie des langages de programmation sont basés sur la logique. Cela provient en grande partie de la correspondance de Curry-Howard, qui démontre un lien étroit entre les règles de preuve logiques et les règles de dactylographie pour les langages de programmation, et entre la suppression de la coupe en logique et l'évaluation dans un langage de programmation. Deux beaux exemples récents d'applications de la logique dans la recherche sur le langage de programmation sont les travaux approfondis sur la logique de séparation en vérification et l'application d'idées de preuve axées sur la compréhension de concepts de langage de programmation tels que l' ordre d'évaluation et l'appariement de modèles .

  • amusant: vous pouvez faire de la programmation et de la théorie en même temps, surtout si vous formalisez et vérifiez vos théories en utilisant un assistant de preuve tel que Coq.

  • et beaucoup plus.

Dave Clarke
la source
11

L'une des principales raisons pour lesquelles je trouve la théorie de l'informatique ("ma" branche de l'informatique théorique) fascinante et intéressante à étudier est la suivante: elle nous fournit un moyen d'enquêter sur des questions philosophiques profondes (et parfois déroutantes).

Alan Turing, l'un des fondateurs de la théorie du calcul, a tenté de préciser le sens de «calcul d'une fonction» pour un être humain équipé d'un morceau de papier, en donnant une description mathématique du processus. Je ne suis pas le seul à penser qu'il a eu un très grand succès et les machines de Turing se sont révélées être un modèle précis de nombreux autres processus informatiques.

Maintenant que nous possédons une classe d’objets mathématiques décrivant des calculs, nous pouvons réellement prouver des théorèmes à leur sujet, essayant ainsi de découvrir ce qui peut être calculé et comment il peut être calculé; Il s'est immédiatement avéré que de nombreuses fonctions parfaitement légitimes ne peuvent être calculées et qu'elles peuvent être classées selon un degré d'incompatibilité (certaines fonctions sont simplement «plus non calculables» que d'autres).

Certains autres, les premiers généralement identifiés par Juris Hartmanis et Richard E. Stearns, ont essayé de décrire mathématiquement ce que cela signifie pour une fonction (resp., Un problème) d'être difficile ou facile à calculer (resp., À résoudre). Il existe plusieurs mesures de complexité selon lesquelles la dureté des problèmes peut être décrite; le plus commun est combien de temps il nous faut pour les résoudre. Alan Cobham et Jack Edmonds ont assez bien réussi à identifier une notion raisonnable de «calcul efficace».

Dans le cadre de la complexité de calcul, nous pouvons maintenant prouver des résultats compatibles avec notre notion intuitive de calcul. Mon exemple préféré est le théorème de la hiérarchie temporelle: si on nous donne plus de temps pour calculer, nous pouvons résoudre des problèmes plus difficiles.

Le problème central non résolu de la théorie de la complexité, P vs NP , consiste simplement à formaliser une autre question importante du point de vue philosophique: est-il vraiment plus difficile de résoudre un problème que de vérifier si une solution alléguée est vraiment correcte? Je crois que cette question mérite d'être posée et de répondre, indépendamment de sa signification pratique.

Antonio E. Porreca
la source
+1: aimé :) ps: quelqu'un a exprimé des opinions similaires sur le blog de Scott .
Kaveh
6

Nous ne pouvons pas vous "convaincre", car l'informatique n'est pas mathématiquement meilleure que l'IA ou tout autre domaine. Donc, nous ne pouvons pas réaliser une preuve de sa domination! OMI, c'est plus une question de goût qu'autre chose.

Incroyable
la source
1
Je suis d'accord avec vous, mais il veut probablement savoir pourquoi "vous" (ou tout le monde ici) a choisi ce domaine.
MS Dousti
@ Júlio Souza: Dans le titre, cela devrait être "théorique" et non "théorique".
MS Dousti
Je ne veux pas savoir si c'est mieux, mais je veux savoir pourquoi vous avez choisi ce domaine, comme l'a dit Sadeq.
JulioC
6

Il est difficile de répondre à cette question avec certitude, mais il convient de garder quelques points à l’esprit.

Si vous faites carrière comme informaticien, votre travail consistera probablement non seulement à traiter et à structurer les données de manière à ce qu’elles soient utiles et efficaces, mais aussi à réfléchir à la manière et aux raisons de ce que vous faites, ainsi qu’au quelle limite il opère (ne serait-ce que pour le comprendre suffisamment pour le mettre en œuvre). C’est surtout le cas pour AI / NLP / IR, qui requiert TRÈS beaucoup de recherche, même si vous n’êtes pas dans le monde universitaire. En fait, le recours à l'IA garantit à peu près que vous ferez face à des problèmes "théoriques", et en fait, il peut être difficile de trouver un emploi sans cette expérience. Donc, cela pourrait être une raison impérieuse que vous envisageriez.

Non seulement cela, mais il serait probablement très difficile de passer la plus grande partie de votre vie dans n’importe quel domaine CS, où vous auriez à maintenir un tel contact intime avec des processus aussi délicats et capricieux (sans parler de la difficulté), sans intérêt que ce soit, même dans les bases du pourquoi les choses fonctionnent. En d’autres termes, je suppose que vous pourriez coller des bibliothèques pour le reste de votre vie, mais si cela ne vous ressemble pas, vous devrez au moins avoir une connaissance passagère des principes fondamentaux des problèmes que vous rencontrez.

Bien que participer activement à la recherche sur le SDC soit une question à laquelle vous seul pouvez probablement répondre, un bon point de départ (IMO) consiste à commencer par examiner les problèmes que vous souhaitez examiner et à partir de là. Vous n’avez peut-être même pas assez d’informations pour répondre à cette question. Une meilleure façon de procéder consiste donc simplement à voir où vos intérêts vous mènent.

apc
la source
Merci d'avoir répondu. Je suis tout à fait d’accord avec votre point de vue, travailler sur quelque chose qui vient de l’être, sans savoir pourquoi cela fonctionne, comment cela fonctionne et si je pouvais le rendre meilleur, ce n’est pas quelque chose que je veux. Je pense que je peux essayer de garder mes plans avec l'IA [ou quelque chose d'autre, qui s'apparente davantage à une "recherche pratique"], mais je continuerai d'essayer d'en apprendre davantage sur d'autres sujets liés au SDC.
JulioC
6

Ce qui m’intrigue le plus, c’est la capacité d’appliquer la théorie informatique à d’autres disciplines, notamment la biologie et la biologie cellulaire. Si cette notion vous intrigue également, je vous suggérerais de jeter un coup d'œil à ce qui suit: un essai de Jeannette Wing sur l'importance de la pensée numérique ; et un rapport de la NSF sur l'application de la lentille algorithmique à d'autres disciplines scientifiques.

Aaron Sterling
la source