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.