Lista de libros de introducción de TCS para aquellos que no saben mucho sobre TCS [cerrado]
10
Si tiene que recomendar libros para alguien que quiera aprender más sobre TCS a nivel introductorio, como teoría de autómatas, algoritmos, teoría de complejidad, etc., ¿qué libro (s) recomendaría para aquellos que estén interesados y quieran aprender más sobre TCS, pero no tuvo ninguna exposición?
@Gigili No. Las listas de libros solían ser CW, pero eso ya no se hace. Lea la publicación del blog que he vinculado.
Gilles 'SO- deja de ser malvado'
Respuestas:
9
Si desea tener una introducción general sin profundizar en los detalles técnicos, le sugiero Algorithmics: The Spirit of Computing de David Harel . Después de eso, esta es mi lista favorita:
Algoritmos de S. Dasgupta, CH Papadimitriou y UV Vazirani: la introducción más intuitiva a los algoritmos con un enfoque más fuerte en la intuición que las pruebas técnicas.
Programming Pearls de Jon Bentley : este no es un libro de texto sobre algoritmos, pero demuestra maravillosamente cómo usar técnicas de diseño de algoritmos para resolver problemas reales que irritan a los programadores reales. :-) Esto podría ser un buen comienzo si tienes algunos conocimientos previos sobre programación.
DPV aún no está impreso; ¿Es generalmente conocido?
Raphael
Debido a la puntuación de esta respuesta, incluí las respuestas en una respuesta agregada . Considere eliminar su respuesta en aras de la claridad.
Raphael
@Raphael DPV ha estado impreso durante varios años, pero todavía está muy bien disponible en línea. Traté de no vincularme a sitios web comerciales como Amazon.
Dai
@Dai: Ya veo. La página a la que enlaza dice "Este es un penúltimo borrador de nuestro libro de texto que aparecerá pronto", por lo tanto, mi confusión.
Raphael
7
Introducción a los algoritmos de Cormen, Leiserson, Rivest, Stein es una opción popular, el título habla por sí mismo.
El libro de Clarke me parece demasiado pesado para alguien sin experiencia en TCS. Conozco (en persona) estudiantes de doctorado que encuentran el libro difícil de entender.
Dai
@Dai, probablemente tengas razón, lo he cambiado a Principios de verificación de modelos de Baier
Daniil
¿Se puede entender la comprobación de modelos sin conceptos básicos en lógica y / o autómatas?
Raphael
1
El Libro del Dragón es ciertamente una buena referencia; ¿Es lo suficientemente teórico? (Sinceramente, no sé)
Raphael
@Raphael "Principios" de alguna manera da una introducción a la lógica (al menos algunos conocimientos necesarios) y autómatas. Es un libro bastante grande también, ~ 980 páginas. En cuanto a The Dragon Book, pensé que los compiladores son un área bastante teórica, ¿no?
Daniil
6
Para las matemáticas necesarias en el análisis de algoritmos, recomiendo el único GKP:
Matemáticas concretas por Graham, Knuth, Patashnik
Un tratamiento integral y de alta calidad de prácticamente todas las matemáticas que necesitará en algoritmos (básicos). Es una lectura entretenida e incluye una gran cantidad de ejercicios (y soluciones).
Intenté leer este libro, pero no me gustó, porque todo se sentía muy ... torpe y agrupado. Simplemente no sentí la belleza de las matemáticas allí. Compare eso con el resumen de la teoría de autómatas de Sipsers o los libros de lógica de Smullyan o incluso el álgebra abstracta de Dummit & Foote. Tal vez solo soy yo, aunque.
Daniil
Yo segundo Daniil. Es una colección de excelentes herramientas para teóricos. Pero es demasiado seco y técnico para que los principiantes lo disfruten. Realmente me gustan los libros que mencioné anteriormente, ya que parecen tener sus propias almas. Leen como si alguien te contara historias interesantes.
Dai
Desafortunadamente, no cubre la inducción estructural, la coinducción, la teoría de dominios y todo lo necesario para el TCS de estilo B de teoría.
Dave Clarke
@DaveClarke: Correcto. No estoy seguro de esperar que algún libro de matemáticas contenga nada de eso. Pero entonces, se supone que GKP es un libro de matemáticas cs. Tampoco contiene lógicas, por lo que debería reformular un poco.
Raphael
2
@DaveClarke, ¿podría recomendarnos algunos libros sobre matemáticas de la Teoría B?
Me encantaría tener TAoCP en la lista, pero me temo que el enfoque meticuloso de Don Knuth no es nada que pueda considerarse como "introductorio". Tristemente...
Logicomix es ciertamente una joya, sin decir que los demás no lo son.
Dave Clarke
Realmente no me gusta la forma en que Logicomix retrató a los lógicos como personas "locas". Las ideas en lógica, cuando se explican de la manera correcta, son muy sencillas y sencillas, y no son realmente tan "dementes".
Dai
1
@Dai Eche un vistazo a la vida de personas extraordinarias como, por ejemplo, Gödel, Wittgenstein, Nash, etc., fueron ... muy extraordinarias.
uli
¿Cuál de ellos es realmente a prueba de principiantes?
Raphael
@Raphael en mi humilde opinión todos ellos, de lo contrario no los habría publicado aquí. Algunos pueden tener una curva de aprendizaje empinada, pero creo que está bien.
uli
4
Si usted es completamente nuevo en el campo de TCS, la Introducción a la teoría de la computación de Sipser es definitivamente el mejor libro para comenzar. He leído otros libros introductorios, y ninguno de ellos, en mi opinión, se acerca a la forma en que Sipser aborda el asunto.
Otros libros teóricos más específicos y buenos son:
@DaveClarke Estaba planeando agregar más recursos a la lista como lo hice ahora con mi edición, ¡pero también quería enfatizar cuán genial es el libro de Sipser al mencionarlo nuevamente! :-)
codd
1
El libro de Pierce es una joya. Ojalá hubiera existido cuando hice mi doctorado (en tipos).
Dave Clarke
@DaveClarke Actualmente lo estoy usando para mi tesis de licenciatura por recomendación de mi asesor y también estoy muy impresionado.
codd
1
Gracias por la referencia, lo echaré un vistazo más tarde hoy. Veo que usted es profesor en KUL, vendré allí el próximo año para estudiar Secure Software (software Veilige). Qué mundo tan pequeño.
codd
3
Algunos buenos libros que cubren la parte de la Teoría B de TCS:
Lógica en CS : lógica en informática: modelado y razonamiento sobre sistemas Por Michael Huth y Mark Ryan.
Amplia cobertura de diversos usos de la lógica en informática. Alrededor del tercer año de pregrado.
El cálculo lambda : cálculo lambda y combinadores. Una introducción de J. Roger Hindley y Jonathan P. Seldin.
Presenta el cálculo lambda, que es un ingrediente esencial en los fundamentos de los lenguajes de programación. Alrededor del tercer año de pregrado.
Diríjase a la teoría de dominios : Introducción a los enrejados y el orden (2ª ed.) Por Davey, BA y Priestley, HA Cambridge University Press. (2002)
Cubre un tema muy útil, especialmente si planea trabajar con semántica. Es un poco más matemático que los otros temas, pero los primeros capítulos están ciertamente en un nivel universitario avanzado.
Semántica : semántica con aplicaciones: un aperitivo de Hanne Riis Nielson y Flemming Nielson.
Una muy buena introducción a la semántica del lenguaje de programación. En lugar de profundizar en un formalismo particular, ofrece una presentación amplia e incluye aplicaciones que generalmente no se consideran en otros libros sobre semántica. Posiblemente podría ser útil para estudiantes de segundo año.
No conozco a ninguno de ellos ni siquiera por reputación, así que no puedo decir si son buenos (aunque me inclino a tomar tu palabra). : /
Raphael
1
He agregado una descripción de cada libro. Todos estan bien.
Dave Clarke
3
Esta es una respuesta agregada que contiene libros de respuestas con puntaje de al menos cinco. Discuta su contenido en el chat .
Algoritmos y Estructuras de Datos
Introducción a los algoritmos por Cormen, Leiserson, Rivest, Stein (3ª ed. 2009)
Un tratamiento integral de algoritmos básicos y estructuras de datos y su análisis sin profundizar demasiado.
Algoritmos de Dasgupta, Papadimitriou, Vazirani (2006)
La introducción más intuitiva a los algoritmos con un enfoque más fuerte en la intuición que las pruebas técnicas.
Principios de verificación de modelos por Baier, Katoen (2008)
Libro masivo que se puede utilizar como una introducción integral a la verificación de modelos.
Programming Pearls por Jon Bentley (2ª ed. 1999)
No es un libro de texto sobre algoritmos, pero demuestra maravillosamente cómo usar técnicas de diseño de algoritmos para resolver problemas reales. Podría ser un buen comienzo si tienes algún conocimiento previo sobre programación.
Esto no responde la pregunta, o si está destinado a hacerlo, no es una buena respuesta. ¿Quieres decir que alguien que comienza TCS necesita leer todos estos libros? Si no, ¿cómo elegirían? Tenga en cuenta que, según su regla, es probable que esta respuesta crezca para contener cientos de libros
Gilles 'SO- deje de ser malvado'
@Raphael ¿Es cortés pedirle a alguien que elimine su propia respuesta? Por lo general, el autor de la pregunta puede hacer el trabajo de agregar sus respuestas favoritas modificando su propio texto de pregunta, pero nunca he visto a nadie obligar a otra persona a eliminar su propia publicación para crear su propia respuesta. Este cs stackexchange se está volviendo extraño con estos comportamientos narcisistas.
Dai
@Raphael: Convertirlo en CW no hace correcto pedirle a alguien que elimine su propia respuesta. Es como decir que voy a escribir un libro / encuesta (que publicaré en línea de forma gratuita), así que doy vueltas y les pregunto a todos los autores cuyos documentos cito que retiren sus propios documentos para evitar confusiones.
Dai
@Raphael No veo ningún lugar en las licencias CC que diga que mi trabajo será finalmente solicitado por alguien más. No sé qué tipo de fantasía tienes con SE, pero definitivamente no es Wikipedia. Sé que trabajas duro para "moderar" este sitio web, pero también respeta la libertad de expresión y privacidad de otra persona, y simplemente deja que los votos arriba / abajo se encarguen del resto. Creo que el objetivo de cs SE es proporcionar un foro más amigable que cstheory SE para principiantes, pero el micro nivel de gestión que propuso aquí lo hizo mucho peor.
Respuestas:
Si desea tener una introducción general sin profundizar en los detalles técnicos, le sugiero Algorithmics: The Spirit of Computing de David Harel . Después de eso, esta es mi lista favorita:
fuente
fuente
Para las matemáticas necesarias en el análisis de algoritmos, recomiendo el único GKP:
Matemáticas concretas por Graham, Knuth, Patashnik
Un tratamiento integral y de alta calidad de prácticamente todas las matemáticas que necesitará en algoritmos (básicos). Es una lectura entretenida e incluye una gran cantidad de ejercicios (y soluciones).
fuente
Algoritmos 4. Edición R. Sedgewick
Una Introducción al Análisis de Algoritmos P. Flajolet, R. Sedgewick
Introducción a la teoría de los autómatas, los idiomas y la computación JE Hopcroft, JD Ullman, (R. Motwani)
La primera edición de 1979 tiene más resultados teóricos que faltan en la segunda edición de 2001. No he mirado al tercer Ed todavía.
Introducción a la teoría del lenguaje formal MA Harrison
Es de 1978 pero todavía me gustaría verlo en la lista.
Logicomix: una búsqueda épica de la verdad A. Doxiadis, CH Papadimitriou ¡
Porque es totalmente increíble!
Nuevamente
, Computadoras e Intractabilidad de Garey y Johnson de 1979 : una guía para la teoría de la integridad de NP
Me encantaría tener TAoCP en la lista, pero me temo que el enfoque meticuloso de Don Knuth no es nada que pueda considerarse como "introductorio". Tristemente...
fuente
Si usted es completamente nuevo en el campo de TCS, la Introducción a la teoría de la computación de Sipser es definitivamente el mejor libro para comenzar. He leído otros libros introductorios, y ninguno de ellos, en mi opinión, se acerca a la forma en que Sipser aborda el asunto.
Otros libros teóricos más específicos y buenos son:
fuente
Algunos buenos libros que cubren la parte de la Teoría B de TCS:
Lógica en CS : lógica en informática: modelado y razonamiento sobre sistemas Por Michael Huth y Mark Ryan.
Amplia cobertura de diversos usos de la lógica en informática. Alrededor del tercer año de pregrado.
El cálculo lambda : cálculo lambda y combinadores. Una introducción de J. Roger Hindley y Jonathan P. Seldin.
Presenta el cálculo lambda, que es un ingrediente esencial en los fundamentos de los lenguajes de programación. Alrededor del tercer año de pregrado.
Diríjase a la teoría de dominios : Introducción a los enrejados y el orden (2ª ed.) Por Davey, BA y Priestley, HA Cambridge University Press. (2002)
Cubre un tema muy útil, especialmente si planea trabajar con semántica. Es un poco más matemático que los otros temas, pero los primeros capítulos están ciertamente en un nivel universitario avanzado.
Semántica : semántica con aplicaciones: un aperitivo de Hanne Riis Nielson y Flemming Nielson.
Una muy buena introducción a la semántica del lenguaje de programación. En lugar de profundizar en un formalismo particular, ofrece una presentación amplia e incluye aplicaciones que generalmente no se consideran en otros libros sobre semántica. Posiblemente podría ser útil para estudiantes de segundo año.
fuente
Esta es una respuesta agregada que contiene libros de respuestas con puntaje de al menos cinco. Discuta su contenido en el chat .
Algoritmos y Estructuras de Datos
Un tratamiento integral de algoritmos básicos y estructuras de datos y su análisis sin profundizar demasiado.
La introducción más intuitiva a los algoritmos con un enfoque más fuerte en la intuición que las pruebas técnicas.
Computabilidad y Complejidad
La mejor introducción a la teoría, la computabilidad y la complejidad de los autómatas.
Idiomas formales y autómatas
El libro estándar sobre compiladores; Muy completo. Toca también la teoría de autómatas.
Teoría aplicada
Libro masivo que se puede utilizar como una introducción integral a la verificación de modelos.
No es un libro de texto sobre algoritmos, pero demuestra maravillosamente cómo usar técnicas de diseño de algoritmos para resolver problemas reales. Podría ser un buen comienzo si tienes algún conocimiento previo sobre programación.
fuente