Informatique, Master CSI, Théorie de la Complexité

Thomas Place, Marc Zeitoun ( contact).


  • DS : mercredi 16 novembre 9h30-12h30. Bât. A29/Amphithéâtre A.
    • Programme : feuilles 1 à 6.
    • Documents non autorisés.
  • Examen : lundi 12 décembre 14h30-17h30. Attention à la salle : Grand amphi de biologie animale, B5.
    • Programme à venir.
    • Documents non autorisés.
  • 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.
  • Coefficients du contrôle continu.
    • DS intermédiaire de 3h : 70%.
    • Test sur les ensembles et le raisonnement : 15%.
    • Rendus travail en TD : 10%.
    • Rendus travail à la maison : 5%.

La note globale est composée de la note d'examen (50%) et de la note de controle continu (50%).

  • 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.