Informatique, Master CSI, Théorie de la Complexité
Thomas Place, Marc Zeitoun (contact).
- Test 1 : 29/9 (30 à 45mn sur les prérequis, cf. ressources ci-dessous). Coefficient : 7.5% du CC.
- Test 2 : 6/10 (30 à 45mn sur les prérequis). Coefficient : 7.5% du CC
- DS : prévu le 14/11 14h-17h (à confirmer). Coefficient : 85% du CC.
- Note de l’UE : 50% CC, 50% Examen.
- Prérequis : vocabulaire des ensembles et raisonnement mathématique.
Nombreuses ressources en ligne, par exemple :
- Bibliographie
- Pierre Wolper, Introduction à la calculabilité, Dunod (conseillé particulièrement pour la première partie, en français).
- Sipser, Introduction to the Theory of Computation.
- Livre de Sylvain Périfel (Pdf). Aborde des notions allant bien au delà du cours.
- Papadimitriou, Computational Complexity.
- Garey & Johnson, Computers and Intractability. Collection de problèmes NP-complets.
- Supports de cours et exercices
- Notes de cours et feuille d'exercices n.1 : machines de Turing.
- Notes de cours et feuille d'exercices n.2 : décidabilité et indécidabilité.
- Notes de cours et feuille d'exercices n.3 : Indécidabilité : problèmes de pavage et de correspondance de Post.
- Notes de cours et feuille d'exercices n.4 : complexité en temps.
- 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