Introduction à l'informatique théorique (IFT2105)

Été 2011

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 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.