¿Qué tan importante es saber programar para TCS?

Viniendo de un fondo más matemático, nunca aprendí realmente cómo codificar. Estoy comenzando un doctorado en TCS y muchas personas se sorprendieron por lo poco que sabía sobre programación (y sobre computadoras en general). Puedo escribir algoritmos en pseudocódigo, pero realmente no conozco ningún lenguaje de programación.

Me imagino que algún día tendré que implementar algunos algoritmos para mi trabajo, pero ¿puedo esperar este momento? ¿O hay algo más?

¿Qué tan importante es saber codificar en TCS (en campos donde la programación no está directamente involucrada): ¿hay razones que podrían llevar a un teórico de CC (por ejemplo) a saber cómo codificar? ¿Vale la pena pasar mucho tiempo aprendiendo a codificar? Y si los hay, ¿hay una categoría (funcional, imperativa, orientada a objetos ...) de lenguaje de programación que sería más adecuada?

La informática teórica es un campo amplio y la importancia de la programación depende de lo que haga en TCS. Mencionaré dos formas en que la programación puede ayudarlo, sin implicar que estas son las únicas formas.

Primero, si diseña algoritmos para problemas de importancia práctica, implementar sus algoritmos y hacer que el código esté disponible para otros puede ser una gran ventaja. Por ejemplo, el problema del casco convexo surge en muchos campos, y la gente usa paquetes de software como cdd de Komei Fukuda y lrs de David Avis para resolver este problema. Si hubieran publicado sus algoritmos solo en documentos, probablemente menos personas habrían usado sus algoritmos. Más usuarios significan más comentarios y probablemente también más oportunidades para colaborar, lo cual es invaluable.

En segundo lugar, incluso si no trabaja en algoritmos, escribir un código de una sola vez le ayuda a probar una conjetura simple cuando la conjetura es adecuada para el cálculo numérico. Por ejemplo, si se pregunta si el producto de tres matrices definidas positivas siempre tiene una traza positiva, es fácil escribir un código para probar algunas opciones aleatorias de matrices definidas positivas 2 × 2 o 3 × 3 y encontrar un contraejemplo. Aunque no anuncia que escribió ningún programa para probar la conjetura, la programación puede ahorrar el tiempo que hubiera pasado en vano tratando de probar una declaración falsa.

El lenguaje de programación a elegir depende de lo que quieras hacer con la programación, y puede ser un tema para un libro completo en mi opinión. Pero si diseña algoritmos y desea implementar sus algoritmos para que otras personas puedan usar la implementación, entonces un factor importante es la disponibilidad. Aunque puede esperar que la mayoría de los usuarios potenciales de su código tengan acceso a un compilador de C, no puede esperar que las mismas personas tengan acceso a un compilador de Haskell. Para programas únicos, la elección se basa más en las bibliotecas disponibles e incluye entornos como Matlab.

Por cierto, la programación también puede ser divertida.

Me siento obligado a citar a Doron Zeilberger sobre esto:

Opinión 37 : La programación es aún más divertida que la prueba, y, lo que es más importante, ofrece tanto, si no más, comprensión y comprensión.

Lee la opinión, está llena de gemas (por cierto, tiende a ser deliberadamente provocativo). Por ejemplo, "La mejor manera de entender algo es enseñarlo. Pero incluso mejor enseñarlo a los humanos es enseñarlo a una computadora".

Mi experiencia personal es que incluso cuando haga un trabajo puramente teórico necesitará algunas herramientas informáticas. Evito muchas manipulaciones algebraicas rutinarias tediosas con Mathematica. Pruebo mis conjeturas a medio cocer mediante instancias pequeñas de fuerza bruta en Matlab o Python. Coescribí un artículo que es puramente combinatorio, y ese es el trabajo que más se ha beneficiado al realizar experimentos informáticos extensos para comprender lo que está sucediendo. Euler hizo enormes tablas de tediosos cálculos para comprender mejor los problemas. Le debemos usar nuestras herramientas para automatizar este proceso cuando hacemos matemáticas.

