La importancia de la matemática discreta en la programación

La importancia de la matemática discreta en la programación y sus diferentes aplicaciones

La matemática discreta es la rama de la matemática que trata con los objetos que pueden asumir solamente valores separados. Por lo tanto, el término “Matemática Discreta” se utiliza en contraste con “Matemática Continua”, que es la rama de las matemáticas que se ocupan de objetos que puedan variar suavemente (y que incluye, por ejemplo, cálculo). Mientras que los objetos discretos pueden caracterizarse a menudo por enteros, los objetos continuos requieren números reales.

La importancia de la matemática discreta en la programación

La importancia de la matemática discreta en la programación

El estudio de cómo los objetos discretos se combinan entre sí y las probabilidades de varios resultados se conoce como combinatoria. Otros campos de las matemáticas que se consideran parte de la matemática discreta incluyen la teoría de los gráficos y la teoría de la computación. Los temas de la teoría de números como las relaciones de congruencia y recurrencia también se consideran parte de la matemática discreta.

El estudio de temas en matemáticas discretas generalmente incluye el estudio de algoritmos, sus implementaciones y eficiencias. La matemática discreta es el lenguaje matemático de la informática, y como tal, su importancia ha aumentado dramáticamente en las últimas décadas.

El conjunto de objetos estudiados en matemáticas discretas puede ser finito o infinito. El término matemáticas finitas se aplica a veces a partes del campo de la matemática discreta que se ocupa de conjuntos finitos, particularmente aquellas áreas relevantes para el negocio.

La investigación en matemáticas discretas aumentó en la segunda mitad del siglo XX en parte debido al desarrollo de ordenadores digitales que operan en pasos discretos y almacenan datos en bits discretos. Los conceptos y las notaciones de la matemática discreta son útiles en el estudio y la descripción de objetos y problemas en ramas de la informática, tales como algoritmos de computadora, lenguajes de programación, criptografía, probar teorema automatizado, y desarrollo de software. Por el contrario, las implementaciones informáticas son importantes en la aplicación de las ideas de la matemática discreta a los problemas del mundo real, como en la investigación de operaciones.

La importancia de la matemática discreta en la programación

Lograr el conocimiento práctico de muchos principios de la informática requiere el dominio de ciertos conceptos matemáticos y habilidades relevantes. Por ejemplo, una comprensión del álgebra booleana que incluye DeMorgans Law es útil para entender las expresiones booleanas y los fundamentos de los circuitos combinacionales que rodean el crecimiento de funciones y las sumaciones son útiles para el análisis de estructuras de control de bucles para resolver relaciones de recurrencia es de rigor para el análisis de algoritmos recursivos y una introducción a los métodos de prueba que facilita la consideración de la corrección del programa y el pensamiento riguroso en general.

Los estudiantes son introducidos a las técnicas de prueba antes de comenzar a considerar la idea de probar programas correctos. Aprenden sobre la lógica proposicional y el álgebra booleana antes de estudiar algunos circuitos muy elementales y aprender las estructuras de control de decisión y las variables booleanas. Se introducen en la lógica de los predicados cerca del momento en que comienzan a programar y aprender acerca de las variables. Aprenden sobre el crecimiento de las funciones de notación grande-O y sumaciones antes de analizar bucles anidados y anclados y tienen las herramientas para comenzar el análisis del algoritmo desde el momento en que primero empiezan a aprender sobre construcciones iterativas. Conjuntamente con una introducción a la teoría de números, realizan ejercicios de laboratorio y de programación que incluyen un surtido de algoritmos enteros.

Los estudiantes aprenden sobre las relaciones recurrentes de las definiciones recursivas, analizando algoritmos recursivos y escribiendo algoritmos y programas recursivos juntos en el mismo curso. Estudian matrices y manipulaciones de matriz en conjunto con la estructura de datos del array. Aprenden sobre permutaciones y combinaciones, relaciones, gráficos y árboles al mismo tiempo que su conocimiento de programación y sofisticación y pueden hacer ejercicios de programación cada vez más interesantes que involucran estos conceptos.

Matemáticas discretas

Lógica de proposición y predicado

Álgebra de Boole

Funciones crecimiento de las funciones big-O notación

Secuencias y sumaciones

Teoría de números elementales enteros

Las técnicas de prueba inducen la inducción indirecta de la contradicción

Matrices

Contando

