Educación en Ciencias de la Computación: ¿Cómo el aprendizaje de matemáticas discretas te hace un mejor programador?

Las matemáticas discretas son la base de muchos programas que escribimos. Lo usamos a sabiendas o sin saberlo. Las construcciones de programación cotidianas, como los bucles, la recursividad, están diseñadas en base a matemáticas discretas. Implementar la recursividad es muy fácil, pero para explicar cómo funciona la recursión se necesita cierto conocimiento de matemáticas discretas. Y también debe saber cuándo y dónde usar la recursividad y cómo funciona la recursividad y por qué la usó en primer lugar.

Existen varios algoritmos, que son básicamente pasos para resolver un problema dado. Cuando tenga más de un algoritmo para resolver un mismo problema, ¿cómo determinará cuál es mejor? Aquí entra en juego la belleza de los conceptos matemáticos discretos. Notaciones asintóticas, teorema maestro, relación de recurrencia y otros conceptos que son muy importantes para demostrar por qué una solución es mejor que otra.

Hay algunos libros como “Matemáticas concretas” de Knuth, que está hecho exclusivamente para personas que aman la informática. Cuando una persona como Knuth escribe un libro sobre matemática discreta, entendemos lo importante que es la matemática discreta.

No diré que no puedes convertirte en programador sin matemáticas discretas, pero no podrás saber cómo funciona el programa y por qué el código de algún programador es mejor que el tuyo. Aprender matemáticas discretas es una de las necesidades básicas para un ingeniero informático o cualquier persona que quiera convertirse en un buen programador o ingeniero.

Las matemáticas discretas no son muy complicadas en la naturaleza, como el álgebra o el cálculo, es la recursión básica, la combinatoria, la notación asintótica, la sumatoria, la lógica, la teoría de conjuntos y todos esos conceptos, pero te harán pensar mucho. La respuesta que crees puede no ser siempre correcta, especialmente en combinatoria. Hay mucho para pensar y uno que comienza a pensar siempre se vuelve mejor de lo que era antes. Lo mismo se aplica a la programación, cuanto más sepa por qué usa algunos conceptos en su programa, mejor será.

Tomé un curso de Matemática discreta en la universidad que trató los siguientes temas:

Lógica y pruebas:
Los programadores usan la lógica. Todo el tiempo. Si bien todos tienen que pensar en la solución, un estudio formal del pensamiento lógico le ayuda a organizar su proceso de pensamiento de manera más eficiente: puede descubrir antes que está viendo una línea de razonamiento que no conducirá a su solución. Además, estudiar cómo transmitir que su solución realmente funciona para un problema le hará mucho bien en su trabajo y prácticamente en cualquier otro lugar.

Combinatoria:
No se puede programar sin bucles o recursividad. (Quiero decir que podríamos, pero no sería muy útil) Tener una idea de las Matemáticas detrás de estos conceptos de programación tan esenciales lo ayuda a optimizar su código. Puede sentir intuitivamente que una recursión particular se repite innecesariamente y hacer el cambio a un enfoque basado en programación dinámica. Cuanto antes.

Gráficos:
No se puede sobrestimar la importancia de los gráficos en CS hoy, con la aparición de las redes sociales y la necesidad de representar todo tipo de relaciones complejas entre entidades. Learning Graphs puede ayudarlo a visualizar mejor muchas estructuras de datos. Además, hay mucho espacio para una mejor programación en gráficos. Tener conocimiento matemático sobre ellos es esencial para hacer eso.

Además, aprendí sobre estructuras algebraicas, celosías y álgebra booleana que, aunque no afectan directamente mis habilidades de programación, indirectamente les han hecho un mundo de bien. Entonces, diría que es extremadamente importante que los programadores de software conozcan Matemáticas discretas.

En algunos sentidos diferentes, los programas son teoremas, y los métodos para derivarlos con alguna esperanza de corrección se asemejan mucho a las enumeraciones, reducciones, inducciones, etc., que son bloques de construcción de pruebas en matemáticas discretas (o su hermano mayor, la teoría de números).

