Las matemáticas discretas son el estudio de estructuras matemáticas que pueden considerarse "discretas" (de manera análoga a las variables discretas , que tienen una biyección con el conjunto de 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áficos y enunciados en lógica . [1] [2] [3] Por el contrario, las matemáticas discretas excluyen temas de "matemáticas continuas" como números reales , cálculo o geometría euclidiana . Los objetos discretos a menudo pueden enumerarse por números enteros ; más formalmente, las matemáticas discretas se han caracterizado como la rama de las matemáticas que trata con 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 que se estudia en las 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 tratan 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 significativas para aplicar ideas de las 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 las 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; sus contenidos eran un tanto caóticos en ese momento. Posteriormente, el plan de estudios se desarrolló en conjunto con los esfuerzos de la ACM y la MAA hasta convertirse en un curso que está destinado básicamente a desarrollar la madurez matemática en los estudiantes de primer año; por lo tanto, hoy en día también es un prerrequisito para las carreras de matemáticas en algunas universidades. [6] [7] También han aparecido algunos libros de texto de matemáticas discretas de nivel secundario. [8] En este nivel, las matemáticas discretas a veces se consideran un curso preparatorio, como el precálculo en este sentido. [9]
El Premio Fulkerson se otorga por artículos destacados en matemáticas discretas.
La informática teórica incluye áreas de matemáticas discretas relevantes para la computación. 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 que se utilizan para los cálculos. La teoría de autómatas y la teoría del lenguaje formal están estrechamente relacionadas con la computabilidad. Las redes de Petri y las álgebras de procesos se utilizan para modelar sistemas informáticos, y los métodos de las 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 varios temas computacionales continuos.
La teoría de la información implica la cuantificación de la información . Estrechamente relacionada con ella 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 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 .
La lógica es el estudio de los principios de razonamiento válido e inferencia , así como de consistencia , solidez y completitud . 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 para la demostración automatizada de teoremas y la verificación formal del software.
Las fórmulas lógicas son estructuras discretas, al igual que las pruebas , que forman árboles finitos [10] o, más generalmente, estructuras de grafos acíclicos dirigidos [11] [12] (con cada paso de inferencia combinando una o más ramas de premisa 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, [13] por ejemplo , la lógica infinitaria .
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 comienzo 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 el desarrollo posterior de la teoría de conjuntos infinitos queda fuera del ámbito de las matemáticas discretas. 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 las formas en que las estructuras discretas pueden combinarse u organizarse. La combinatoria enumerativa se concentra en contar el número de ciertos objetos combinatorios; por ejemplo, el método de doce pasos 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 ocupa del uso de técnicas de la topología y la topología algebraica / topología combinatoria en la combinatoria . La teoría del diseño es un estudio de los diseños combinatorios , que son colecciones de subconjuntos con ciertas propiedades de intersección . La teoría de la partición estudia varios problemas de enumeración y asintóticos relacionados con particiones enteras , y está estrechamente relacionada con las series q , las funciones especiales y los polinomios ortogonales . La teoría de particiones, que originalmente formaba parte de la teoría y el análisis de números , 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 ha crecido lo suficiente y se ha diferenciado lo suficiente, con su propio tipo de problemas, como para ser considerada como un tema por derecho propio. [14] Los grafos 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 computación, 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 algebraicos 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 grafos 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 números enteros . Tiene aplicaciones en la criptografía y el criptoanálisis , particularmente en lo que respecta a la aritmética modular , las ecuaciones diofánticas , las congruencias lineales y cuadráticas, los números primos y las 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 de las matemáticas continuas. Los temas que van más allá de los objetos discretos incluyen los números trascendentales , la aproximación diofántica , el análisis p-ádico y los cuerpos de funciones .
Las estructuras algebraicas se dan tanto como ejemplos discretos como continuos. Las álgebras discretas incluyen: el álgebra de Boole, utilizada en puertas lógicas y programación; el álgebra relacional, utilizada en bases de datos ; las versiones discretas y finitas de grupos , anillos y cuerpos son importantes en la teoría de codificación algebraica ; los semigrupos discretos y los monoides aparecen en la teoría de lenguajes formales .
Hay muchos conceptos y teorías en matemáticas continuas que tienen versiones discretas, como el cálculo discreto , las transformadas de Fourier discretas , la geometría discreta , los logaritmos discretos , la geometría diferencial discreta , el cálculo exterior discreto , la teoría de Morse discreta , la optimización discreta , la teoría de probabilidad discreta , la distribución de probabilidad discreta , las ecuaciones diferenciales , los sistemas dinámicos discretos y las medidas vectoriales discretas .
En cálculo discreto y cálculo de diferencias finitas , una función definida en un intervalo de números enteros se denomina habitualmente secuencia . Una secuencia puede 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 puede definirse explícitamente mediante una lista (si su dominio es finito), o mediante una fórmula para su término general, o puede darse implícitamente mediante una relación de recurrencia o una ecuación diferencial . Las ecuaciones diferenciales son similares a las ecuaciones diferenciales , pero sustituyen la diferenciación tomando la diferencia entre términos adyacentes; pueden utilizarse para aproximar ecuaciones diferenciales o (más a menudo) estudiarse por derecho propio. Muchas preguntas y métodos relacionados con las ecuaciones diferenciales tienen contrapartes para las ecuaciones diferenciales. Por ejemplo, donde hay transformadas integrales en el análisis armónico para estudiar funciones continuas o señales analógicas, hay 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 a escala temporal es una unificación de la teoría de ecuaciones diferenciales con la de ecuaciones diferenciales , que tiene aplicaciones en campos que requieren el modelado simultáneo de datos discretos y continuos. Otra forma de modelar una situación de este tipo es la noción de sistemas dinámicos híbridos .
La geometría discreta y la geometría combinatoria tratan sobre las propiedades combinatorias de conjuntos discretos de objetos geométricos. Un tema de larga data en la geometría discreta es el teselado del plano .
En geometría algebraica , el concepto de curva se puede extender a geometrías discretas tomando los espectros de anillos polinómicos sobre cuerpos finitos como modelos de los espacios afines sobre ese cuerpo, 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 para un cuerpo se puede estudiar como , un punto, o como el espectro del anillo local en (xc) , un punto junto con un entorno a su alrededor. Las variedades algebraicas también tienen una noción bien definida de espacio tangente llamado 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 propósito 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 en á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). [15]
En lógica , el segundo problema de la lista de problemas abiertos de David Hilbert , presentado en 1900, era demostrar que los axiomas de la aritmética son consistentes . El segundo teorema de incompletitud de Gödel , demostrado en 1931, mostraba 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 se podía hacer .
La necesidad de descifrar códigos alemanes en la Segunda Guerra Mundial condujo a avances en criptografía y ciencia informática teórica , con el primer ordenador electrónico digital programable desarrollado en Bletchley Park, Inglaterra, con la guía de Alan Turing y su obra seminal, On Computable Numbers. [16] La Guerra Fría significó que la criptografía siguió siendo importante, con avances fundamentales como la criptografía de clave pública que se desarrolló en las décadas siguientes. La industria de las telecomunicaciones también ha motivado avances en matemáticas discretas, particularmente en teoría de grafos y teoría de la información . La verificación formal de declaraciones en lógica 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 de 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 de bioinformática asociados con la comprensión del árbol de la vida . [17]
En la actualidad, uno de los problemas abiertos más famosos en la informática teórica es el problema P = NP , que involucra la relación entre las clases de complejidad P y NP . El Instituto de Matemáticas Clay ha ofrecido un premio de 1 millón de dólares estadounidenses para la primera demostración correcta, junto con premios para otros seis problemas matemáticos . [18]
Las matemáticas discretas son la rama de las matemáticas en la que tratamos cuestiones que involucran conjuntos finitos o infinitos contables.
![{\displaystyle V(xc)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/147df15a1780a002602cd26438adbec315699e2b)
![{\displaystyle \operatorname {Espec} K[x]/(xc)\cong \operatorname {Espec} 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)
