IFT 2102 ­ automne 2001

Introduction à l'informatique théorique

Acétates

Veuillez noter que les versions préliminaires occasionnellement affichées la veille du cours peuvent être changées après le cours pour y correspondre mieux.

Introduction (jeudi 6/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF
Jeu: page composée par un singe au hasard, Postscript (le texte change chaque fois que l'on l'imprime).
Automates finis déterministes (lundi 10/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Automates finis non-déterministes (jeudi 13/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Automates finis non-déterministes II (lundi 17/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Expressions régulières (jeudi 20/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Lemme du pompiste (lundi 24/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Poème: Le Lemme du Pompiste par Harry Mairson (en anglais).
Grammaires hors-contexte (jeudi 27/9)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
GHC: forme normale de Chomsky (lundi 1/10)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Automates à pile (jeudi 4/10)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Machines de Turing (lundi 22/10)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Machines de Turing || (jeudi 25/10)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Décidabilité (lundi 29/10)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Décidabilité II (jeudi 1/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Décidabilité III: réducibilité et le théorème de Rice (lundi 5/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Décidabilité IV: hiérarchie de Chomsky (jeudi 7/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité (lundi 12/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité II: la classe NP (jeudi 15/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité III: temps non-déterministe (lundi 19/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité IV: réductions (jeudi 22/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité V: problèmes NP-complets (lundi 26/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.
Complexité VI: d'autres problèmes NP-complets (jeudi 29/11)
2/page Postscript, 2/page PDF, 6/page Postscript, 6/page PDF.