Introduction à l'informatique théorique (IFT2105)

Automne 2017

Professeur: Louis Salvail

LITQ, DIRO, Université de Montréal (Québec), Canada



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.