Ressources d'auto-apprentissage en informatique théorique pour les programmeurs

14

Je suis un ingénieur logiciel assez compétent, mais je ne connais pas beaucoup la théorie. Je veux en savoir plus sur la théorie. Les sujets particuliers qui m'intéressent sont: la complexité informatique, les langages formels et la théorie des types. Mais je ne sais pas trop comment commencer à apprendre ces domaines.

Quelles ressources recommanderiez-vous à quelqu'un qui souhaite en savoir plus sur la théorie par l'auto-apprentissage? Existe-t-il des guides théoriques d'autoformation en informatique pour les ingénieurs logiciels?

soft-question teaching books Henry H.
la source
3
Cela dépend de ce que vous voulez apprendre. Arora-Barak donne une introduction approfondie à la théorie de la complexité informatique (et est disponible gratuitement en ligne). C'est donc un bon point de départ.
Thomas soutient Monica
4
Avez-vous suivi des cours théoriques au collège / université comme les structures de données, les algorithmes, etc.? Si vous n'avez pas suivi les cours théoriques de premier cycle normalement requis, les manuels pour ces cours seraient un bon point de départ. Après cela, vous pouvez consulter les articles de wikipedia, notre liste de livres et la liste des vidéos , des cours en ligne à Coursera / Udacity / EdX / ... Coursera a de très bons cours théoriques.
Kaveh
Qu'as-tu étudié au collège?
Omar Shehab
Dans quel type de langues programmez-vous? Une grande partie de la CS théorique peut être apprise en tandem avec quelque chose de concret. Par exemple, si vous voulez en savoir plus sur les langages formels, les langues / expressions régulières (c'est-à-dire les expressions régulières) sont un bon point de départ, tout comme l'apprentissage des compilateurs. Pour la théorie des types, vous voudrez peut-être jouer avec un langage typé comme haskell, F # ou ML.
Baby Dragon
essayez New Turing Omnibus par Dewdney en tant que référence / enquête / section transversale d'introduction large / accessible. voir aussi les livres de science pop qui inspirent TCS
vzn

Réponses:

7

C'est un vaste domaine avec quelques domaines très différents.

Je commencerais par quelques-unes des idées les plus fondamentales sur ce que sont les ordinateurs: Hopcroft et Ullman, «Introduction à la théorie des automates, aux langages et au calcul».

La raison pour laquelle je recommanderais cela en particulier, c'est l'accent mis sur les preuves. Ils vous guident dans une réflexion rigoureuse. C'est la différence entre écrire des programmes et être scientifique.

Kate F
la source
1
Merci! Je ne sais pas si cela change quoi que ce soit, mais j'ai en fait une formation en mathématiques basées sur la preuve (j'aurais probablement dû le mentionner dans la question). J'ai fait une analyse réelle basée sur des preuves, une topologie par points et une algèbre abstraite.
Henry H.
Ensuite, vous pourrez travailler très rapidement :)
Kate F
c'est une différence mais pas la différence. CS implique de nombreux autres principes, etc.
vzn
Je ne pense pas que le besoin de rigueur soit vraiment une différence entre la programmation et les mathématiques. La programmation et la démonstration des théorèmes sont des tâches très apparentées (cf. l'isomorphisme de Curry-Howard), et pratiquement aucune tâche non mathématique ne requiert plus de rigueur que la programmation. Les compilateurs tolèrent beaucoup moins les erreurs que les humains qui lisent les épreuves.
Jan Johannsen
2
@JanJohannsen Je serais tout à fait en désaccord - par exemple, voir Comportement indéfini pour C.
Kate F
9

Il existe plusieurs façons de se renseigner sur la théorie des types. Pour un programmeur qui travaille, Types et langages de programmation de B. Pierce est un bon début. Les bases pratiques pour les langages de programmation par R. Harper pourraient également être bonnes. Si vous voulez un peu de contexte facile à lire sur la sémantique opérationnelle, je recommande G. Winskel, The Formal Semantics of Programming Languages: An Introduction . Avec T. Nipkow, G. Klein, Concrete Semantics, une variante du livre de Winskel a été formalisée pour l'assistant de preuve interactif Isabelle / HOL. Je soupçonne qu'il est vraiment difficile de se familiariser avec un prouveur juste à partir de ce livre (ou de tout autre livre), vous voudriez qu'un expert à proximité pose des questions. Si vous voulez une approche plus mathématique de la théorie des types, vous pouvez regarder JR Hindley, JP Seldin, Lambda-Calculus and Combinators: An Introduction , ou H. Barendregt's, Lambda Calculi with Types . Bien que je ne recommanderais pas de partir de Barendregt.

Si vous voulez une seule recommandation, je dirais de lire tout Pierce sauf la partie VI (Systèmes d'ordre supérieur) et d'implémenter les langages de jouets dont le livre traite. Vous vous retrouverez avec une solide base dans la théorie des types, et probablement un meilleur programmeur aussi.

Martin Berger
la source
2

Je recommande la calculabilité, la complexité et les langages de Martin Davis, Ron Sigal et Elaine Weyuker.

valepert
la source
C'est un beau livre pour TCS old-skool. À l'exception de la partie de la sémantique théorique du domaine, qui peut être ignorée.
Martin Berger
1

Je suis un grand fan de la théorie et des algorithmes. J'ai eu une fois l'occasion de visiter l'informatique théorique à l'Institut indien de technologie de Madras (IIT-M), en Inde. J'ai appris beaucoup de théoriciens à l'IIT-M. Quand j'y suis allé, je n'avais aucune idée de ce qu'était la théorie, mais aujourd'hui j'en suis totalement amoureuse.

Merci à @Kate F pour le pointeur, oui Hopcroft et Ullman est un excellent point de départ.

Mais voici comment j'ai commencé,

  1. Lisez l'introduction aux algorithmes par Cormen. <\ Br> C'est un excellent point de départ. Lorsque vous étudiez, essayez de comprendre chaque preuve aussi longuement que possible. Si vous comprenez bien la preuve, essayez de coder la même logique dans la langue de votre choix. (Cela prend un peu plus de temps mais ça vaut le coup d'essayer)

  2. Suivez les meilleures conférences en Théorie comme
    FOCS
    SODA
    STOC
    EC (Commerce électronique) - Théorie des jeux algorithmiques
    COLT (Conférence sur la théorie de l'apprentissage) - Théorie de l'apprentissage
    CRYPTO - Cryptographie
    SOCG (Symposium sur la géométrie informatique) - Computational Geometry
    CCC (Conférence sur Complexité informatique) - Théorie de la complexité

Même si vous ne comprenez pas beaucoup, essayez de lire et de PENSER autant que possible. Vous devez faire autant de preuves que possible ..

  1. C'est un endroit merveilleux à regarder si vous pensez en particulier à la complexité informatique ( cela vient de Stanford ).
  2. Suivez le professeur Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Soudan
  3. Voici un ensemble d'informations synthétisées dans le domaine de la complexité informatique
Jaugust
la source