Informatique, Master CSI, Théorie de la Complexité
Thomas Place, Marc Zeitoun (contact).
- Test 1 : 23/9.
- Test 2 : 30/9.
- DS : 15/11 14h-17h A9/ Amphithéâtre 3.
* Prérequis : vocabulaire des ensembles et raisonnement mathématique.
Vidéos du MOOC préparatoire, Introduction au raisonnement mathématique : préparation à l'entrée dans l'enseignement supérieur de Henri Lemberg et Magali Rocher : Vidéos du MOOC.
- Bibliographie
- Livre de Sylvain Périfel (Pdf).
- Pierre Wolper, Introduction à la calculabilité, Dunod (en français).
- Sipser, Introduction to the Theory of Computation.
- Papadimitriou, Computational Complexity.
- Garey & Johnson, Computers and Intractability.
- Supports de cours et exercices
- Diapos septembre 2023.
- Notes de cours et feuille d'exercices n.1 : automates finis et langages réguliers.
- Notes de cours et feuille d'exercices n.2 : grammaires et langages hors-contexte.
- Notes de cours et feuille d'exercices n.3 : machines de Turing.
- Notes de cours et feuille d'exercices n.4 : décidabilité et indécidabilité.
- Préparation au DS (DS 2023-24) : problème de correspondance de Post.
- Notes de cours et feuille d'exercices n.5 : complexité en temps.
- Notes de cours et feuille d'exercices n.6 : complexité en espace.
- Annales
- 2024-2025
- 2023-2024
- 2022-23
- 2021-22
- 2020-21
- 2019-20
- DM.
- DS.
- Examen session 1.
- 2018-19
- 2017-18
- 2016-17
- 2015-16