prérequis | pour approfondir | pour aller plus loin | pour élargir | |
accessible |
![]() ![]() |
![]() ![]() |
![]() ![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
plus difficile |
![]() ![]() |
![]() |
![]() ![]() ![]() ![]() |
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) |