Modelos Avanzados de Computación
Computabilidad y Complejidad Computacional

  El problema de la parada

  Máquinas de Turing

  Reducciones

  Problemas NP-completos

  Clases de complejidad

Bibliografía recomendada

	Cristopher Moore & Stephan Mertens: The Nature of Computation Oxford University Press, 2011 ISBN 0199233217 http://www.nature-of-computation.org/
	Sanjeev Arora & Boaz Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2009 ISBN 0521424267 http://theory.cs.princeton.edu/complexity/

Bibliografía complementaria

	Michael Sipser: Introduction to the Theory of Computation Cengage Learning, 3rd edition, 2012 ISBN 113318779X
	Christos H. Papadimitriou: Computational Complexity Addison-Wesley, 1994 ISBN 0201530821
	Martin D. Davis, Ron Sigal & Elaine J. Weyuker: Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science Morgan Kaufmann, 2nd edition, 1994 ISBN 0122063821
	John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation Prentice Hall, 3rd edition, 2006 ISBN 0321455363 http://infolab.stanford.edu/~ullman/ialc.html
	Michael R. Garey & David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness W. H. Freeman, 1979 ISBN 0716710455