Aparte de eso, si trabaja en algoritmos y estructuras de datos, la programación le dará una perspectiva insustituible sobre cuestiones de eficiencia y usabilidad. Mi opinión aquí difiere un poco con los demás. Creo que aprender un lenguaje funcional para poder escribir pruebas que escriban correctamente es una pérdida de tiempo (creo que es un gran punto que las personas que tienen experiencia con un lenguaje fuertemente tipado probablemente tiendan a escribir pruebas estructuradas más cuidadosamente; simplemente no No creo que valga la pena hacer ese ejercicio). La programación funcional oculta los problemas de diseño de algoritmos y el tiempo de ejecución y enfatiza los problemas de lógica y semántica (y, por supuesto, el aprendizaje de la programación funcional es probablemente una necesidad y será algo natural si está interesado en la lógica / semántica PL). Similar, Creo que entrar en los detalles de OO de Java y C ++ tampoco es la forma óptima de pasar el tiempo, ya que el propósito de OO es escribir código modular reutilizable. Es el camino a seguir si va a generar código para que otros lo usen. Pero en caso de que desee obtener información sobre la eficiencia y el tiempo de ejecución, si le preocupan los algoritmos y las estructuras de datos realmente eficientes, secundo la sugerencia de investigar C. Le permite permanecer cerca de la máquina mientras proporciona un nivel razonable de abstracción . De esta manera, usted tiene una idea de lo que es rápido y lo que es lento, lo que es una estructura de datos razonable, etc. Pero en caso de que desee obtener información sobre la eficiencia y el tiempo de ejecución, si le preocupan los algoritmos y las estructuras de datos realmente eficientes, secundo la sugerencia de investigar C. Le permite permanecer cerca de la máquina mientras proporciona un nivel razonable de abstracción . De esta manera, usted tiene una idea de lo que es rápido y lo que es lento, lo que es una estructura de datos razonable, etc. Pero en caso de que desee obtener información sobre la eficiencia y el tiempo de ejecución, si le preocupan los algoritmos y las estructuras de datos realmente eficientes, secundo la sugerencia de buscar en C. Le permite permanecer cerca de la máquina mientras proporciona un nivel razonable de abstracción . De esta manera, usted tiene una idea de lo que es rápido y lo que es lento, lo que es una estructura de datos razonable, etc.

Puedes ser un científico informático teórico bastante exitoso sin programar. Para algunas personas, la programación es bastante difícil, y si usted es uno de ellos, no debe desesperarse y cambiar de campo.

Sin embargo, para la mayoría de los estudiantes graduados de matemáticas e informática, aprender a programar no es particularmente difícil y es una habilidad que es muy útil. Debes aprender un lenguaje de programación y, si lo disfrutas, debes tratar de obtener suficiente práctica para llegar a ser razonablemente competente. Luego, cuando llegue el momento (y lo hará) de que será útil en su investigación escribir un programa, podrá hacerlo.

Si no aprende a programar ahora, es muy probable que cuando finalmente necesite escribir un programa, no tenga tiempo para aprender, por lo que es posible que no lo escriba y termine siendo menos eficaz en su investigación. Si bien conseguir que un estudiante de posgrado o un estudiante universitario haga esto por usted no es demasiado difícil, hay muchas veces en que es mucho más fácil y lleva menos tiempo hacerlo usted mismo en lugar de explicarles el problema.

¿Qué idioma debes aprender? Recomendaría un lenguaje orientado a objetos, ya que estos son los que actualmente se usan más, y sospecho que esto será más cierto en el futuro. Tal vez Python o Java: ambos son lenguajes orientados a objetos, y aunque se usan menos en la práctica que C ++, mi impresión es que ambos son mucho, mucho más fáciles de aprender. (Advertencia: no sé C ++, a pesar de haber trabajado en Bell Labs, así que tal vez me equivoque sobre esto).

Hay otra respuesta que nadie realmente ha planteado. La programación en realidad puede conducir a una teoría interesante. Muchos de los desarrollos recientes en hashing (especialmente hashing de tabulación) están motivados no por preocupaciones teóricas per se, sino por el hecho de que los algoritmos teóricamente óptimos no son tan buenos en la práctica. Esto, por supuesto, es algo que no sabes a menos que puedas escribir código.

Incluso en el ámbito de los algoritmos de tiempo exponencial exacto, una motivación es producir algoritmos que realmente puedan funcionar. Los solucionadores SAT son el ejemplo canónico de esto.

En resumen, la capacidad de codificar le permite darse cuenta de las deficiencias y debilidades en lo que podrían parecer resultados teóricos óptimos, y eso a su vez abre nuevas direcciones de investigación teórica.

Tres puntos:

