¿Qué tan importante es saber programar para TCS?

66

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?

Gopi
fuente
12
Debería haber programado algunos para escribir pseudocódigos significativos, es decir, definidos y que reflejen el tiempo de ejecución. Los matemáticos a menudo no lo hacen. Además, si realmente desea utilizar la teoría que desarrolla, es probable que tenga que implementar algo. En cuanto a los idiomas, probablemente sea mejor aprender algo funcional. C es bueno para el rendimiento pero difícil de razonar y desordenado en muchos aspectos. (Como puede ver, YMMW)
Raphael
66
Estoy de acuerdo con "Los matemáticos a menudo no lo hacen". Una prueba simple para saber si un matemático que describe un algoritmo realmente ha programado realmente es preguntar "¿ Qué quiere decir exactamente con 'Dado una X ...'?"
Jeffε
44
Programación, ¿qué es eso? Los teoremas son mis programas. Un procedimiento de cocción es diferente del arte de cocinar. Lo siento, en más de 20 años no puedo leer ningún código de programa. En realidad, odio este desastre "realizado en PC". (Ya esta notación enferma.) Euclides no pudo programar. Sin embargo, hizo programas durante siglos.
Stasys
66
@StasysJukna: Euclid era en realidad un programador muy, muy malo. No solo nunca implementó sus algoritmos, ni siquiera los ejecutó a mano en casos de prueba moderadamente complicados.
Jeff el
3
@ Jɛ ff E: Sí, Euclid era un programador horrible, exactamente eso quería decir. Nosotros, en TCS, tendemos a no distinguir entre libros de cocina y arte de amartillar. Euclides pudo. Tengo un gran respeto por las personas que pueden programar. Pero no creo que esta característica signifique "una CAN en TCS". Simplemente no dolerá.
Stasys

Respuestas:

55

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.

Tsuyoshi Ito
fuente
2
@SureshVenkat: De hecho, si la programación es divertida, la pregunta "¿Qué tan importante es la programación?" Puede no ser muy relevante. Pero entonces la mayor parte de mi respuesta será irrelevante. ¡Qué triste! :)
Tsuyoshi Ito
¡No pensé en tu segundo argumento antes, de hecho, parece una muy buena idea probar una conjetura con un programa corto! En cuanto a la programación, puede ser divertido, por lo que parece, pero todavía tengo que ver todo el largo aprendizaje de fin de semana =).
Gopi
@Gopi: Dicho esto, muchas conjeturas no encajan en este marco de "prueba con un programa simple". Por ejemplo, generalmente no podemos probar comportamientos asintóticos (al menos mediante un programa simple). Pero cuando tienes alguna conjetura que se puede probar, un poco de programación puede ser una herramienta poderosa. En cuanto a la diversión, sí, lo entiendo. Simplemente no quería ignorar el punto de vista "divertido" al enumerar solo algunas motivaciones desde el punto de vista de "utilidad".
Tsuyoshi Ito
3
Las notas de Knuth sobre una clase de resolución de problemas tienen un maravilloso ejemplo de la interacción entre conjeturas y código (vea el problema 1): www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (particularmente me gusta la imagen de alguien corriendo al aula con un montón de impresiones)
Suresh Venkat
47

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.

Sasho Nikolov
fuente
10
"La programación funcional oculta problemas de diseño de algoritmos y tiempo de ejecución y enfatiza problemas de lógica y semántica". Fighting words :)
Suresh Venkat
3
"La programación funcional oculta problemas de diseño de algoritmos y tiempo de ejecución y enfatiza problemas de lógica y semántica". Es por eso que es una buena opción si trabaja en el lado lógico o semántico de TCS. :)
Radu GRIGore
55
Ejem.
Jeff el
3
@Sasho: Todas las técnicas comunes todavía funcionan en lenguajes funcionales. El único "problema" es que la programación funcional fomenta un estilo de programación y diseño de estructura de datos que las técnicas ordinarias de análisis algorítmico están insuficientemente equipadas para manejar. (Por ejemplo, ¿cuál es el gran-O de la composición de funciones El funcionamiento es? Trivial , pero se rompe por completo los supuestos de complejidad asintótica - no hay métrica simple numérico de tamaño para una entrada funcional.)
Neel Krishnaswami
3
@SashoNikolov: Cada vez que enseño una clase de estructuras de datos de posgrado, realmente desearía poder asumir que todos tenían alguna experiencia de programación funcional. En lugar de pasar tres conferencias de 90 minutos para explicar la persistencia, podría simplemente decir "Hey, ¿notaron que sus estructuras de datos ya hacen ESTO?"
Jeffε
33

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).

