Plan/Description
Le plan de cours est accessible ici:
Horaire
Les cours ont lieu les lundi et mercredi comme
indiqué ci-bas:
Le premier cours aura lieu que le
lundi 2 mai 2011. Les demos auront lieu le mercredi de
14:30-16:30.
Le cours du lundi débutera à 9:30 au
lieu
de 8:30. La salle du cours est le Z-337 et non le
Z-300 jusqu'au (excluant cette dernière) 16
mai.
À partir du 16 mai, le cours du lundi aura lieu
au Z-220.
Devoirs
Il y aura a peu près un devoir par semaine (un
peu moins). La question 2 avait une typo
malencontreuse: je demandais de demontrer les 3
enoncés tandis qu'il y en avait 4...La nouvelle
version corrige le tir...
- Le premier devoir. À remettre le 1ier
juin à 13:30. Les retards ne seront pas acceptés.
- Le
deuxième devoir.
À remettre le mercredi 15 juin à 13:30, juste
avant l'examen intra.
Les retards ne seront pas acceptés...
- Le
troisième devoir.
À remettre le lundi 4 juillet à 9:30.
Les retards ne seront pas acceptés...
- Le
quatrième devoir.
À remettre le mercredi 13 juillet à 13:30.
Les retards ne seront pas acceptés...
- Le
cinquième devoir. Comme nous avons
décidé au cours, la date
de remise est le mercredi 20 juillet à 13:30.
Les retards ne seront pas acceptés...
- L'examen final de
pratique.
Sera corrigé au cours du lundi le 25 juillet.
Les devoirs compterons pour 30% de la note finale.
Notes
Voici les sujets traités à mesure que le semestre progresse:
- Chapitre 1:
Introduction, Techniques de preuve,
notions asymptotiques. (1ière semaine)
- Chapitre 2:
Deux modèles de calcul
simples. Les programmes RÉPÉTER et TANTQUE. Une limite
quant à la puissance de calcul des programmes
RÉPÉTER. (2 et 3ième semaine)
- Chapitre 3:
La thèse de Curch-Turing: Les
machines
de Turing et les expressions booléenne.
L'équivalence entre la puissance de calcul des
programmes TANTQUE
et les machines de Turing. (4ième semaine)
- Chapitre 4:
Langages, Langages Réguliers et
Hors-Contextes. (5 et 6ième semaine)
- Chapitre 5:
Introduction à la NP-complétude.
- Chapitre 6:
PSPACE et autres classes de complexité.
- Chapitre 7:
Langages décidables et reconnaissables.
Liens utiles
Examens
- L'examen intra aura lieu le mercredi 15 juin de
13:30 à 15:30 au Z-210. La matière
de l'examen sera celle des chapitre 1,2,3 et
4. Pour les langages hors-contextes,
la matière est celle qui va jusqu'à
la forme normale de Chomsky sans l'inclure.
Vous n'avez pas droit à vos notes (ni au
livre, ni aux transparents) durant l'examen...
- L'examen final aura lieu le mercredi 27 juillet de
14:30 à 17:30 au Z-330. La matière
de l'examen sera toute celle que nous avons vu au
cours et en démo. J'examinerai davantage
la fin du chapitre 3 (à partir des langages
HC) et les chapitres 4,5,6 et 7.
Vous n'avez pas droit à vos notes (ni au
livre, ni aux transparents) durant
l'examen...Autrement dit, aucune documentation n'est permise.
Mise-à-jour
Date de la dernière mise à jour est: 27/07/2011.
|