Esto no quiere decir que no pueda programar nada sin él (legiones de hackers locales probarían que esa suposición es incorrecta), pero practicar el modo de pensar fortalece su confianza en que un programa hará lo que quiere antes de compilar /ejecutarlo.

Es algo así como tener una dieta equilibrada no ayuda directamente a un corredor de larga distancia, pero de todos modos lo hace. La digestión del desayuno no debería ser la mayor preocupación mientras corres un maratón, por lo que rindes mejor si es algo que has cubierto con anticipación y no tienes que lidiar en cada intento.

Aunque odio la mecánica de las matemáticas, y normalmente les digo a los programadores que no la necesitan, usted preguntó por qué las matemáticas discretas son útiles. Tomemos un ejemplo de la vida real.

Digamos que tengo dos métodos generales para resolver un problema, y ​​para mi conjunto de entradas y salidas deseadas, los métodos son idénticos.

Uno tiene 5 líneas de largo y el otro tiene 1000 líneas de largo. Sin conocer las matemáticas discretas y cómo se aplica al análisis de algoritmos, diría que el método de 5 líneas es mejor que el método de 1000 líneas.

Te equivocarías en muchos casos, aunque no en todos o incluso en la mayoría de los casos. Debe observar el tiempo y los recursos que requiere cada solución.

Agreguemos una arruga más: el ejemplo de 5 líneas se escribió durante el almuerzo en el reverso de una servilleta, mientras que el ejemplo de 1000 líneas es un programa en un idioma del que nunca ha oído hablar, que fue escrito para una máquina que ganó ‘ Existe desde hace 10 años.

La única forma de compararlos sin matemáticas discretas es implementar cada uno, haciendo algunos puntos de referencia. Esto implica varios problemas:

• Diferencias en sus implementaciones, con el mejor ejemplo teórico que le brinda resultados incorrectos
• Con el programador promedio escribiendo 8 líneas de código completamente depurado al día; con 4 meses de pruebas directas necesarias, luego tirando la más lenta; y con 4 meses de tiempo perdido y esfuerzo si es el ejemplo de 1000 líneas

Con el análisis de algoritmos, a través de unos pocos cálculos simples, a lápiz y papel, en teoría, podemos ver cuánto tiempo llevará cada uno en * CUALQUIER * computadora, y luego usar el que tenga las mejores características de rendimiento.

Informalmente, esto se llama “big-O” y se denota como O (x), donde “x” es un número que le indica cuántas veces necesita realizar una operación de tecla para una entrada de tamaño n.

Por ejemplo, independientemente de la cantidad de entrada, un algoritmo O (1) toma la misma cantidad de tiempo. AO (n!) [N! = N * n-1 * n-2 * … 1] es un algoritmo extremadamente lento, y de hecho, su apodo es “NP”.

Cualquier algoritmo que requiera menos de [matemática] O (n ^ k) [/ matemática] para una constante k se conoce informalmente como P. Uno, si no el único, santo grial de CS es P = NP.

En otras palabras, ¿alguna fórmula mágica nos permite convertir todos los problemas NP en problemas P?

