Contenu du cours:
(Ceci est un "guideline" susceptible d' être modifié).
-
Langages récursivement énumérables, machines de Turing;
-
Calculabilité, hypothèse de Church-Turing, machine de Turing
universelle, réduction;
-
Complexité et classes de complexité, hiérarchie des
langages, rapports entre mesures de complexité;
-
Problèmes NP-complets, classes polynomiales: P et
NP,réduction bornée.
Séries d'exercices:
Les anciennes séries d'exercices sont disponibles
[ici]
Bibliographie:
-
Olivier Biberstein and José Rolim, Eléments
d'informatique théorique. Université de Genève,1997.
-
John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory,
languages and computation. , Addison-Wesley, 1979.
-
Michael Sipser. Introduction to the theory of computation. PWS Publishing
Company, Boston, 1997. (F.0.0 Sip hors prêt).
-
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).
-
Christos H. Papadimitriou, Complexity.
-
Bovet Crescenzi, Introduction to complexity theory
-
Dino Mandriolo and Carlo Ghezzi. Theorical foundations of computer science.
John Wiley & Sons, New York, 1987. (F.0.0 Man hors prêt).
-
Michael R. Garey and David S. Johnson. Computers and intractability,
a guide to the theory of NP-Completeness. Freeman and Company, New York, 1979.
-
Roger Penrose. The emperor's new mind. Vintage, Oxford University
Press, 1989.