Plan/Description
Le plan de cours est accessible ici:
Horaire
Les cours ont lieu les lundis et mardis:
Les cours seront les mardis 9:30-10:30, Z-245 et
les mercredis 13:30-15:30, Z-305.
Le premier cours aura lieu le
mardi 5 septembre 2017, 9:30. Les demos auront lieu les mardis,
10:30-12:30, Z-245. La première séance de
démo sera le mardi le 12 septembre.
Devoirs
Il y aura à peu près un devoir aux deux semaines.
- Le premier
devoir. À remettre mardi le 26
septembre à 10:30 à votre démonstratrice.
Les retards ne seront pas acceptés.
- Le
deuxième devoir.
À remettre le mardi 10 octobre à 10:30
à Stéphanie.
Les retards ne seront pas acceptés...
- Le
troisième devoir.
À remettre le mercredi 7 novembre à 10:30
à Stéphanie avant la période de démonstration.
Les retards ne seront pas acceptés...
- Le
quatrième devoir.
À remettre le mardi 28 novembre à 10:30.
Les retards ne seront pas acceptés.
- Le
cinquième devoir. La date
de remise est le 8 décembre à 12:00 (midi!) par STUDIUM.
Les retards ne seront pas acceptés...Si vous
voulez le remettre en version papier alors
conformez-vous à la procédure
décrite dans l'introduction du devoir.
Nous fournirons le solutionnaire après la remise (évidemment).
ATTENTION: Il y avait un oubli sur l'énoncé du devoir #5
à la question 3. Le blanc doit être ajouté à Gamma,
l'alphabet de ruban. C'est maintenant corrigé.
Les devoirs comptent 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ème semaine)
- Chapitre 3:
La thèse de Church-Turing: Les
machines
de Turing et les expressions booléennes.
L'équivalence entre la puissance de calcul des
programmes TANTQUE
et les machines de Turing. (3ième semaine)
- Chapitre 4:
Langages, Langages Réguliers et
Hors-Contextes. (4,5 et 6ième semaines)
- Chapitre
5:
La classe P et une
introduction à la NP-complétude.
- Chapitre 6:
PSPACE et autres classes de complexité.
- Chapitre 7:
Langages décidables et reconnaissables.
Ici
pour voir la preuve de l'indécidabilité de ATM
sur vidéo.
Démos
Le contenu des démos est disponible sur Studium.
Liens utiles
Examens
- L'examen intra aura lieu le mardi 17 octobre de
9:30 à 11:30 au Z-245 (120mins pour compléter). La matière
de l'examen sera celle des chapitre 1,2,3 et
4. Pour les langages HC,
la matière est celle qui va jusqu'à
la forme normale de Chomski et les propriétés
de fermeture sur les langages HC. Vous devez connaître
le propriétés de fermeture des langages HC pour l'union,
l'intersection et la complémentation.
Le lemme du pompiste
pour les langages HC N'EST PAS à l'examen.
Vous avez droit à une page de notes
recto-verso.
- L'examen final aura lieu le mardi 12 décembre de
9:30 à 12:00 aux locaux Z-315 et Z-350, pav. McNicoll. J'examinerai
les grammaires HC,
la NP-complétude,
l'indécidabilité et les autres classes
de complexité. Les vrais ou faux peuvent référer
à toute la matière vue au cours, mais l'emphase sera
sur la matière vue depuis l'intra.
Vous n'avez droit qu'à une page de notes recto-verso
(pas au
livre ni aux diapos) durant
l'examen...
ATTENTION: D'ici l'examen final
- La matière du cours sera complétée mercredi le 29 novembre.
Le cours de mardi le 5 décembre n'aura pas lieu, mais je serai
disponible à mon bureau pour répondre à vos questions.
- Le cours du mercredi 6 décembre aura lieu. Je reviserai avec
vous la matière depuis l'intra.
Mise-à-jour
6/12/2017.
|