Peter Shor
fuente
2
Veo la verdad en tu tercer párrafo :).
Gopi
1
"Sin embargo, para la mayoría de las personas, aprender a programar no es particularmente difícil": mi experiencia me lleva a estar en desacuerdo con esto, pero la mayoría de las personas no son investigadores de TCS.
Max
2
Con el surgimiento de Sage, es posible trabajar con un lenguaje agradable y popular como Python sin dejar de tener disponibles instantáneamente bibliotecas matemáticas de estilo Mathematica / Maple / Matlab.
András Salamon
1
C ++ tiene el sistema de metaprogramación / tipo más avanzado de todos los lenguajes de programación de uso general que he visto, excepto la familia de lenguajes Lisp. Por lo tanto, si le gusta la teoría de tipos, el diseño de lenguaje o la teoría de compiladores, o más ampliamente la semántica formal, es posible que desee familiarizarse con ella. Además de C ++, Java y C # son imprescindibles si desea investigar en Ciencias de la Computación experimentales, o si desea obtener un trabajo como programador o ingeniero de software en la industria. Python debería enseñarse en las escuelas secundarias: D
Antonio Valerio Miceli-Barone
44
@ AntonioValerioMiceli-Barone: Tengo que estar en desacuerdo, al menos para la teoría de tipos, el diseño del lenguaje, la semántica formal y la teoría del lenguaje de programación (PLT) en general: C ++ no es el lenguaje para aprender en esos campos; TT y la semántica formal se relacionan casi exclusivamente con la programación funcional, mientras que la comunidad PL es más diversa, pero prefiere lenguajes más elegantes que C ++. Haskell es el lenguaje "convencional" con el sistema de tipos más avanzado, seguido de Scala (menos avanzado, un poco más convencional). C ++ tiene características interesantes, pero tiene un nivel demasiado bajo para el gusto moderno.
Blaisorblade
33

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.

Suresh Venkat
fuente
Su respuesta podría ayudar en la pregunta sobre los resultados empíricos en TCS .
Gopi
tal vez: pero ese hilo ha desaparecido hace mucho tiempo :)
Suresh Venkat
De hecho, no miré la fecha, estaba en el último boletín que recibí, en la sección "Grandes éxitos de semanas anteriores" =).
Gopi
18

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.

AL(X,Y)BL(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 "? :)

Alessandro Cosentino
fuente
2
Nadie que conozco usa "programar" para "programar lineal" o "programar semidefinido". En su lugar, diría "construir / resolver un programa lineal".
Peter Shor
2
@PeterShor El punto 3 no era serio
Alessandro Cosentino
3
Y, por supuesto, también debe aprender a un programa lineal y a un programa semidefinido ... ambas habilidades útiles.
Peter Shor
3
+1 para el punto 2, en realidad me enseñaron un poco de OCaml cuando era estudiante de pregrado, aunque solo lo usé durante un año, tuve la costumbre de verificar los tipos de mis pruebas.
Gopi
44
Yo programo dinámicamente !
Jeff el
16

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).

Martin Berger
fuente
"Si tiene suerte, tendrá que impartir cursos que estén bastante lejos de su área de especialización". ¿Tiene suerte ...?
Tsuyoshi Ito
3
@ Tsuyoshi: Bueno, te obliga a familiarizarte con un nuevo tema. A corto plazo, eso significa mucho trabajo (que se amortiza a largo plazo, ya que es probable que enseñe este material más de una vez). Al mismo tiempo, amplía considerablemente tus horizontes intelectuales.
Martin Berger
@ TsuyoshiIto: ¡Sí!
Jeff el
13

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).

Radu GRIGore
fuente
2
Finalmente un argumento en contra de la programación :).
Gopi
1
@Gopi, creo que la programación puede ser muy divertida y que la mejor comprensión que obtienes es muy importante. Las otras respuestas dan excelentes ejemplos de cómo la programación ayuda a comprender. Por lo tanto, le recomiendo que aprenda a programar y que no se rinda si la empresa no parece rendir rápidamente.
Radu GRIGore
66
Probar teoremas también es una buena manera de mejorar su comprensión de varios conceptos, pero también es un sumidero de tiempo peligroso.
Jeff el
@ Jɛ ff E, mi opinión está preservada por la sustitución [pseudocódigo-> prueba en papel, código-> prueba en un asistente de prueba].
Radu GRIGore
12

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.

John Moeller
fuente
3
Sé programar, y soy absolutamente inútil en la visualización. También sospecho que hay herramientas que te permitirán visualizar cosas sin hacer mucha programación; si no lo hay, debería haberlo, y tal vez lo será en unos años.
Peter Shor
@PeterShor: ¡Porque no usas C ++! (Es broma)
Tsuyoshi Ito
1
@ PeterShor: No me estoy refiriendo a ningún lenguaje o entorno específico; MATLAB cuenta aquí. Pero saber cómo programar puede obtener visualizaciones que de otro modo serían increíblemente inconvenientes. Por ejemplo, el espacio de las matrices bidimensionales positivas definidas es tridimensional, y quería visualizar una familia de construcciones en este espacio. Tuve que idear una transformación y luego codificarla para ver realmente mis objetos.
John Moeller el
@ John ... tienes razón, no creo que pudieras haber hecho eso de otra manera.
Peter Shor
7

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.

Lev Reyzin
fuente
Tsuyoshi Ito escribió un argumento similar en su respuesta (segundo punto :)).
Gopi
Vaya, tienes razón, me lo perdí.
Lev Reyzin
5

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.

marca
fuente
0

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.

Samuel Duclos
fuente
44
No sé cuánto está respondiendo la pregunta original: no pregunté "cómo", sino más "para qué".
Gopi
0

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.

lgidwani
fuente
3
¿Podría explicar cómo se relaciona este documento con la pregunta, es decir, qué tan importante es saber programar para TCS ?
scaaahu
Incluso si fuera un ejemplo de resultado teórico que se beneficiara de la programación, ¿no respondería la pregunta original?
Jeremy
La pregunta pregunta si es necesario que un teórico de la complejidad conozca la codificación. El artículo mencionado anteriormente claramente usa resultados experimentales para complementar los conceptos teóricos; Esto requiere codificación. En cualquier caso, me llevó mucho tiempo encontrar un proyecto de programación que esté tan estrechamente relacionado con un concepto central en informática teórica. Espero que esta publicación pueda ser útil para alguien en una búsqueda similar.
lgidwani