L3 Informatique, U. Grenoble Alpes
Pour l’autre partie du cours Modèles de calculs, qui traite de lambda-calcul, visiter la page dédiée.
Le plan indiqué est prévisionnel et susceptible de modifications.
Ces références sont présentes pour celles et ceux qui le souhaitent, mais il n’y a aucune obligation à les consulter. Elles peuvent soit vous permettre d’avoir une autre présentation des sujets traités en cours, soit d’aller plus loin car elles abordent des sujets non traités.
Références principales, en anglais (qui couvrent bien plus que le cours !) :
B. Barak, Introduction to theoretical computer science, 2023 (work in progress). Livre accessible en ligne en format html ou pdf, à conseiller très fortement ! Inutile d’aller au delà du chapitre 10 pour ce cours.
R. Sedgewick and K. Wayne, Computer science: an interdisciplinary approach. Addison-Wesley, 2017. Livre très abordable, très bien fait !
M. Sipser, Introduction to the theory of computation, 3. ed. Andover: Cengage Learning, 2013. Encore un livre assez abordable, mais bien plus formel.
Livres en français, accessibles à la bibliothèque universitaire :
P. Wolper, Introduction à la calculabilité : cours et exercices corrigés, 3è éd., Dunod, 2006.
O. Ridoux, G. Lesventes, Calculateurs, calculs, calculabilité, Dunod, 2008. Calculabilité sans machine de Turing.
O. Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
J.-M. Autebert, Calculabilité et décidabilité : une introduction, Masson, 1992.
Notes de cours en français disponible en ligne :
E. Asarin, Calculabilité, 2003. Super notes de cours sur la calculabilité (par un ancien enseignant de Grenoble) ! Tout y est, de manière concise. Très chaudement recommandé !
K. Perrot, Calculabilité, 2022-2023. Un ensemble de notes de cours, sujets de TD, examens, etc. d’un collègue marseillais.
Dernière modification : 13 janvier 2025