La matemática discreta es el estudio de estructuras matemáticas que pueden considerarse "discretas" (de manera análoga a las variables discretas , al tener una biyección con el conjunto de los números naturales ) en lugar de "continuas" (de manera análoga a las funciones continuas ). Los objetos estudiados en matemáticas discretas incluyen números enteros , gráficas y enunciados de lógica . [1] [2] [3] Por el contrario, las matemáticas discretas excluyen temas de "matemáticas continuas", como los números reales , el cálculo o la geometría euclidiana . Los objetos discretos a menudo pueden enumerarse mediante números enteros ; Más formalmente, las matemáticas discretas se han caracterizado como la rama de las matemáticas que se ocupa de conjuntos contables [4] (conjuntos finitos o conjuntos con la misma cardinalidad que los números naturales). Sin embargo, no existe una definición exacta del término "matemáticas discretas". [5]
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 las matemáticas discretas que se ocupan de conjuntos finitos, en particular aquellas áreas relevantes para los negocios.
La investigación en matemáticas discretas aumentó en la segunda mitad del siglo XX, en parte debido al desarrollo de computadoras digitales que operan en pasos "discretos" y almacenan datos en bits "discretos". Los conceptos y notaciones de las matemáticas discretas son útiles para estudiar y describir objetos y problemas en ramas de la informática , como algoritmos informáticos , lenguajes de programación , criptografía , demostración automatizada de teoremas y desarrollo de software . Por el contrario, las implementaciones informáticas son importantes para aplicar ideas de matemáticas discretas a problemas del mundo real.
Aunque los principales objetos de estudio en matemáticas discretas son objetos discretos, a menudo también se emplean métodos analíticos de matemáticas "continuas".
En los planes de estudio universitarios, las matemáticas discretas aparecieron en la década de 1980, inicialmente como un curso de apoyo a la informática; su contenido era algo desordenado en ese momento. Posteriormente, el plan de estudios se desarrolló junto con los esfuerzos de ACM y MAA hasta convertirse en un curso que básicamente tiene como objetivo desarrollar la madurez matemática en los estudiantes de primer año; por lo tanto, hoy en día también es un requisito previo para las carreras de matemáticas en algunas universidades. [6] [7] [8] También han aparecido algunos libros de texto de matemáticas discretas de nivel secundario. [9] En este nivel, las matemáticas discretas a veces se consideran un curso preparatorio, como el precálculo a este respecto. [10]
El Premio Fulkerson se otorga a trabajos destacados en matemáticas discretas.
La informática teórica incluye áreas de matemáticas discretas relevantes para la informática. Se basa en gran medida en la teoría de grafos y la lógica matemática . Dentro de la informática teórica se incluye el estudio de algoritmos y estructuras de datos. 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, el espacio y otros recursos utilizados por los cálculos. La teoría de los autómatas y la teoría del lenguaje formal están estrechamente relacionadas con la computabilidad. Se utilizan redes de Petri y álgebras de procesos para modelar sistemas informáticos, y métodos de matemáticas discretas se utilizan para analizar circuitos electrónicos VLSI . La geometría computacional aplica algoritmos a problemas geométricos y representaciones de objetos geométricos , mientras que el análisis de imágenes por computadora los aplica a representaciones de imágenes. La informática teórica también incluye el estudio de diversos temas computacionales continuos.
La teoría de la información implica la cuantificación de la información . Estrechamente relacionada está la teoría de la codificación , que se utiliza para diseñar métodos de transmisión y almacenamiento de datos eficientes y confiables. La teoría de la información también incluye temas continuos como: señales analógicas , codificación analógica , cifrado analógico .
La lógica es el estudio de los principios de razonamiento e inferencia válidos , así como de coherencia , solidez y exhaustividad . 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 lógica y se ha acumulado en la demostración automatizada de teoremas y la verificación formal de software.
Las fórmulas lógicas son estructuras discretas, al igual que las pruebas , que forman árboles finitos [11] o, más generalmente, estructuras gráficas acíclicas dirigidas [12] [13] (en las que cada paso de inferencia combina una o más ramas de premisas para dar una única conclusión). Los valores de verdad de las fórmulas lógicas suelen formar un conjunto finito, generalmente restringido a dos valores: verdadero y falso , pero la lógica también puede tener valores continuos, por ejemplo, la lógica difusa . También se han estudiado conceptos como árboles de prueba infinitos o árboles de derivación infinitos, [14] por ejemplo, lógica infinita .
La teoría de conjuntos es la rama de las matemáticas que estudia los conjuntos , que son colecciones de objetos, como {azul, blanco, rojo} o el conjunto (infinito) de todos los números primos . Los conjuntos parcialmente ordenados y los conjuntos con otras relaciones tienen aplicaciones en varias áreas.
En matemáticas discretas, los conjuntos contables (incluidos los conjuntos finitos ) son el foco principal. El inicio de la teoría de conjuntos como rama de las matemáticas suele estar marcado por el trabajo de Georg Cantor que distingue entre diferentes tipos de conjuntos infinitos , motivado por el estudio de las series trigonométricas, y un mayor desarrollo de la teoría de conjuntos infinitos queda fuera del ámbito de la teoría de conjuntos discretos. matemáticas. De hecho, el trabajo contemporáneo en teoría descriptiva de conjuntos hace un uso extensivo de las matemáticas continuas tradicionales.
La combinatoria 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; por ejemplo, la forma doce veces proporciona un marco unificado para contar permutaciones , combinaciones y particiones .La combinatoria analítica se ocupa de la enumeración (es decir, la determinación del número) de estructuras combinatorias utilizando herramientas del análisis complejo y la teoría de la probabilidad . A diferencia de la combinatoria enumerativa, que utiliza fórmulas combinatorias explícitas y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo obtener fórmulas asintóticas .La combinatoria topológica se refiere al uso de técnicas de topología y topología algebraica / topología combinatoria en combinatoria . 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 diversos problemas asintóticos y de enumeración relacionados con las particiones enteras , y está estrechamente relacionada con las series q , las funciones especiales y los polinomios ortogonales . Originalmente parte de la teoría y el análisis de números , la teoría de la partición ahora se considera parte de la combinatoria o un campo independiente.La teoría del orden es el estudio de conjuntos parcialmente ordenados , tanto finitos como infinitos.
La teoría de grafos, el estudio de grafos y redes , a menudo se considera parte de la combinatoria, pero se ha vuelto lo suficientemente grande y distinta, con su propio tipo de problemas, como para ser considerada como un tema por derecho propio. [15] Los gráficos son uno de los principales objetos de estudio en matemáticas discretas. Se encuentran entre los modelos más ubicuos de estructuras tanto naturales como artificiales. Pueden modelar muchos tipos de relaciones y dinámicas de procesos en sistemas físicos, biológicos y sociales. En informática, pueden representar redes de comunicación, organización de datos, dispositivos computacionales, el flujo de cálculo, etc. En matemáticas, son útiles en geometría y ciertas partes de la topología , por ejemplo, la teoría de nudos . La teoría de grafos algebraica tiene estrechos vínculos con la teoría de grupos y la teoría de grafos topológicos tiene estrechos vínculos con la topología . También hay gráficos continuos ; sin embargo, en su mayor parte, la investigación en teoría de grafos cae dentro del dominio de las matemáticas discretas.
La teoría de números se ocupa de las propiedades de los números en general, particularmente de los enteros . Tiene aplicaciones en criptografía y criptoanálisis , particularmente en lo que respecta a aritmética modular , ecuaciones diofánticas , congruencias lineales y cuadráticas, números primos y pruebas de primalidad . Otros aspectos discretos de la teoría de números incluyen la geometría de los números . En la teoría analítica de números también se utilizan técnicas procedentes de la matemática continua. Los temas que van más allá de los objetos discretos incluyen números trascendentales , aproximación diofántica , análisis p-ádico y campos funcionales .
Las estructuras algebraicas se presentan tanto como ejemplos discretos como como ejemplos continuos. Las álgebras discretas incluyen: álgebra booleana utilizada 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 codificación algebraica ; Los semigrupos discretos y los monoides aparecen en la teoría de los lenguajes formales .
Hay muchos conceptos y teorías en matemáticas continuas que tienen versiones discretas, como cálculo discreto , transformadas discretas de Fourier , geometría discreta , logaritmos discretos , geometría diferencial discreta , cálculo exterior discreto , teoría de Morse discreta , optimización discreta , teoría de probabilidad discreta , probabilidad discreta distribución , ecuaciones en diferencias , sistemas dinámicos discretos y medidas vectoriales discretas .
En cálculo discreto y cálculo de diferencias finitas , una función definida en un intervalo de números enteros suele denominarse secuencia . Una secuencia podría ser una secuencia finita de una fuente de datos o una secuencia infinita de un sistema dinámico discreto . Una función discreta de este tipo podría definirse explícitamente mediante una lista (si su dominio es finito), o mediante una fórmula para su término general, o podría estar dada implícitamente mediante una relación de recurrencia o una ecuación en diferencias . Las ecuaciones en diferencias son similares a las ecuaciones diferenciales , pero reemplazan la diferenciación tomando la diferencia entre términos adyacentes; pueden usarse para aproximar ecuaciones diferenciales o (más a menudo) estudiarse por sí solos. Muchas preguntas y métodos relacionados con las ecuaciones diferenciales tienen contrapartes para las ecuaciones en diferencias. Por ejemplo, donde existen transformadas integrales en el análisis armónico para estudiar funciones continuas o señales analógicas, existen transformadas discretas para funciones discretas o señales digitales. Además de los espacios métricos discretos , existen espacios topológicos discretos más generales , espacios métricos finitos y espacios topológicos finitos .
El cálculo de escala de tiempo es una unificación de la teoría de ecuaciones en diferencias con la de ecuaciones diferenciales , que tiene aplicaciones en campos que requieren modelado simultáneo de datos discretos y continuos. Otra forma de modelar tal situación es la noción de sistemas dinámicos híbridos .
La geometría discreta y la geometría combinatoria tratan sobre propiedades combinatorias de colecciones discretas de objetos geométricos. Un tema de larga data en geometría discreta es el mosaico del plano .
En geometría algebraica , el concepto de curva se puede extender a geometrías discretas tomando los espectros de anillos polinomiales sobre campos finitos como modelos de los espacios afines sobre ese campo, y dejando que las subvariedades o espectros de otros anillos proporcionen las curvas que se encuentran en ese espacio. Aunque el espacio en el que aparecen las curvas tiene un número finito de puntos, las curvas no son tanto conjuntos de puntos como análogos de curvas en entornos continuos. Por ejemplo, cada punto de la forma de un campo se puede estudiar como un punto, o como el espectro del anillo local en (xc) , un punto junto con una vecindad a su alrededor. Las variedades algebraicas también tienen una noción bien definida de espacio tangente llamada espacio tangente de Zariski , lo que hace que muchas características del cálculo sean aplicables incluso en entornos finitos.
En matemáticas aplicadas , el modelado discreto es el análogo discreto del modelado continuo . En el modelado discreto, las fórmulas discretas se ajustan a los datos . Un método común en esta forma de modelado es utilizar la relación de recurrencia . La discretización se refiere al proceso de transferir modelos y ecuaciones continuos a contrapartes discretas, a menudo con el fin de facilitar los cálculos mediante el uso de aproximaciones. El análisis numérico proporciona un ejemplo importante.
La historia de las matemáticas discretas ha implicado una serie de problemas desafiantes que han centrado la atención dentro de áreas del campo. En teoría de grafos, gran parte de la investigación estuvo motivada por los intentos de demostrar el teorema de los cuatro colores , enunciado por primera vez en 1852, pero no demostrado hasta 1976 (por Kenneth Appel y Wolfgang Haken, utilizando una importante ayuda informática). [dieciséis]
En lógica , el segundo problema de la lista de problemas abiertos de David Hilbert presentada en 1900 era demostrar que los axiomas de la aritmética son consistentes . El segundo teorema de incompletitud de Gödel , demostrado en 1931, demostró que esto no era posible, al menos no dentro de la propia aritmética. El décimo problema de Hilbert era determinar si una ecuación diofántica polinómica dada con coeficientes enteros tiene una solución entera. En 1970, Yuri Matiyasevich demostró que esto no era posible .
La necesidad de descifrar los códigos alemanes en la Segunda Guerra Mundial condujo a avances en criptografía y ciencias de la computación teóricas , y la primera computadora electrónica digital programable se desarrolló en Bletchley Park de Inglaterra con la guía de Alan Turing y su trabajo fundamental, On Computable Numbers. [17] La Guerra Fría significó que la criptografía siguió siendo importante, y en las décadas siguientes se desarrollaron avances fundamentales como la criptografía de clave pública . La industria de las telecomunicaciones también ha motivado avances en las matemáticas discretas, particularmente en la teoría de grafos y la teoría de la información . La verificación formal de declaraciones lógicas ha sido necesaria para el desarrollo de software de sistemas críticos para la seguridad , y los avances en la demostración automatizada de teoremas han sido impulsados por esta necesidad.
La geometría computacional ha sido una parte importante de los gráficos por computadora incorporados en los videojuegos modernos y las herramientas de diseño asistido por computadora .
Varios campos de las matemáticas discretas, en particular la informática teórica, la teoría de grafos y la combinatoria , son importantes para abordar los desafiantes problemas bioinformáticos asociados con la comprensión del árbol de la vida . [18]
Actualmente, uno de los problemas abiertos más famosos en informática teórica es el problema P = NP , que involucra la relación entre las clases de complejidad P y NP . El Clay Mathematics Institute ha ofrecido un premio de 1 millón de dólares por la primera prueba correcta, junto con premios por otros seis problemas matemáticos . [19]
Matemáticas Discretas es la rama de las Matemáticas en la que tratamos cuestiones que involucran conjuntos finitos o contablemente infinitos.
![{\displaystyle V(xc)\subset \operatorname {Especificación} K[x]=\mathbb {A} ^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![{\displaystyle \operatorname {Especificación} K[x]/(xc)\cong \operatorname {Especificación} K}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80cc3220b7c86e6d0862f1bcf3fbac3ffc0191a7)
![{\displaystyle \operatorname {Especificación} K[x]_{(xc)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e6e66e203e1805ec5b90fa25d9f0c817f28dd7)
