¿Cuáles son las pruebas más importantes que uno debe estudiar en el campo de la informática teórica?

Cuando se le invita a una entrevista para ingresar a un programa de posgrado en informática teórica, lo primero que debe construir es la base matemática necesaria. Esto incluye los conceptos básicos de teoría de números, álgebra lineal y algunos otros conceptos básicos de matemática discreta.
Probablemente tendría el conocimiento requerido de estos temas de la escuela secundaria, cursos de pregrado o tal vez debido a la preparación para un examen de ingreso a nivel nacional que lo llevó a la entrevista de admisión. Pero es esencial repasar estos temas, no solo porque podría llevarlo a una entrevista exitosa, sino más importante porque lo acompañará a lo largo de su experiencia de posgrado en informática teórica.

En términos de pruebas, es posible que desee profundizar con las pruebas teóricas de números generales, como el pequeño teorema de Fermat, el algoritmo euclidiano, etc. Una vez que haya hecho estas pruebas, le resultará más fácil estudiar y comprender los conceptos de los siguientes subtemas básicos. áreas de informática teórica.
1. Teoría de autómatas: esto incluiría todas las pruebas relacionadas con la estructura de DFA, NFA, gramáticas libres de contexto, expresiones regulares y su interdependencia con problemas computacionales.
2. Teoría de la computabilidad: esto requeriría que comprenda el modelo de las máquinas de Turing y su relación con la capacidad de decisión y la indecidibilidad. Las pruebas importantes incluirían el teorema de detención y la prueba de la indecidibilidad de varios lenguajes descritos en términos de los modelos computacionales de DFA, NFA, etc.
3. Teoría de la complejidad computacional: Esto incluiría la pregunta más comentada en informática, que es la pregunta P vs NP. Y esto incluiría pruebas de complejidades en el tiempo y el espacio, que demuestren la integridad de NP de ciertos problemas conocidos y que presenten algoritmos no triviales para problemas de NP difíciles conocidos, como vendedor ambulante, isomorfismo gráfico, satisfacción, etc.

Una vez que haya completado las pruebas formales matemáticas necesarias, ya tiene la competencia necesaria para resolver un nuevo problema algorítmico, que es lo que puede esperar en su entrevista. El panel de la entrevista estaría interesado en ver cómo aborda un problema desconocido, desde cero.

También refiérase a varios blogs que han puesto sus experiencias, o hable con personas mayores que tendrían experiencias de primera mano de tales entrevistas.
¡La mejor de las suertes!