. Il présente tout le contenu de ce cours, y compris les sujets de travaux pratiques et les recommandations pour les réaliser.
| prérequis | pour approfondir | pour aller plus loin | pour élargir | |
| accessible |
 «Mathématiques pour l'informatique»,
de A. Arnold et I. Guessarian (Dunod, 2005).
«Méthodes mathématiques pour l'informatique»,
de J. Vélu (Dunod, 2005).
|
«Computer Ltd, What they really can't do!», de D. Harel (Oxford University Press, 2000)
;
«L'infini et l'univers des algorithmes»,
de G. Dowek (Pour la Science, hors-série «Les infinis», décembre 2000).
|
«Histoire d'algorithmes --- Du caillou à la puce»,
de J.-L. Chapert et al. (Belin, 1994).
«Turing»,
de J. Lassègue (Pour la Science, Les génies de la sciences, n. 29, novembre-janvier 2007).
«La machine de Turing»,
de A. Turing et J.-Y. Girard (Seuil, 1995). «De la programmation considérée comme un des Beaux-Arts»,
de P. Lévy (La découverte, 1992).
«The new Turing omnibus»,
de A.K. Dewdney (Owl Books, 2001).
|
«L'apologie d'un mathématicien»,
de AG.H. Hardy (Belin, 1985).
«La philosophie des sciences»,
de D. Lecourt (PUF, Que-sais-je ?, 2001).
«Le fascinant nombre PI»,
de J.-P. Delahaye (Belin/Pour la Science, 1997).
«Oncle Petros et la conjecture de Goldbach»,
de A. Doxiadis (Owl Books,2001).
|
| plus difficile |
«Logique, réduction et résolution», de R.
Lalement (Masson, 1990) ;
«Computability and complexity --- From a programming perspective»,
de N.D. Jones (MIT Press, 1997).
|
«La machine en logique»,
de P. Wagner (PUF, 1998).
|
«Abrégé d'histoire des mathématiques»,
collectif, dir. J. Dieudonné (Herman, 1978).
«Le défi de Hilbert --- Un siècle de mathématiques»,
de J. Gray (Dunod, 2004).
«
Et Dieu créa les nombres --- Les plus grands textes de mathématiques»,
de S. Hawking (Dunod, 2006).
«Conversation avec le Sphinx --- Les paradoxes en physiques»,
de É. Klein (Albin Michel, 1991).
|
| semaine |
cours |
TD |
TP |
auto-évaluation |
| 2 | 8/01 --- Introduction : programme, fonction, théorèmes de Cantor | Avoir compris quelque chose de l'introduction, et surtout qu'il y a plus de fonctions que de programmes. | ||
| 3 | 15/01 --- Calculateur, mémoire, état, unité de calcul, arrêt, problème de l'arrêt | 17/01 et 18/01 --- Énumération de Cantor | Avoir compris la preuve du programme de l'arrêt. | |
| 4 | 22/01 --- Variantes du problème de l'arrêt, réduction calculatoire, théorème de Rice | 24/01 et 25/01 --- Énumération de Cantor | Avoir pris l'environnement Scheme en main. Avoir compris la notion de réduction, et son mode d'emploi. |
|
| 5 | 29/01 --- Le langage WHILE ; syntaxe et sémantique | 31/01 et 01/02 --- Préparation TP pretty-printer | Avoir compris la formalisation du langage WHILE, et faire le lien avec le modèle de calculateur présenté après l'introduction. | |
| 6 | 05/02 --- Programmation dans le langage WHILE | 07/02 et 08/02 --- Un pretty-printer (étape 1) | Se faire une idée des possibilités du langage WHILE. | |
| 7 | 12/02 --- Interpréteur WHILE en WHILE | 14/02 et 15/02 --- Un pretty-printer (étape 2) | Comprendre ce qu'a d'universel l'interpréteur WHILE. | |
| 8 | 19/02 --- Le langage FOR : syntaxe et sémantique | 21/02 et 22/02 --- Un pretty-printer (étape 3) | Avoir pris en main l'environnement de programmation utilisé en TP : test, stratégie de développement. | |
| 10 | 04/03 --- FOR est strictement moins expressif que WHILE | 06/03 et 07/03 --- Préparation TP interpréteur WHILE | 07/03 --- Rendre compte-rendu du TP pretty-printer (par e-mail) | Avoir compris le schéma de preuve de l'incomplétude de FOR. |
| 11 | 11/03 --- Le concept de complexité asymptotique | 13/03 et 14/03 --- Un interpréteur WHILE (étape 1) | Avoir compris le concept de complexité asymptotique. | |
| 12 | 18/03 --- P et NP | 20/03 et 21/03 --- Un interpréteur WHILE (étape 2) | Comprendre les définitions de P et NP, et le rôle de la réduction polynomiale. Bien distinguer les niveaux de langage trouvés dans un interpréteur. |
|
| 13 | 25/03 --- NP-complétude : le problème SAT | 27/03 et 28/03 --- Préparation TP transformation d'expressions | Avoir compris la structure de la preuve de la NP-complétude du programme SAT. | |
| 14 | 01/04 --- Conclusion | 03/04 et 04/04 --- Transformation d'expressions (étape 1) | Retrouver dans le cours les idées recensées dans la conclusion, et comprendre comment elles s'articulent. Bien distinguer les niveaux de langage trouvés dans un compilateur. |
|
| 15 | 10/04 et 11/04 --- Transformation d'expressions (étape 2) | Savoir lire les rubriques «Pour aller plus loin», et comprendre où elles conduisent. S'imaginer traiter les autres transformations de programme présentées dans le cours. |
||
| 16 | 18/04 --- Rendre compte-rendu du TP transformation d'expressions (par e-mail) |