IFT 2102 automne 2001
Introduction à l'informatique théorique
Professeur:
Miklós Csürös
Bureau: AA 3253
Tél: 343-6111 poste 1655
E-mail: csuros@iro.umontreal.ca
Démonstrateurs:
S'il vous plaît, adressez toute question à l'adresse dift2102@IRO.UMontreal.CA
Type | Jour | Heure | Local |
---|---|---|---|
cours | lundi | 8:309:30 | Z-340 |
jeudi | 11:3013:30 | ||
TP | vendredi | 15:3017:30 | AA 1360, 1409 |
Première demo: le vendredi 7 septembre.
IFT1010 (Programmation I) et IFT1063 (Structures discrètes en informatique).
Existe-t il un programme en language C qui puisse, à la lecture de deux autres programmes P1 et P2, déterminer si P1 et P2 auront le même comportement sur toutes les données qu'on leur soumettra? La théorie sous-jacente à l'informatique offre des balises en ce qui a trait à ce type de questions. Dans le cas précis de la question ci-dessus, essayez pour l'instant de deviner la réponse...
Lorsqu'un programme résolvant un problème existe, des questions d'efficacité se posent. Par exemple, il peut être utile de se demander si la solution du problème pourra être obtenue en moins d'un siècle de calcul ininterrompu. Dans certains cas, la théorie permet de répondre non, sans qu'il soit nécessaire d'attendre qu'un siècle se soit écoulé...
La théorie ne fournit pas que des réponses négatives. Elle rend aussi des choses possibles. Par exemple, ce sont des travaux théoriques sur les langages formels qui ont permis des progrès répétés dans le domaine de la compilation des langages de programmation, ou celui de la recherche de mots dans un texte.
Voici les principaux objectifs du cours IFT2102:
En plus d'acquérir les connaissances factuelles ci-dessus, l'étudiant(e)
Le livre obligatoire et certains livres de référence ont été mis en réserve à la bibliothèque de Math-Info (pavillon André-Aisenstadt).
Pierre Wolper. Introduction à la calculabilité. 2e édition. Dunod 2001. ISBN 2-10-004853-8.
devoirs: 30% intra: 30% final: 40%
Les deux examens seront à livre fermé et l'examen final portera sur la matière de toute la session. Il y aura 6±1 devoirs à caractère théorique, sans programmation, dont les numéros ne seront pas nécessairement tous corrigés. Si la note moyenne aux examens n'atteint pas le seuil de 40%, le cours est échoué.
Important: Vous êtes encouragés à faire vos devoirs en groupes de deux et à remettre une seule copie par groupe.
Semaine | Date | Heures | Matière | Sipser |
---|---|---|---|---|
1 | Je 6/9 | 2 | introduction, languages, automates | ch. 0 |
2 | Lu 10/9 | 9 | automates finis, expressions régulières, langages réguliers | ch. 1 |
Je 13/9 | ||||
3 | Lu 17/9 | |||
Je 20/9 | ||||
4 | Lu 24/9 | |||
Je 27/9 | ||||
5 | Lu 1/10 | 3 | langages hors-contextes, automates à pile | ch. 2 |
Je 4/10 | ||||
6 | (congé universitaire) | |||
7 | Lu 15/10 | 4 | machines de Turing, hypothèse de Church-Turing | ch. 3 |
Je 18/10 | 2 | EXAMEN INTRA: 11:3013:30, salle E-310 | ch. 12 | |
8 | Lu 22/10 | machines de Turing (cont.) | ch. 3 | |
Je 25/10 | ||||
9 | Lu 29/10 | 9 | indécidabilité, réductabilité | ch. 45 |
Je 1/11 | ||||
10 | Lu 5/11 | |||
Je 8/11 | ||||
11 | Lu 12/11 | |||
Je 15/11 | ||||
12 | Lu 19/11 | 7 | théorie de la complexité, P, NP, NP-complétude | ch. 7 |
Je 22/11 | ||||
13 | Lu 26/11 | |||
Je 29/11 | ||||
14 | Lu 3/12 | |||
Je 6/12 | 2 | conclusion, révision, précisions,... | ||
Ve 21/12 | 3 | EXAMEN FINAL: 14:3017:30, salle Z-210 | ch. 15, 7 |