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-255 et
les mercredis 13:30-15:30, Z-260.
Le premier cours aura lieu le
mardi 4 septembre 2018, 9:30. Les demos auront lieu les mardis,
10:30-12:30, Z-255. La première séance de
démo sera le mardi le 11 septembre.
Devoirs
Il y aura à peu près un devoir aux deux semaines.
- Le premier
devoir. À remettre le mardi 25
septembre 9:30 à votre démonstrateur.
Les retards ne seront pas acceptés.
- Le
deuxième devoir.
À remettre le mardi 9 octobre à 9:30
à votre démonstrateur.
Les retards ne seront pas acceptés...
- Le
troisième devoir.
À remettre le mardi 23 octobre avant 13:00.
Vous pouvez remettre votre devoir sous forme
électronique à l'adresse charles.menardATlive.fr.
Les retards ne seront pas acceptés. Le solutionnaire
sera disponible ici après la date de remise.
- Le
quatrième devoir.
À remettre le mardi 27 novembre à 9:30.
Les retards ne seront pas acceptés.
- Le
cinquième devoir. La date
de remise est le 7 décembre à 18:00.
Les retards ne seront pas tolérés...Si vous
voulez le remettre en version papier alors
conformez-vous à la procédure
décrite dans l'introduction du devoir.
Le solutionnaire est disponible ici.
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.
(7 et 8ième semaines)
- Chapitre 6:
Langages décidables et reconnaissables.
(9 et 10ième semaines)
- Chapitre 7:
Un peu de cryptographie.
Démos
Le contenu des démos est disponible sur Studium.
Liens utiles
- Un modèle de calcul construit à partir de
plantes carnivores.
-
La machine de Turing à Alain Tapp(roule
sur PC).
-
Ici
pour un simulateur de Machine de Turing en javascript.
-
Ici
pour une jolie preuve de l'indécidabilité du problème de l'arrêt
originalement montrée par Alan Turing (1936).
Examens
-
L'examen intra aura lieu le mardi 30 octobre de
9:30 à 11:30 au Z-255 (120mins pour compléter). La matière
de l'examen sera celle des chapitres 1,2,3 et
4. Vous avez droit à une page de notes (recto verso).
- L'examen final aura lieu le mardi 11 décembre de
9:30 à 12:30 au local E-240 du pav. Marie-Victorin.
J'examinerai principalement les
chapitres 5 et 6. Il y aura une application du lemme du pompiste.
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 (y compris une question sur la crypto).
Vous n'avez droit qu'à une page de notes recto verso
(pas au
livre ni aux diapos) durant
l'examen...
Mise-à-jour
7/12/2018.
Pour
me rejoindre
|