Principio del agujero de la paloma

Permutaciones y combinaciones

Probabilidad discreta

Relaciones de recurrencia de definiciones recursivas

Relaciones: propiedades aplicaciones representación cierre equivalencia

Gráficos: representación terminológica isomorfismo trayectorias de conectividad

 

Aplicaciones de las Matemáticas Discretas

La informática teórica incluye áreas de matemáticas discretas relevantes para la informática. Se basa en la teoría de los gráficos y la lógica. Dentro de la ciencia informática teórica se incluye el estudio de algoritmos para calcular resultados matemáticos. La computabilidad estudia lo que se puede calcular en principio y tiene estrechos vínculos con la lógica, mientras que la complejidad estudia el tiempo que toman los cálculos. La teoría de los autómatas y la teoría formal del lenguaje están estrechamente relacionadas con la computabilidad. Las redes de Petri y las álgebras de proceso se usan para modelar sistemas informáticos, y los métodos de la matemática discreta se utilizan en el análisis de circuitos electrónicos VLSI. La geometría computacional aplica algoritmos a problemas geométricos, mientras que el análisis de imágenes por ordenador los aplica a representaciones de imágenes. La informática teórica también incluye el estudio de varios temas computacionales continuos.

 Teoría de la información

La teoría de la información implica la cuantificación de la información. Estrechamente relacionada es la teoría de la codificación que se utiliza para diseñar métodos de transmisión y almacenamiento de datos eficientes y fiables. La teoría de la información también incluye temas continuos como señales analógicas, codificación analógica, cifrado analógico y lógica matemática.

Lógica matemática

La lógica es el estudio de los principios de razonamiento e inferencia válidos, así como de consistencia, solidez e integridad. Por ejemplo, en la mayoría de los sistemas de lógica (pero no en la lógica intuicionista) la ley de Peirce (((P → Q) → P) → P) es un teorema. Para la lógica clásica, se puede verificar fácilmente con una tabla de verdad. El estudio de la prueba matemática es particularmente importante en la lógica, y tiene aplicaciones a la comprobación automatizada del teorema.

Las fórmulas lógicas son estructuras discretas, al igual que las pruebas, que forman árboles finitos o, más generalmente, estructuras de grafos acíclicas dirigidas (con cada paso de inferencia combinando una o más ramas de premisa para dar una sola conclusión). Los valores de verdad de las fórmulas lógicas generalmente forman un conjunto finito, generalmente restringido a dos valores: verdadero y falso, pero la lógica también puede ser de valor continuo, por ejemplo, lógica difusa. También se han estudiado conceptos tales como árboles de prueba infinita o árboles de derivación infinita.

Teoría de conjuntos

La teoría de conjuntos es la rama de la matemática que estudia conjuntos, que son colecciones de objetos, como {azul, blanco y rojo} o el conjunto (infinito) de todos los números primos. Conjuntos y conjuntos parcialmente ordenados con otras relaciones que tienen aplicaciones en varias áreas.

Conjunto de teoría de intersección de dos conjuntos

En la matemática discreta, los conjuntos contables (incluidos los conjuntos finitos) son el foco principal. El principio de la teoría de conjuntos como una rama de las matemáticas suele estar marcado por el trabajo de Georg Cantor que distingue entre diferentes tipos de conjunto infinito, motivado por el estudio de series trigonométricas, y el desarrollo posterior de la teoría de conjuntos infinitos está fuera del alcance de la matemática discreta. De hecho, el trabajo contemporáneo en la teoría descriptiva de conjuntos hace un uso extensivo de las matemáticas continuas tradicionales.

Combinatoria

Combinatorias estudia la forma en que se pueden combinar o organizar estructuras discretas. La combinatoria enumerativa se concentra en contar el número de ciertos objetos combinatorios. La forma de doce proporciona un marco unificado para contar las permutaciones, combinaciones y particiones. La combinatoria analítica se refiere a la enumeración (es decir, la determinación del número) de estructuras combinatorias utilizando herramientas de análisis complejo y teoría de probabilidad. En contraste con la combinatoria enumerativa que utiliza fórmula combinatoria explícita y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo obtener una fórmula asintótica. La teoría del diseño es un estudio de diseños combinatorios, que son colecciones de subconjuntos con ciertas propiedades de intersección.




