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.