Solicitud de sugerencia: ¿Libro accesible y completo sobre informática?

Sería difícil comprender la complejidad computacional a cualquier profundidad sin comprender los algoritmos. De muchos libros sobre algoritmos, uno que es razonablemente accesible, pero también conceptualmente profundo, es “Algorithms” de Dasgupta, Papadimitriou y Vazirani. Los autores son los mejores investigadores en complejidad computacional, y el libro cubre bien las ideas básicas. El libro no está particularmente interesado en la implementación de algoritmos en algún lenguaje de programación práctico, pero eso solo sería una preocupación para usos prácticos.

El libro de Michael Sipser “Introducción a la teoría de la computación” (sugerido en varias respuestas) podría ser el siguiente paso, pero no es tan accesible como el libro de Dasgupta et al.

Ciertamente no recomendaría el TAOCP de cuatro volúmenes de Knuth a un principiante. Siempre que alguien lo recomiende, pregúnteles qué fracción han leído y cuántos ejercicios han resuelto. TAOCP es una gran fuente de referencia para las personas que conocen el campo y tienen cierta intuición al respecto. Para la mayoría de los principiantes de hoy, puede parecer una guía telefónica escrita en un idioma extranjero. Ah … y el cuarto volumen aún no está terminado. Por favor, no me malinterpreten, tengo los tres volúmenes en mi oficina, y este es un gran trabajo. Pero probablemente no sea muy útil para principiantes.

Cuando era estudiante universitario, disfruté la “Introducción a la teoría de la computación” de Sipser. Cubre todos los temas básicos de la teoría de la complejidad de una manera muy fácil y accesible; por ejemplo, todas las pruebas en el libro están precedidas por una breve explicación informal de la idea de la prueba.

Advertencia: el libro de Sipser es realmente un libro de matemáticas, lo que significa que está escrito en un estilo a prueba de definición de teorema, pero, de nuevo, el campo de la complejidad computacional en sí es realmente un subcampo de las matemáticas. Así que complementaría este libro con un libro sobre estructuras de datos y algoritmos. El libro que recomienda Igor Markov parece agradable, y también parece que (o al menos un borrador) está actualmente disponible gratuitamente: http://www.cs.berkeley.edu/~vazi …

EDITAR: Acabo de darme cuenta de que publiqué una copia casi exacta de la respuesta de Kevin Lin. Bueno, espero que eso te convenza de que son grandes libros.

Como usted lo solicitó, quería publicar una respuesta que estaba en violento acuerdo con el Prof. Markov con su recomendación de Dasgupta y los algoritmos de la compañía . Como persona con experiencia en física y matemáticas, no he encontrado un libro de algoritmos que explique más claramente todos los algoritmos interesantes y su complejidad de una manera significativa que también lo mantenga intuitivo y motivado. Su explicación de la FFT fue lo que me ayudó a entender cómo funcionaba (y escribí una respuesta sobre Quora con mis notas de ese libro). Menciono mis antecedentes porque cuando comencé no me importaban todos los detalles sobre cada algoritmo y estructura de datos, solo quería algo que fuera agradable de leer y me diera suficientes cosas para masticar. Leer Introducción a Algos por CLRS fue exactamente lo contrario de esto.

Otro libro que realmente me gustó fue Introducción de Sipser a la teoría de la computación , principalmente porque era breve pero también porque era claro.

Es difícil especificar qué es “analógico” aquí. Pero la “nueva mente del emperador” del mismo autor contiene un capítulo sobre la teoría de autómatas finitos + bastante matemática. Esto puede considerarse relacionado con las ciencias de la computación.

Si está buscando un punto de entrada, sugeriría “Algorithmics: The Spirit of Computing” de David Hare. Está muy bien escrito y explica todos los conceptos fundamentales en informática. Es algo análogo a “Road to Reality” y te dejará con ganas de saber más.

No comience de inmediato con “El arte de la programación de computadoras”. El único volumen de este libro puede desanimarte. Lo compararía con The Feynman Lectures on Physics, un viaje para un semi-especialista que es extremadamente interesante pero que podría ser demasiado para un novato.