1) Existe una aproximación a las matemáticas llamada Matemática Experimental (ver también wikipedia: // Prueba asistida por computadora ) en la que se utilizan programas informáticos para investigar patrones y estructuras de objetos con el fin de obtener pruebas analíticas sobre estos objetos. Para este enfoque, es mejor que sepa cómo programar. Puede estar seguro de que necesitará este enfoque para probar afirmaciones muy teóricas. Creo que el esnobismo contra la programación a menudo resulta no ser realmente útil en la investigación de TCS.

$A \in L(X,Y)$$B \in L(Y,C)$ ). Esto es bueno para el lectores de un manuscrito Los compiladores (e intérpretes) nos convierten en buenos científicos :) Para este tipo de habilidades, siento sugerir un lenguaje funcional fuertemente tipado.

3) Cuando dice "programar", ¿quiere decir también " programa lineal " o " programa semidefinido "? :)

Gracias Gopi por esta pregunta. Me gustaría extender las muchas respuestas interesantes en otra dimensión que aún no se ha mencionado.

La investigación no es lo único que hacemos en la universidad: si quieres permanecer en la academia, eventualmente tendrás que enseñar. Si tiene suerte, deberá impartir cursos que estén bastante lejos de su área de especialización. Es muy probable que se le asignen cursos con un componente de programación sustancial. Aquí es donde incluso una habilidad moderada para programar ayuda sustancialmente: serás mucho mejor maestro si sabes programar. En primer lugar, se sentirá más cómodo con el material, podrá responder mejor a las preguntas de los estudiantes y comprenderá las dificultades que tienen los estudiantes para aprender a programar, ya que usted mismo ha experimentado este proceso de aprendizaje. Además, puede producir un mejor material didáctico. Por ejemplo, puede probar los ejercicios de programación usted mismo antes de dárselos a los estudiantes,

Hay una dimensión pragmática adicional: la enseñanza implica varias tareas repetitivas que un programador experto a menudo puede automatizar, como crear rápidamente un sitio web que los estudiantes puedan usar para enviar los cursos, y que se califique automáticamente (de acuerdo con la cantidad de pruebas automatizadas que pasa el código).

La programación es una buena manera de mejorar su comprensión de varios conceptos, pero también es un sumidero de tiempo peligroso.

Un argumento típico en contra de la programación es que te hace pasar tiempo con detalles sin importancia; Un argumento típico para la programación es que te hace darte cuenta de que los detalles que creías que no son importantes son importantes. Llegar a ser bueno en la programación significa principalmente ser capaz de lidiar con las partes sin importancia rápidamente. Volverse bueno lleva mucho tiempo.

En cuanto al lenguaje de programación para aprender: "todos ellos" es mi respuesta (irónica).

Llego tarde a la fiesta, y estas son todas excelentes respuestas, pero tengo otra razón:

Visualización.

Sí, a menudo trabajará con cosas que no se pueden visualizar, pero a menudo trabajará con cosas que sí pueden. Saber programar es indispensable para esta tarea, y la visualización puede ofrecerle mucha información sobre un problema.

Solo un punto rápido: saber programar me da una herramienta adicional en la investigación teórica. Cuando tengo un algoritmo que creo que funcionará, si es lo suficientemente fácil, podría codificarlo y verificar si realmente funciona. Si mi idea no funciona (incluso) en la práctica, no es muy probable que funcione en teoría, y este enfoque a menudo me salva de perder una enorme cantidad de tiempo tratando de probar algo que es falso.

Nadie aquí ha abordado los problemas prácticos de por qué alguien que estudia TCS debería aprender a programar.

Si está planeando hacer un doctorado en TCS en un departamento de Ciencias de la Computación, existe una buena posibilidad de que necesite tomar algunos cursos que no sean de Teoría, y estos seguramente serán muy intensivos en programación. Dependiendo del programa en el que se encuentre, también puede necesitar conocimientos de materias no teóricas para aprobar sus exámenes de calificación.

Cuando terminas tu doctorado, la mayoría de las oportunidades laborales para TCS están en la academia. Si trabajas en la academia, se espera que enseñes, y se espera que enseñes una clase de CS de pregrado de nivel introductorio que será más programación que teoría. Incluso si está enseñando una clase de teoría a estudiantes de pregrado, como digamos Algoritmos, puede esperar que sus estudiantes sepan más sobre programación que teoría, y sin saber lo que saben sus estudiantes, será difícil para usted cerrar las brechas en su comprensión. . ¡Me estremezco ante la idea de que alguien que no conozca la programación enseñe a estudiantes universitarios de CS!