La gran mayoría de las personas con CS dice P! = NP (P no es NP igual), pero la pregunta es imposible de probar o refutar hasta que hayamos probado todas las soluciones posibles, lo cual es un problema de NP en sí mismo. (-;

Personalmente, creo que es un enfoque académico, y no veo que las matemáticas sean muy relevantes para la informática. Pero hay algún punto en eso en que las matemáticas discretas tratan con dominios que no son continuos, sino incrementales en pasos. Eso es exactamente con lo que te encuentras con la programación.

Algo puede ser confuso en que su programa puede calcular una probabilidad del 70% de una elección, reconocimiento de objetos, ruta más corta u otro resultado, y el programa tiene que alterar eso al 100%. No hay intermedios con la programación. Tiene que ser 100% de un camino u otro. Esto aparece a menudo con imágenes y gráficos. Por ejemplo, el problema de alias que hace que una línea ligeramente angular parezca una escalera, es el resultado de esta discreta elección de píxeles. Lo que los programadores deben hacer para ocultarlo es una aleatorización local de color, brillo o patrón, para evitar que se note esta repetición discreta. Por lo tanto, es preocupante, pero más en términos de inteligencia artística o artificial, que en un sentido matemático.

Los ingenieros eléctricos tienen que lidiar con esto todo el tiempo cuando necesitan integrar circuitos analógicos y digitales. Puede ser complicado Pero nuevamente, solo requiere recordar que las computadoras simplifican demasiado la física del mundo real cuando tienen que dividir las cosas en valores discretos, cuando en realidad el mundo no es discreto. Necesita crear un algoritmo de over para compensar las limitaciones de la computadora. Pero no es realmente matemático.

Además, cuando necesita lidiar con hardware lógico, los circuitos binarios solo pueden ser valores discretos de 1 o 0, por lo que es útil poder resolver problemas de circuitos complejos utilizando cosas como tablas de verdad.

Van de la mano, pero creo que a menudo funciona más al revés. Desarrollar experiencia en programación te hará mejor en matemáticas discretas 🙂

Aún así, las matemáticas discretas a menudo implican un pensamiento algorítmico, simplemente expresado en un idioma diferente. Las pruebas por inducción son conceptualmente similares a escribir una función recursiva. También los principios de conteo son bastante útiles para tener una idea “de un vistazo” de cómo esperar que su código funcione

Las matemáticas detrás de la informática moderna se basan únicamente en matemáticas discretas. Las matemáticas discretas incluyen la teoría de grafos, la combinatoria y la lógica. Para comprender los algoritmos informáticos, uno debe tener una comprensión adecuada de las matemáticas discretas. No solo es útil en la programación, sino que también puede mejorar sus habilidades lógicas y matemáticas.

Uno puede desarrollar una forma natural de resolver problemas de codificación al tener una buena comprensión de las matemáticas discretas.

Estoy trabajando como ingeniero de software, y he trabajado como TA para el curso discreto de matemáticas. y creo que el buen conocimiento de las matemáticas definitivamente te hará un mejor programador, Mathematics entrena tu mente de una manera que es útil no solo para resolver problemas específicos, sino que también te enseña cómo pensar en los problemas de una manera más formal (que, Creo que es importante para escribir el código correcto).

En la línea de producción de programación, creo que la teoría de conjuntos, el álgebra booleana, los mapas, etc. son beneficiosos para un programador y son parte de matemáticas discretas. definitivamente, los conceptos no siempre serán aplicables en el sentido más académico. Casi nunca abrirá su libro de texto de matemáticas discretas y copiará algo en su código para resolver un problema. Sin embargo, comprender esos conceptos ayudará a los desarrolladores a escribir un mejor código, mejores algoritmos y usar patrones de diseño de manera más efectiva.

Agregaré un tema a la respuesta del usuario de Quora:

Complejidad de tiempo (notación O)
Has inventado un nuevo algoritmo y quieres saber qué tan rápido es (lo que se llama notación O). Puede hacerlo “programáticamente” o analíticamente utilizando matemáticas discretas. (Por ejemplo, mire el libro de Donald Knuth: El arte de la programación de computadoras)

Las matemáticas discretas te ayudan a echar un vistazo al universo o al tema con el que trabajas en términos de objetos discretos. Obtiene las herramientas para crear modelos matemáticos sobre objetos individuales o grupos de objetos. Te acostumbras a mapear la realidad con esos modelos, que tienen una base matemática para describir su comportamiento.

Es muy frecuente escuchar que el cálculo o la física ayudan a tener una forma de pensar. Las matemáticas discretas te traen lo mismo, en una dirección ligeramente diferente, cerca de tu experiencia diaria.