Calculabilité et Complexité

Année 2003-2004


Contacts:

Horaires: Contrôles continus:
Les dates et règlements des contrôles continus sont disponibles ici: [ps] [pdf]

Contenu du cours:
(Ceci est un "guideline" susceptible d' être modifié).

Séries d'exercices:
Les anciennes séries d'exercices sont disponibles [ici]

Bibliographie:

  1. Olivier Biberstein   and José Rolim, Eléments d'informatique théorique. Université de Genève,1997.
  2. John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages and computation. , Addison-Wesley, 1979.
  3. Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, Boston, 1997. (F.0.0 Sip hors prêt).
  4. Harry R. Lewis and Christos H Papadimitriou. Elements of the theory of computation. , Prentice-Hall, Englewood Cliffs, 1981. ( F.0.0 Lew hors prêt).
  5. Christos H. Papadimitriou, Complexity.
  6. Bovet Crescenzi, Introduction to complexity theory
  7. Dino Mandriolo and Carlo Ghezzi. Theorical foundations of computer science. John Wiley & Sons, New York, 1987. (F.0.0 Man hors prêt).
  8. Michael R. Garey and David S. Johnson. Computers and intractability, a guide to the theory of NP-Completeness. Freeman and Company, New York, 1979.
  9. Roger Penrose. The emperor's new mind. Vintage, Oxford University Press, 1989.

Compteur