Matemáticas discretas

Las matemáticas discretas son el estudio de estructuras matemáticas que pueden considerarse "discretas" (de forma análoga a las variables discretas, que tienen una biyección con el conjunto de números naturales) en lugar de "continuas" (análogamente a las funciones continuas). Los objetos estudiados en matemáticas discretas incluyen números enteros, gráficos y declaraciones en lógica. 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 se pueden enumerar 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 los conjuntos contables (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".

El conjunto de objetos estudiados en matemáticas discretas puede ser finito o infinito. El término matemáticas finitas a veces se aplica 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 estudios universitarios, "Matemáticas Discretas" apareció en la década de 1980, inicialmente como un curso de apoyo a la informática; su contenido era algo desordenado en ese momento. A partir de entonces, el plan de estudios se ha desarrollado junto con los esfuerzos de ACM y MAA 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 los estudiantes de matemáticas en algunas universidades. También han aparecido algunos libros de texto de matemáticas discretas de nivel secundario. En este nivel, las matemáticas discretas a veces se ven como un curso preparatorio, no muy diferente del precálculo en este sentido.

El Premio Fulkerson se otorga por trabajos destacados en matemáticas discretas.

Grandes desafíos, pasados ​​y presentes

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 la teoría de grafos, gran parte de la investigación estuvo motivada por los intentos de probar el teorema de los cuatro colores, establecido por primera vez en 1852, pero no probado hasta 1976 (por Kenneth Appel y Wolfgang Haken, utilizando una importante ayuda informática).

En lógica, el segundo problema en la lista de problemas abiertos de David Hilbert presentado en 1900 fue probar 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 aritmética misma. El décimo problema de Hilbert era determinar si una ecuación diofántica polinomial 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 los códigos alemanes en la Segunda Guerra Mundial condujo a avances en la criptografía y la informática teórica, con el desarrollo de la primera computadora electrónica digital programable en Bletchley Park de Inglaterra con la guía de Alan Turing y su obra fundamental, Sobre números computables. La Guerra Fría significó que la criptografía siguiera 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 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 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.

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 para la primera prueba correcta, junto con premios para otros seis problemas matemáticos.

Temas de matemáticas discretas

Informática teórica

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. Incluido dentro de la informática teórica está 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 necesarios para los cálculos. La teoría de los autómatas y la teoría del lenguaje formal están estrechamente relacionadas con la computabilidad. Las redes de Petri y el álgebra de proceso se utilizan para modelar sistemas informáticos, y los 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.

Teoría de la información

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 eficientes y fiables de transmisión y almacenamiento de datos. La teoría de la información también incluye temas continuos como: señales analógicas, codificación analógica, encriptación analógica.

Lógica

La lógica es el estudio de los principios del razonamiento y la inferencia válidos, así como de la coherencia, la solidez y la 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 lógica y tiene aplicaciones para la prueba 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 o, más generalmente, estructuras gráficas acíclicas dirigidas (con cada paso de inferencia que 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 ser de valores continuos, por ejemplo, lógica difusa. También se han estudiado conceptos como árboles de prueba infinita o árboles de derivación infinita, por ejemplo, lógica infinita.

Teoría de conjuntos

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 enfoque 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 series trigonométricas, y el desarrollo posterior de la teoría de conjuntos infinitos está fuera del alcance de las matemáticas discretas. De hecho, el trabajo contemporáneo en la teoría descriptiva de conjuntos hace un uso extensivo de las matemáticas continuas tradicionales.

Combinatoria

La combinatoria estudia la forma en que las estructuras discretas pueden combinarse o organizarse. La combinatoria enumerativa se concentra en contar el número de ciertos objetos combinatorios; por ejemplo, la vía doce 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 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 asintóticos y de enumeración relacionados con las particiones de enteros, y está estrechamente relacionada con las series q, las funciones especiales y los polinomios ortogonales. Originalmente una 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.

Teoría de grafos

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 distintiva, con su propio tipo de problemas, como para ser considerada como un tema por derecho propio.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 hechas por el hombre. Pueden modelar muchos tipos de relaciones y procesos dinámicos 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, 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 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.

Teoría de los números

La teoría de los números se ocupa de las propiedades de los números en general, en particular de los enteros. Tiene aplicaciones a la criptografía y el criptoanálisis, particularmente con respecto a la 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 de matemáticas continuas. 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 de funciones.

Estructuras algebraicas

Las estructuras algebraicas se presentan como ejemplos discretos y 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 la codificación algebraica; los semigrupos discretos y los monoides aparecen en la teoría de los lenguajes formales.

Análogos discretos de las matemáticas continuas

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.

Cálculo de diferencias finitas, análisis discreto y cálculo discreto

En el cálculo discreto y el cálculo de diferencias finitas, una función definida en un intervalo de los números enteros suele llamarse secuencia. Una secuencia podría ser una secuencia finita de una fuente de datos o una secuencia infinita de un sistema dinámico discreto. Tal función discreta podría definirse explícitamente por una lista (si su dominio es finito), o por una fórmula para su término general, o podría estar dada implícitamente por una relación de recurrencia o una ecuación en diferencia. 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í mismos. Muchas preguntas y métodos relacionados con las ecuaciones diferenciales tienen equivalentes para las ecuaciones en diferencias. Por ejemplo, donde existen transformadas integrales en 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, espacios topológicos finitos.

El cálculo de la escala de tiempo es una unificación de la teoría de las ecuaciones en diferencias con la de las ecuaciones diferenciales, que tiene aplicaciones en campos que requieren el 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.

Geometría discreta

La geometría discreta y la geometría combinatoria tratan sobre las 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 polinómicos 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 configuraciones continuas. Por ejemplo, cada punto de la forma de un campo se puede estudiar como , un punto o como el espectrodel 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 llamado espacio tangente de Zariski, lo que hace que muchas características del cálculo sean aplicables incluso en entornos finitos.

Modelado discreto

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