Hay toneladas de ejemplos de métodos continuos en TCS, así como casi cualquier otra área de la informática también. Aquí hay algunos ejemplos que puedo tomar de la parte superior de mi cabeza, ¡pero hay muchos otros!
Informática teórica
Una aplicación cercana a mis intereses es el uso de métodos continuos en la búsqueda de una resolución a la conjetura de los juegos únicos. Esto tiene todo tipo de aplicaciones en la teoría de algoritmos de aproximación y pruebas probabilísticamente comprobables (que pueden ser de inters
La idea aquí es que estamos interesados en un cierto tipo de problema de satisfacción de restricciones en los gráficos. Tenemos un objeto discreto, pero lo que se notó es que podemos aprender mucho sobre la naturaleza de estas restricciones al observar los espectros de los gráficos. En esencia, resolvemos la ecuación de Laplace, [matemática] \ Delta u = 0 [/ matemática] en el gráfico y las soluciones nos permiten “escuchar” las propiedades de estas restricciones. (Esto se reduce a cálculos matriciales en la versión discretizada pero la “filosofía” es continua “)
- ¿Qué habilidades de obtener un título en Informática fueron útiles? ¿Y qué habilidades no fueron útiles?
- ¿Qué haces como estudiante de licenciatura y posgrado en informática en el MIT (aprender o investigar)?
- ¿Le importan las profesiones de programación / informática si fuma marihuana?
- ¿Cuáles son los nuevos campos emergentes en informática?
- A partir de 2016/2017, ¿qué lenguaje de programación sería mejor aprender y dominar desde el punto de vista profesional?
Dado que usted proviene de un fondo de probabilidad y estadísticas, también puede pensar en los problemas de satisfacción de restricciones como distribuciones de probabilidad en gráficos. Y luego obtienes todo tu conjunto de herramientas de probabilidad, todas tus estimaciones favoritas se traducen en declaraciones sobre gráficos, problemas y complejidad. Consulte algunos de estos documentos para obtener más información:
- Página sobre Cornell
- Página sobre Arxiv
- Página sobre Mit
Es mi creencia personal que los métodos continuos continuarán impulsando la investigación en TCS. Muchas personas buscan temas esotéricos como la geometría algebraica para probar una solución para P = NP, por lo que está eligiendo un buen momento para involucrarse.
Algoritmos
No sé cuánto CS sabes, pero aquí hay una analogía. Si usted es un ingeniero informático que diseña un sistema, hay dos herramientas principales que tiene a su disposición: indirección y almacenamiento en caché. Si está familiarizado con el sistema operativo y el diseño del sistema distribuido, verá estos principios por todas partes. En el mundo de los algoritmos tenemos nuestros análogos: aproximación y aleatorización.
Lo que generalmente hace que los estudiantes de algoritmos provenientes de CS puro no sean los algoritmos en sí, sino su análisis. Eso es porque el factor determinante son los métodos continuos. Si proviene de la probabilidad y el análisis, los métodos [matemática] \ epsilon- \ delta [/ matemática] le resultarán familiares y no tendrá problemas para demostrar que un algoritmo es una [matemática] (1+ \ epsilon) [/ matemática] -aproximación al óptimo. Si viene del mundo de la probabilidad, las estimaciones utilizadas para establecer que su algoritmo es correcto con probabilidad [matemática] (1- \ delta) [/ matemática] le resultarán familiares.
Esta es una idea muy importante en algoritmos. En la industria, los tiempos de ejecución como [math] \ Omega (n ^ 3) [/ math] no son prácticos para ejecutarse en grandes conjuntos de datos. Por lo tanto, introducimos un elemento de aleatorización o aproximación para reducir nuestros tiempos de ejecución a un rango factible.
¡Viniendo de tu experiencia, puedes contribuir a este esfuerzo! Recomiendo comenzar con estos libros:
- Algoritmos aleatorizados: Rajeev Motwani, Prabhakar Raghavan: 9780521474658: Amazon.com: Libros
- Amazon.com: Algoritmos de aproximación (9783540653677): Vijay V. Vazirani: Libros
Criptografía
La criptografía es otra difícil. RSA supuestamente “resolvió” el problema del cifrado. Sin embargo, técnicas más sofisticadas como la criptografía de curva elíptica.
La criptografía de curva elíptica se basa en métodos de alta potencia de la teoría de números analítica y algebraica. Supongo que se podría argumentar que gran parte de la geometría de estas curvas tiene grupos b y, por lo tanto, es discreta. Sin embargo, gran parte de la información analítica podría ser la clave para romper ciertos tipos de cifrados. Si vienes del ámbito de las estadísticas y la probabilidad, es posible que desees elegir un libro como este:
Teoría de números algorítmicos, vol. 1: Algoritmos eficientes (fundamentos de la informática): Eric Bach, Jeffrey Shallit: 9780262024051: Amazon.com: Libros
y ponerse loco. Sin embargo, la NSA podría estar llamando a tu puerta pronto …
Gráficos
A mi entender, muchos métodos modernos en gráficos provienen del lado continuo del espectro. Sin embargo, no soy un experto aquí. Si desea seguir esta ruta, prepare su análisis numérico. Una increíble dirección de investigación es reconstruir el sonido de una escena dada. Piense en lo que pueden hacer los gráficos en este momento, podemos renderizar objetos y usar algunos conocimientos de física (¡métodos continuos!) Para descubrir cómo sonarían estas escenas.
Piense en esto, Pixar crea una nueva escena hermosa, y en lugar de juntar manualmente muestras de sonido y sincronizarlas con el video, podemos representar cómo se ve y suena una escena simultáneamente. ¡Todo lo que tendrían que hacer es agregar las voces de los personajes y BOOM! Te conseguiste una película. El futuro de la animación tal como la veo (pero nuevamente esta no es mi área).
Consulte algunos de estos documentos para obtener más información:
- Página sobre Usc
- http://www.cs.cornell.edu/projec…
Análisis de los datos
Este es otro lugar donde los métodos continuos están en todas partes. Piensa en los datos en la web. Si ha tenido la desgracia de escribir javascript, sabrá que todo está almacenado como cadenas. Bueno, hay algunas formas realmente geniales de analizar cadenas convirtiéndolas primero en una serie de potencia y luego los patrones en los datos están dados por los coeficientes. Echa un vistazo a este documento para obtener más información:
Página sobre Charuaggarwal
También hay formas correspondientes de intuir los patrones “escuchándolo” (usando el análisis de Fourier) y “viéndolo” usando la topología.
Para este último, piense en cómo las personas lidian con las altas dimensiones. Proyectan aleatoriamente los datos en un subespacio de baja dimensión que podemos ver y luego realizan algunas acrobacias (ver Algoritmos más arriba) para asegurarse de que las propiedades que les interesan se conservan con alta probabilidad. Podemos hacerlo mejor, una forma es utilizar los métodos de corte y corte de Topología para comprender los patrones. En realidad hay una compañía llamada Ayasdi | Descubrimiento automático de información que emplea estos métodos en primera línea. El peso pesado topológico Gunnar Carlsson está al mando, por lo que vale la pena echarle un vistazo. Ver lo siguiente
Página sobre Ayasdi
para más.
Otra buena idea es ver si los buenos métodos de análisis locales y suaves (en particular, la geometría espectral) funcionan bien con los métodos de topología de hack-and-slash. Ambos métodos tienen sus defectos teóricos. Pero el campo del “aprendizaje múltiple” está cobrando más fuerza como un área de investigación seria. Aquí hay un artículo sobre el tema. Cuidado con este: no es para los débiles de corazón.
Página sobre Arxiv
Lenguajes de programación
Creo que la teoría del tipo de homotopía ya se ha mencionado. Pero parece que la topología está apareciendo por todas partes. Nuevamente, no estoy involucrado en esta área (vivo en el análisis de datos) pero me consideraría un observador interesado. Fui a una charla de Dan Licata (página de inicio de Daniel Licata) que fue bastante interesante. Echale un vistazo.
Redes de computadoras
Este es otro tema fuera de mi conocimiento. Pero un gran artículo sobre este tipo de cosas es este: Page sobre Dartmouth. Las redes eléctricas están en el corazón de CS. Podemos hacer todo tipo de cosas utilizando el análisis (especialmente el análisis de Fourier) para comprender estas ideas.
Ahora para sus preguntas:
Además, ¿qué tipo de antecedentes en cálculo / análisis se considera suficiente para estas áreas?
En mi opinión, la cantidad de matemáticas que conoce es el cuello de botella en la cantidad que puede contribuir al campo. La investigación es guerra; Cuantas más herramientas tengas en tu arsenal, mejor.
¿Debo pasar a TCS después de mi título de UG?
Si quieres hacer TCS, entonces hazlo. Un doctorado es un compromiso a muy largo plazo, pero muy gratificante. Mira este consejo de Terry Tao para obtener una sabiduría mayor que la mía:
Orientación profesional
¡Buena suerte! Echa un vistazo a algunos de los enlaces que publiqué. Si esas áreas le parecen interesantes, entonces hágalo.