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

Horaire

TypeJour HeureLocal
courslundi8:30­9:30Z-340
jeudi11:30­13:30
TPvendredi15:30­17:30AA 1360, 1409

Première demo: le vendredi 7 septembre.

Préalables

IFT1010 (Programmation I) et IFT1063 (Structures discrètes en informatique).

Contenu général et objectifs du cours

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)

Bibliographie

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

Livre obligatoire

Michael Sipser. Introduction to the Theory of Computation. PWS (Brooks/Cole) 1997. ISBN 0-534-94728-X.

Autres références

John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation 2e édition. Addison-Wesley 2000. ISBN 0-201-44124-1.

Pierre Wolper. Introduction à la calculabilité. 2e édition. Dunod 2001. ISBN 2-10-004853-8.

Évaluation

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.

Plan approximatif

Semaine Date Heures Matière Sipser
1Je 6/92introduction, languages, automatesch. 0
2Lu 10/9 9 automates finis, expressions régulières, langages réguliers ch. 1
Je 13/9
3Lu 17/9
Je 20/9
4Lu 24/9
Je 27/9
5Lu 1/103 langages hors-contextes, automates à pile ch. 2
Je 4/10
6 (congé universitaire)
7Lu 15/104 machines de Turing, hypothèse de Church-Turing ch. 3
Je 18/102 EXAMEN INTRA: 11:30­13:30, salle E-310 ch. 1­2
8Lu 22/10  machines de Turing (cont.) ch. 3
Je 25/10
9Lu 29/109 indécidabilité, réductabilité ch. 4­5
Je 1/11
10Lu 5/11
Je 8/11
11Lu 12/11
Je 15/11
12Lu 19/117 théorie de la complexité, P, NP, NP-complétude ch. 7
Je 22/11
13Lu 26/11
Je 29/11
14Lu 3/12
Je 6/122conclusion, révision, précisions,...  
 Ve 21/123 EXAMEN FINAL: 14:30­17:30, salle Z-210 ch. 1­5, 7