Introducción a la Teoría de la Computación – Michael Sipser – 1ra Edición

La filosofía de Michael Sipser al escribir este libro era simple: hacer el tema interesante y relevante, y que los estudiantes aprenderán. Su énfasis unificador en la teoría de la informática – en lugar de ofrecer una colección de detalles de bajo nivel – establece este libro aparte, al igual que sus explicaciones intuitivas.

A lo largo del libro, Sipser – una autoridad conocida en la teoría de la computación – construye el conocimiento de los estudiantes con las herramientas conceptuales utilizadas en la informática, con el sentido estético que necesitan para crear sistemas elegantes, y la capacidad de pensar a través de problemas por sí mismos.

Introducción a la Teoría de la Computación ofrece un tratamiento matemático de la teoría de la computación basada en teoremas y demostraciones. Las pruebas se presentan con un componente “idea de prueba” para revelar los conceptos que sustentan el formalismo. Los algoritmos se presentan usando la prosa en vez de pseudocódigo para centrar la atención en los algoritmos de sí mismos, y no en modelos de cálculo específicos.

La cobertura de temas, la terminología, y el orden de presentación son tradicionales para un curso de nivel superior en la teoría de la informática. Los lectores estarán interesados ​​en observar varios capítulos sobre la teoría de la complejidad: el capítulo 8 de la complejidad del espacio; Capítulo 9 sobre intratabilidad demostrable, y en el capítulo 10 sobre temas avanzados, incluyendo algoritmos de aproximación, la alternancia, sistemas de demostración interactiva, criptografía y la computación paralela.