La teoría de la partición estudia diferentes enumeraciones y problemas asintóticos relacionados con particiones enteras, y está estrechamente relacionada con la serie q, funciones especiales y polinomios ortogonales. Originalmente una parte de la teoría numérica y el análisis, la teoría de la partición se considera ahora una parte de la combinatoria o un campo independiente. La teoría de órdenes es el estudio de conjuntos parcialmente ordenados, tanto finitos como infinitos.

Geometría discreta y geometría computacional

Teoría de grafos

La teoría de los gráficos, el estudio de los gráficos y las redes, se considera a menudo parte de la combinatoria, pero ha crecido lo suficientemente grande y lo suficientemente distinta, con su propio tipo de problemas, para ser considerado como un tema en sí mismo. Los gráficos son uno de los objetos principales del estudio en la matemática discreta. Están entre los modelos más ubicuos de estructuras naturales y humanas. Pueden modelar muchos tipos de relaciones y dinámicas de proceso en sistemas físicos, biológicos y sociales. En informática, pueden representar redes de comunicación, organización de datos, dispositivos computacionales, flujo de cómputo, etc. En matemáticas, son útiles en geometría y ciertas partes de topología. Teoría del nudo. La teoría del grafo algebraico tiene lazos cercanos con la teoría del grupo. También hay gráficos continuos, sin embargo, en su mayor parte, la investigación en la teoría de los gráficos pertenece al dominio de la matemática discreta.

 

Teoría de la probabilidad discreta

La teoría de la probabilidad discreta trata de los eventos que ocurren en los espacios de muestra contable. Por ejemplo, las observaciones de conteo, tales como el número de aves en manadas, comprenden sólo valores numéricos naturales {0, 1, 2,}. Por otro lado, las observaciones continúas tales como los pesos de las aves comprenden valores de números reales y normalmente se modelarían mediante una distribución de probabilidad continua como la normal. Las distribuciones discretas de probabilidad se pueden utilizar para aproximar las continuas y viceversa. Para situaciones muy restringidas tales como lanzar dados o experimentos con barajas de cartas, calcular la probabilidad de eventos es básicamente enumerativo.

Dados de la teoría de la probabilidad discreta

Teoría de los números

La teoría numérica se ocupa de las propiedades de los números en general, particularmente los enteros. Tiene aplicaciones a la criptografía, criptoanálisis y criptología, particularmente con respecto a la aritmética modular, ecuaciones diofantinas, congruencias lineales y cuadráticas, números primos y principalmente pruebas. Otros aspectos discretos de la teoría numérica incluyen la geometría de los números. En la teoría del número analítico, también se utilizan técnicas de matemáticas continuas. Los temas que van más allá de los objetos discretos incluyen números trascendentales, aproximación diofantina y campos de análisis y funciones.

Las estructuras algebraicas se presentan tanto como ejemplos discretos como ejemplos continuos. Las álgebras discretas incluyen: Álgebra booleana usada en puertas lógicas y programación; Álgebra relacional utilizada en bases de datos; Las versiones discretas y finitas de grupos, anillos y campos son importantes en la teoría de la codificación algebraica; Semi grupos discretos y monodies aparecen en la teoría de lenguajes formales.

Geometría discreta y geometría computacional

La geometría discreta y la geometría combinatoria se refieren a las propiedades combinatorias de las colecciones discretas de objetos geométricos. Un tema de larga data en la geometría discreta es el embaldosado del plano. La geometría computacional aplica algoritmos a problemas geométricos.

 

Árboles

Los árboles se utilizan para representar datos que tienen alguna relación jerárquica entre los elementos de datos.

Árbol de estructura discreta

Topología

Aunque la topología es el campo de las matemáticas que formaliza y generaliza la noción intuitiva de “deformación continua” de los objetos, da lugar a muchos temas discretos; Esto se puede atribuir en parte al enfoque en invariantes topológicos, que usualmente toman valores discretos. Ver topología combinatoria, teoría de los gráficos topológicos, combinatoria topológica, topología computacional, espacio topológico discreto, espacio topológico finito, topología (química).

CONCLUSIONES

Enfatizamos el papel esencial que desempeña la matemática en el desarrollo de la programación tanto para el conocimiento particular como para las habilidades de razonamiento asociadas con la madurez matemática. Hacemos hincapié en la importancia de ciertos conceptos matemáticos para la informática.

One Response

  1. Luis septiembre 19, 2017

Leave a Reply