Matemáticas para TCS major

10

Estoy buscando una especialización en Informática Teórica; específicamente, estoy interesado en la teoría de la complejidad y la teoría probabilística de autómatas. Al graduarme en un año, ¿qué cursos avanzados de matemáticas (como la teoría de Galois o el análisis armónico, por ejemplo) crees que serían útiles para tomar en los próximos dos semestres? ¿Por qué?

complexity-theory automata education ADR
fuente
2
Ver pregunta relacionada .
Nicholas Mancuso
1
También revise los requisitos del curso en su escuela , así como preguntas similares sobre Ciencias de la Computación Teórica (por ejemplo, esto o esto ). Estoy tentado de cerrar este aquí como un duplicado; También está bastante localizado.
Raphael
66
¡Toma TODAS las matemáticas!
JeffE
2
@JeffE Toma ... todas las matemáticas?
MrGomez
2
Todas las matemáticas en el juego de herramientas de un teórico .
Chao Xu

Respuestas:

2

(Un resumen de los comentarios a las preguntas)

prácticamente cualquier área de las matemáticas podría ser importante en TCS, por lo que debe hacer lo mejor para fortalecer su formación matemática. Cualquier herramienta que aprenda es una ganancia, y puede emplearse en algún campo (sub) de TCS.


Esta pregunta también fue respondida en otros SE, y se pueden encontrar detalles muy informativos en:

  1. qué tipo de fondo matemático es necesario para la teoría de la complejidad
  2. ¿Ejemplos de matemáticas "no relacionadas" que juegan un papel fundamental en TCS?
  3. ¿Qué cursos de matemáticas debo tomar para prepararme para una maestría o doctorado en CS?
Ran G.
fuente
1
Totalmente en desacuerdo con esta declaración general. De hecho, la gran mayoría de las áreas de las matemáticas no son útiles para la informática teórica. Diga análisis funcional, teoría de conjuntos (por ejemplo, forzamiento), topología, geometría algebraica (no, GCT no cuenta), ecuaciones diferenciales, y la lista podría seguir y seguir. El tema matemático más importante es la teoría de la probabilidad (incluso eso depende del tipo de TCS que esté haciendo). Aparte de eso, algunos conocimientos muy básicos en algunas áreas, por ejemplo, la teoría de grupos.
Yuval Filmus
@ Yuval, creo que esto es un poco corto de vista. ¿Quién pensó que las transformaciones de Fourier pueden ser tan útiles para TCS (antes de la gloria que logró cuando se usó para PCP, etc.) ) ... Creo que se pueden usar muchos otros métodos para TCS y seguramente para CS en general ... Es cierto, no todos los métodos son igualmente importantes, y esperaba que este hilo se convirtiera en una lista de métodos / aplicaciones, donde la mayoría métodos importantes obtendrían los votos más altos.
Ran G.
Las transformadas de Fourier son conceptos muy elementales. No necesita comprender el núcleo Fejer en TCS. En cuanto a los SDP, provienen de la investigación de operaciones (u optimización convexa, si lo prefiere). Es cierto que algunas cosas pueden ser útiles. Por ejemplo, encontré mi experiencia en C muy útil, y Virginia Williams encontró su experiencia en Maple muy útil. En términos de su carrera, escribir y hablar en público también son muy útiles. Todos estos son probablemente más útiles que un curso sobre teoría combinatoria de conjuntos. ¿Por qué no decirle a la gente que estudie estas materias en lugar de cursos de matemáticas al azar?
Yuval Filmus
1
@YuvalFilmus No entiendo: el principio de invariancia MMO es una generalización estricta de Berry-Esseen. Tampoco estoy de acuerdo con tu punto más amplio. Una gran cantidad de TCS puede usar la probabilidad hasta un límite de Chernoff. Pero el lema JL, la concentración de la medida en ARV, el teorema de Dvoretzky para la detección comprimida, la desigualdad de Grothendieck para aproximar la norma de corte son solo algunos ejemplos muy exitosos de que FA es útil en TCS. sí, el enfoque principal de los dos campos es diferente, pero las intersecciones van más allá de "las primeras 10 páginas" y hacen que valga la pena aprender matemáticas.
Sasho Nikolov
1
Además, aunque nuestras aplicaciones generalmente nos permiten mantener (variantes de) resultados que pueden describirse y a menudo demostrarse de manera elemental, el contexto más amplio proporciona intuición (CLT es una gran heurística, por ejemplo). y dado que es difícil saber qué es útil hasta que necesite usarlo, no me importaría tomar algunos cursos de matemáticas además de leer grupos en TCS que lo ayuden a aprender lo que ya se sabe que es útil. Hace poco encontré un resultado FA (que casi nunca se usa en TCS afaik) como la clave de un problema en el que estaba trabajando
Sasho Nikolov