Hay una respuesta más específica a esta pregunta que se centra en aquellos que tienen una comprensión más general de la informática teórica y quieren hacer un proyecto antes de ir a la escuela de posgrado. Y luego está el estudiante más principiante que está interesado en CS teórico, pero realmente no puede distinguirlo de otras áreas de CS.
Para el segundo estudiante (y realmente cualquier estudiante interesado en CS), recomendaría las mismas cosas que Teodoro Filippini. Hay algunas áreas matemáticas que deberían estar allí, como la teoría de conjuntos y las matemáticas discretas. Hay algunas cosas básicas en la lógica , hay conceptos algorítmicos básicos como algoritmos codiciosos , programación dinámica y recursividad.
Sin embargo, para el primer tipo de estudiante, recomendaría estudiar una o más de estas áreas con mayor detalle. Una vez que descubrí que quería estudiar CS teórico, caí en picada (¿es esa la metáfora que quiero usar?) En algoritmos. Primero, comencé a jugar con los algoritmos básicos para problemas en P, viendo cuán bien los entendía. ¿Cómo trabajan? ¿Por qué trabajan ellos? ¿Qué problema (s) resuelven? ¿Qué problema (s) no resuelven? ¿Cuáles son sus limitaciones? ¿Cómo los implementaría? ¿Hay alguna ventaja de ciertas estructuras de datos o representaciones? Entiendes la esencia.
- ¿Cómo debo estudiar combinatoria?
- Teoría de la complejidad computacional: ¿Cuál es la diferencia entre las máquinas de Turing deterministas y no deterministas?
- ¿Por qué escribimos A = IA para operaciones de fila y A = AI para operación de columna para encontrar el inverso de una matriz?
- ¿Las instancias SAT generadas por la reducción de un problema más fácil (por ejemplo, factorización de enteros) serán más fáciles en promedio que las instancias SAT aleatorias?
- ¿Qué se entiende por inversa modular de un número?
También había tomado una clase de CS teórica en este momento y había visto una introducción a NP-Completeness. Si bien no leí los documentos de Cook o Karp en la universidad, no creo que estén fuera del ámbito de la universidad.
Hay tres libros que recomiendo encarecidamente. Los dos primeros son bien conocidos y los he visto en la mayoría de las listas de lectura para el tema, Computadoras e Intractabilidad: una guía para la teoría de la integridad de NP y elementos de la teoría de la computación . Esos son los dos libros que tuve en la universidad y creo que están bien escritos e introducen los conceptos de P, NP, NP-Completeness, Turing Machines , etc. a un buen nivel.
El tercer libro que recomendaría es otro libro que utilicé, pero este fue para la escuela de posgrado. Sus algoritmos de aproximación: Vijay V. Vazirani . Este libro puede ser un poco más avanzado para un estudiante universitario (y tal vez algo así como Optimización combinatoria: algoritmos y complejidad Es un mejor enfoque). El razonamiento detrás de este (estos) libro (s) es que llegas a un punto de “ahora qué” con NP-Completeness. Si tiene un problema que ha demostrado ser NP-Complete, debe hacer algo. Los algoritmos de aproximación son un área que puede ser un poco compleja de comprender por completo para un estudiante universitario, pero pueden ser interesantes conceptos como los algoritmos de aproximación para Vertex Cover & Set Cover , esquemas de aproximación de tiempo polinomial . Esta área también (probablemente) le presentará la programación lineal (y la programación de enteros ) y el método simplex , que es un algoritmo eficiente para resolver problemas de programación lineal.
Dado que la Programación de enteros (IP) es NP-Complete, todos los problemas en NP se pueden representar como IP. Luego, la programación lineal (relajación LP) para estas IP (en lugar de exigir valores enteros para nuestras variables, permitimos números reales) se convierten en los primeros enfoques para muchos de estos problemas. Luego aprendemos sobre los teoremas de dualidad fuertes y débiles que dicen que la relajación primaria y dual de la relajación LP de un IP da límites a la solución óptima. Esto dice que también se debe investigar sobre representaciones eficientes de problemas de programación de enteros en lugar de solo algoritmos.
Esa es una rama para bajar. También hay otras técnicas en las que puede buscar obtener comprensión: búsqueda local , búsqueda tabú , programación genética , optimización de red , matrices totalmente unimodulares , teoría matroide , aprendizaje automático , etc.
Espero que esto ayude.
