CS teórico y matemáticas: recomendaciones de autoaprendizaje

14

Soy un graduado que no es CS y mi campo de estudio no está relacionado con CS. Sin embargo, como parte de un plan más amplio para convertirse en un científico de la computación, quiero obtener una sólida formación en informática teórica y matemáticas en lo que se refiere a CS. Investigué mucho y seleccioné los siguientes libros mejores / realmente buenos sobre el tema de CS y matemáticas y me gustaría pedirle su opinión sobre:

  • Compleción de los temas cubiertos (por favor, recomiende cualquier cosa que me haya perdido)
  • Superposición de material cubierto / área de exageración (recomiende libros que deberían eliminarse de la lista)
  • Orden para estudiar los libros (enumeré en el orden en que creo que deberían estudiarse)

La lista se siente excesivamente larga, por lo que agradecería las recomendaciones para eliminar algunos libros, sin la pérdida de los conocimientos básicos necesarios para CS.

Entonces, los libros son:

  1. El placer del matemático por WW Sawyer
  2. Cómo demostrarlo: un enfoque estructurado por Daniel J. Velleman
  3. Cómo resolverlo: un nuevo aspecto del método matemático por G. Polya
  4. Una introducción a la programación funcional a través del cálculo lambda por Greg Michaelson
  5. Fundamentos de la informática por Al Aho y Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
  6. Matemáticas concretas: una base para la informática por Graham, Knuth y Patashnik
  7. Introducción a la teoría de la computación por Michael Sipser
  8. Introducción a la teoría de autómatas, idiomas y computación por John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  9. Complejidad computacional: una perspectiva conceptual por Oded Goldreich
  10. Complejidad computacional: un enfoque moderno por Sanjeev Arora, Boaz Barak
  11. Un curso de combinatoria por JH van Lint, RM Wilson
  12. Computabilidad: una introducción a la teoría de la función recursiva por Nigel Cutland
  13. Computadoras e Intractabilidad: una guía para la teoría de la completitud NP por MR Garey, DS Johnson
  14. Teoría de funciones recursivas y computabilidad efectiva por Hartley Rogers
  15. Desigualdades por GH Hardy, JE Littlewood, G. Polya
  16. Lógica matemática: un curso con ejercicios (Parte I): cálculo proposicional, álgebras de bookean, cálculo predicado por René Cori, Daniel Lascar
  17. Lógica matemática: un curso con ejercicios (Parte II): teoría de la recursión, teoremas de Godel, teoría de conjuntos, teoría de modelos por René Cori, Daniel Lascar
CSLover
fuente
Consulte esta pregunta cstheory.stackexchange.com/questions/3253/…
Bartosz Przybylski
Comience con un libro de Algoritmo conocido si aún no tiene experiencia en este tema.
AJed
@Bartek: Gracias, pero esta fue una de las preguntas que miré antes para compilar la lista en primer lugar. Mi pregunta es más sobre cómo leer prácticamente todo el gran material que existe. El tiempo es siempre una limitación, por lo que quiero saber qué libros debo "no" leer para evitar repeticiones, etc.
CSLover
@AJed: ¿Estás sugiriendo comenzar con el libro # 5 en la lista en lugar de algunos de los libros de matemáticas # 1-4? Creo que # 5 da una introducción suave a los algoritmos y las estructuras de datos.
CSLover
Demasiado aquí. Solo elegiría uno y me iría, luego me preocuparía por lo que viene después cuando llegues allí. Podría recomendar que Sipser comience para un principiante que quiere una sólida formación en fundamentos de CS.
usul

Respuestas:

10

Tu lista es extremadamente problemática.

Para empezar, me saltearía los libros 6,11,12,14,15,16,17: los libros 6, 11 y 15 son matemáticas generales que realmente no son necesarias a menos que te conviertas en un investigador teórico . Los libros 12 y 14 cubren la teoría de la recursión que no es informática (¡aunque se trata de la computabilidad!). Los libros 16 y 17 cubren temas avanzados en lógica, mientras que solo necesita conocer una lógica muy básica.

De los libros 1, 2, 3, elegiría solo uno para servir como introducción general a las matemáticas y las pruebas.

Los libros 5,7,8,9,10,13 cubren varios temas: teoría de autómatas, algoritmos y teoría de la complejidad. Permítame sugerirle que siga Sipser (Libro 7) para la teoría de autómatas y la teoría de la complejidad, e Introducción a los algoritmos de Cormen, Leiserson, Rivest y Stein ("CLRS") para algoritmos.

Libro 4 ofertas con programación funcional. Si bien mi educación en informática nunca ha incluido ningún curso sobre este tema, es justo decir que muchos investigadores en informática teórica cuentan la programación funcional como parte de los fundamentos esenciales.

Resumiendo: lo que te queda es

  • Uno de los libros 1-3 (o cualquier texto comparable de "introducción a la prueba")
  • CLRS
  • Libro 4 (programación funcional)
  • Libro 7 (teoría de autómatas y teoría de la complejidad)
Yuval Filmus
fuente
Muchas gracias por una respuesta tan completa. Sabía que la lista era excesiva, pero al leer todo tipo de recomendaciones de libros para informáticos, terminas con una larga lista. Su recomendación es muy práctica, y eso es lo que busco. ¡¡Muchas gracias!!
CSLover
1
No estoy de acuerdo con el consejo de que "las matemáticas no son necesarias". Elija cualquier aspecto de la informática y le mostraré cómo se necesitan las matemáticas. Cuantas más matemáticas aprendas, mejor te irás. Por otro lado, es casi imposible aprender matemáticas reales por sí mismo, sin ir a la escuela. Por lo tanto, probablemente sea mejor concentrarse en informática, que es más fácil de aprender.
Andrej Bauer
5