Si no le importan estas preocupaciones prácticas, entonces probablemente pueda hacerlo haciendo una investigación sin realmente saber nada sobre programación. Ciertamente, tiene mucha compañía en la comunidad de TCS, pero el kilometraje variará según el área exacta de Teoría en la que esté trabajando. Por ejemplo, si está haciendo una teoría de complejidad computacional pura, demostrando límites más bajos en clases que nadie tiene Alguna vez has oído hablar, entonces es probable que la programación no te sea útil. Pero si está haciendo algo más algorítmico, creo que ser capaz de escribir un buen código de trabajo limpio fortalecerá su intuición, si nada más.

Recomiendo aprender C (no C ++). Recoja una copia de K&R y léala de frente a atrás. C no tiene muchas de las características sofisticadas de los lenguajes modernos, pero sí tiene una sintaxis y una semántica simples pero elegantes, que deberías poder aprender en su totalidad. Sin embargo, incluso cuando comprenda el lenguaje en su totalidad, aún requiere práctica para dominar la escritura de un código elegante y libre de errores en C. Sin embargo, si puede dominar la codificación en C, podrá dominar cualquier lenguaje de programación que encuentre. Además, esa disciplina lo ayudará a pensar cómo piensa el hardware, lo que será beneficioso al diseñar algoritmos.

Ideas como los punteros son muy importantes para cualquier persona que diseñe algoritmos, pero desafortunadamente, lenguajes como Java y Python los ocultan de usted, por eso no los recomiendo como primer idioma para alguien con experiencia en matemáticas. OOP es más importante para las personas que tienen que mantener grandes proyectos de software, no para alguien que está diseñando algoritmos.

Le sugiero que no espere el comienzo de su curso, ya que la informática en cualquier nivel implica la implementación de algoritmos a través de una computadora para lograr / verificar / resolver cualquier teoría que tendrá que enfrentar a lo largo de su curso, ESPECIALMENTE a su nivel.

Primero tuve que programar en el grado 10 (escuela secundaria), y ya sabía cómo usar una línea de comando y esto realmente ayudó (esto es para mostrarle cómo se consideran las habilidades de programación "básicas" en CS).

El asombro de sus compañeros está bien fundado, ya que los pseudocódigo y los algoritmos se encuentran entre las primeras cosas que uno tiene que aprender para programar.

Sin embargo, no debe perderse por completo en su próximo curso, ya que puede usar sus habilidades matemáticas más amplias (por su cuenta) a su favor para omitir la programación orientada a objetos para ponerse al día aprendiendo más rápido un lenguaje de programación funcional.

• La programación funcional está MUY orientada a las matemáticas, se considera más difícil de aprender por sus conocimientos matemáticos necesarios, se considera muy poderosa (en su forma "simple" y matemática para resolver problemas difíciles a través de medios elegantes y "limpios").
• La orientación a objetos es buena cuando no desea comprender los algoritmos subyacentes y los principios de implementación y simplemente desea "reutilizar" objetos ya existentes.

Creo que podría abordar Haskell (generalmente no es un primer idioma) porque es puramente matemático, funcional y puede hacer básicamente cualquier cosa que desee. Aprender Haskell lo pondría en un nivel en el que no necesitaría aprender mucho más para mantenerse al día, e incluso lo pondría en una situación de control y poder sobre su curso. Si te gustan las estadísticas, aprender R es una ventaja, pero no tanto como Haskell. He visto informes de matemáticos que indican cuán sorprendidos estaban por su cercanía con las matemáticas y cómo abrazó su forma de pensar.

Además, un desafío que vale la pena abordar (para acostumbrarse rápidamente a un entorno de programación) sería instalar y usar Linux (Ubuntu Linux lo hará). Confía en mí, aprenderás mucho jugando con él ...

Estos consejos son la mejor manera que conozco de ponerme al día rápida y seguramente para un matemático en informática. Además, la comunidad de código abierto es muy amigable y servicial, y si está atascado, IRC es la forma más directa de hablar sobre cualquier tema a través de canales especializados (conéctese en FreeNode). Recuerde: preguntar es la única forma de resolver preguntas, ya sea para usted mismo, un foro, un motor de búsqueda o en salas de chat.

Un ejemplo de una implementación en C ++ de un sistema de prueba interactivo es el siguiente documento: Pruebas interactivas de tiempo óptimo para evaluación de circuitos, por Justin Thaler. Está disponible en http://people.seas.harvard.edu/~jthaler/ . Parece ser un paso hacia el objetivo de desarrollar una implementación práctica de sistemas de prueba interactivos de uso general.

Documentos similares y códigos fuente relacionados aparecen en el sitio web mencionado anteriormente.