También puede considerar aprovechar algunos de los muchos cursos en línea disponibles. Por ejemplo, tanto Stanford como el MIT ofrecen cursos en línea (gratuitos) en informática, y creo que también hay muchos otros disponibles.

En lo que respecta a los libros, apoyo la mayoría de las recomendaciones de Yuval, excepto que CLRS es una gran referencia, pero un poco abrumador como libro introductorio para simplemente sentarse y leer. Para un primer paso en la porción de algoritmos, podría recomendar Algorithms de Dasgupta et al. . El enlace anterior es a la preimpresión en línea gratuita, pero también es bastante barato comprar en rústica.

Joe
fuente
Okay. Le agradezco su respuesta. Muchas gracias.
CSLover
2

Las referencias que sugieres serían un "muy" científico teórico de la computación. pero honestamente no encuentro ningún beneficio al leer todos estos libros si eres de un título que no es CS. Por supuesto, todo depende de lo que necesite.

Encuentro que algunos libros como el Libro 14, 15, 16, 17 no están destinados a informáticos. El libro 3 es detallado. Es solo general para cualquier estudiante. Por lo tanto, supongo que los libros 1 y 2 son iguales.

Para mí, estando en su misma situación que no era originalmente un informático (sino un ingeniero eléctrico / informático), propongo dos direcciones iniciales:

  • diseño y análisis de algoritmos, (muchas personas sugieren la Introducción a los Algoritmos de CLRS . Es una gran referencia, pero realmente no soy fan de ella e inicialmente fue una apuesta más difícil de entender y, a veces, muy detallada. Sugiero que siga su tabla de contenido y, desde allí, consulte los cursos en línea para obtener referencias más claras).

--- asegúrese de dominar un lenguaje de programación para IMPLEMENTAR los algoritmos y las estructuras de datos que aprende; por lo tanto, sugiero la serie de Algoritmos, de Sedgewick (¡increíble!)

--- AGREGADO: También sugiero este libro: Algoritmos combinatorios: generación, enumeración y búsqueda por D. Kreher. Este es un libro muy bonito. Le dará una perspectiva diferente a muchos problemas en los algoritmos.

  • combinatoria (especialmente teoría de grafos), un curso de combinatoria por JH van Lint, RM Wilson , es bueno. Existen muchas otras referencias. Por lo general, cualquier libro de combinatoria conocido es suficiente; todo lo demás se obtendría de referencias adicionales de Internet. Personalmente me gustó: combinatoria de peter j cameron y Bondy y Murty Graph Theory.

  • Una apuesta de probabilidad (siempre necesaria). Llama la atención que muchos campos de la ciencia no utilizan la probabilidad. Pero créeme, todo lo que tienes que saber son los conceptos básicos.

Luego: muchos investigadores que se autodenominan científicos teóricos de la informática se centran tanto en la teoría de la computación (automota y otros). Hay algunos buenos libros para esto (ver la publicación de Yuvul Filmus),

Aho y Ullman son buenos (en realidad todos los libros de Ullman son buenos). Póngase cómodo con el diseño del compilador (consulte http://infolab.stanford.edu/~ullman/ullman-books.html ).

Después de eso: todo depende de lo que quieras hacer. Diferentes direcciones que puede tomar: 1) bases de datos, 2) reconocimiento de patrones y minería de datos, 3) algoritmos distribuidos, 4) bases de lenguajes de programación, 4) algoritmos aleatorios y muchos otros. [cada una de las cuales requiere otra publicación] ¡ pero trata de tener una idea sobre todo!

* La idea general: si eres nuevo en CS, entonces siéntete cómodo con tantos subdominios de CS como sea posible. ¡Restringirse a la "teoría" le hará perder gran parte de la creatividad CS! * (mi opinión)

AJed
fuente
Para mí programación funcional. No use un libro heredado como el que citó. Los lenguajes funcionales se requieren actualmente en la industria. Existen algunos tutoriales en Internet sobre idiomas como Scheme, Haskel y Erlang. No te pongas muy teórico, este es mi consejo.
AJed
Todos los buenos comentarios. Mi objetivo es diseñar un programa de autoaprendizaje completo y esta pregunta solo se ocupa de una sección del programa, que pensé que era la más difícil de organizar. Otras áreas incluyen: estructuras y algoritmos de datos, arquitectura de computadoras, sistemas operativos, redes, seguridad y criptografía, paralelismo, métodos formales, inteligencia artificial, gráficos y simulación, bases de datos, lenguajes de programación, compiladores, ingeniería de software y finalmente filosofía y administración de Unix. Creo que la mayoría de estos son bastante fundamentales para CS, pero
merecerían
Su mejor truco es una base sólida en el diseño y análisis de algoritmos. - cualquier otro campo es un subcampo de diseño y análisis de algoritmos.
AJed
¿Sería amable y aclararía qué libro de algoritmos de Sedgewick me recomendó? Tiene uno llamado "Algoritmos", pero no es una serie. También tiene "Algorithms in C ++" (u otros lenguajes), que creo que son 2 libros con un total de 5 partes.
CSLover
El que usé fueron los de C ++. Sin embargo, los usé como referencias. Este es su sitio web cs.princeton.edu/~rs
AJed