Matemática discreta

La matemática discreta es un área de la matemática encargada del estudio de los conjuntos discretos: finitos o infinitos numerables.

En oposición a la matemática continua, que se encargan del estudio de conceptos como la continuidad y el cambio continuo, la matemática discreta estudia estructuras cuyos elementos pueden contarse uno por uno separadamente. Es decir, los procesos en matemática discreta son contables, como por ejemplo, los números enteros, grafos y sentencias de lógica.​​​​

Mientras que el análisis real está fundado en el conjunto de los números reales los cuales no son numerables, la matemática discreta es la base de todo lo relacionado con los números naturales y/o conjuntos numerables.

Son fundamentales para la ciencia de la computación, porque solo son computables las funciones de conjuntos numerables.^{[cita requerida]}

La clave en matemática discreta es que no es posible manejar las ideas de proximidad o límite y suavidad en las curvas, como se puede en el análisis. Por ejemplo, en matemática discreta una incógnita puede ser 2 o 3, pero nunca se aproximará a 3 por la izquierda con 2.9, 2.99, 2.999, etc. Las gráficas en matemática discreta vienen dadas por un conjunto finito de puntos que se pueden contar por separado; es decir, sus variables son discretas o digitales, mientras que las gráficas en cálculo son trazos continuos de rectas o curvas; es decir, sus variables son continuas o analógicas.

Historia

La matemática discreta ha visto un gran número de problemas difíciles de resolver. En teoría de grafos, mucha de la investigación realizada en sus inicios fue motivada por intentos para probar el teorema de los cuatro colores, el cual fue probado más de cien años después de su inicial descripción. El problema de los puentes de Königsberg, un problema clásico del prolífico Leonhard Euler.

En lógica, el segundo problema de la lista de problemas abiertos de David Hilbert, era probar que los axiomas de la aritmética son consistentes. El segundo teorema de Gödel de la incompletitud probó en 1931 que esto no es posible, por lo menos dentro de la aritmética en sí. El décimo problema de Hilbert era determinar si un polinomio diofántico con coeficientes enteros dado tiene una solución entera. En 1970, Yuri Matiyasevich probó que esto es imposible de hacer.

La necesidad de descifrar códigos alemanes en la Segunda Guerra Mundial dio paso a avances en la criptografía y la ciencia computacional teórica, con el primera computadora electrónica, digital y programable desarrollado en Inglaterra. Al mismo tiempo, requerimientos militares motivaron avances en la investigación de operaciones. La Guerra Fría tuvo significancia en la criptografía, y la mantuvo vigente, con lo que se realizaron avances en la criptografía asimétrica.

Actualmente, uno de los problemas abiertos más famosos en la teoría de la informática es el problema de las clases de complejidad "P = NP". El Clay Mathematics Institute ha ofrecido un premio de un millón de dólares para la primera demostración correcta, junto con premios para 6 problemas más.

Tópicos en la matemática discreta

Informática teórica

La complejidad estudia el tiempo en el cual un algoritmo se ejecuta.

La teoría de la informática incluye áreas de la matemática discreta relevante a la computación. Está altamente relacionada con teoría de grafos y lógica. Dentro de la teoría de la informática se encuentra la teoría de algoritmos para problemas matemáticos. La computabilidad estudia lo que puede ser computado y tiene lazos fuertes con la lógica, mientras que la complejidad estudia el tiempo que se necesita para hacer los cálculos. La teoría de autómatas, los lenguajes formales y la Dinámica de sistemas se relacionan de manera cercana con la computabilidad. Las redes de Petri y álgebra de procesos se usan para modelar sistemas de cálculo, y los métodos de la matemática discreta se usan para analizar circuitos VLSI. La geometría computacional aplica algoritmos a problemas geométricos, mientras que el análisis digital de imágenes los aplica a representaciones de imágenes. La teoría informática también incluye el estudio de tópicos de informática continua.

Teoría de la información

Los códigos mostrados aquí son una manera de representar una palabra en teoría de la información, como también para algoritmos de proceso de información.

La teoría de la información se ve involucrada en la cuantificación de la información. Cercanamente relacionado con esto es la teoría de codificación, que es usada 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 tópicos continuos tales como señales análogicas, codificación análoga y cifrado análogo.

Lógica

La lógica es el estudio de los principios del razonamiento válido y la inferencia, como también de la consistencia, solidez y completitud. Por ejemplo, en la mayoría de los sistemas en la lógica, la ley de Peirce, (((P→Q)→P)→P) es un teorema. En lógica clásica, puede ser fácilmente verificado con una tabla de verdad. El estudio de las demostraciones matemáticas es particularmente importante en lógica y tiene aplicaciones en la demostración automática de teoremas y verificación formal de software.

Las fórmulas lógicas son estructuras discretas, como lo son las demostraciones, las cuales forman árboles finitos, o más generalmente, estructuras de grafos acíclicos (en cada paso de inferencia combinando una o más ramas de premisas para dar una sola conclusión). Las tablas de verdad de fórmulas lógicas usualmente forman un conjunto finito, generalmente restringido a dos valores: verdadero y falso, pero la lógica puede tener valores continuos, por ejemplo en la lógica difusa. Los conceptos como árboles de demostraciones o derivaciones infinitas también han sido estudiados, por ejemplo en la lógica proposicional infinitaria.

Teoría de conjuntos

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

En la matemática discreta, los conjuntos numerables (incluyendo conjuntos finitos) son el principal objeto de estudio. El inicio de la teoría de conjuntos generalmente se relaciona con el trabajo de Georg Cantor, haciendo distinción entre diferentes tipos de conjuntos infinitos, motivado por el estudio de las series trigonométricas. El desarrollo más profundo en la teoría de conjuntos infinitos está fuera del alcance de la matemática discreta. De hecho, el trabajo contemporáneo en teoría descriptiva de conjuntos hace uso extenso del uso de la matemática continua tradicional.

Combinatoria

La combinatoria es la rama de la matemática que estudia colecciones finitas de objetos que pueden ser combinados u ordenados.

La combinatoria enumerativa se ocupa, en particular, del "recuento" de los objetos de dichas colecciones.

La combinatoria analítica se concentra en la enumeración de estructuras combinatorias utilizando herramientas de análisis complejo y teoría de probabilidad. En contraste con la combinatoria enumerativa, que usa fórmulas combinatorias explícitas y funciones generatrices para describir los resultados, la combinatoria analítica se enfoca en obtener fórmulas asintóticas.

La teoría de diseño es el estudio de diseños combinatorios, que son clases de subconjuntos con ciertas propiedades numéricas de intersección.

La teoría de particiones estudia varios problemas asintóticos y de enumeración relacionados con particiones enteras, y está relacionada con series q, funciones especiales y polinomios ortogonales. Originalmente una parte de teoría numérica y análisis, la teoría de particiones es considerada una parte de combinatoria, o un área independiente.

La teoría del orden es el estudio de conjuntos parcialmente ordenados, finitos e infinitos.

Teoría de grafos

La teoría de grafos se relaciona estrechamente con la Teoría de grupos. Este grafo de un tetraedro truncado está relacionado con el grupo alternado A₄.

La teoría de grafos es el estudio de grafos y la teoría de redes. Generalmente es considerada parte de la Combinatoria, pero ha evolucionado por su parte lo suficiente como para ser considerada una materia por sí misma.​ La teoría de grafos tiene extensas aplicaciones en todas las áreas de la matemática y la ciencia. Existen, incluso, grafos continuos.

Teoría de distribuciones de probabilidad discretas

La teoría de distribuciones discretas trata con eventos que ocurren en espacios de muestra numerables. Por ejemplo, conteos como el número de aves en una bandada solo pueden tener valores naturales {0, 1, 2,...}. Por otra parte, observaciones continuas como los pesos de estas aves se pueden representar mediante números reales, y típicamente serían modelados por una distribución de probabilidad continua, como por ejemplo, la distribución normal. Distribuciones continuas pueden ser utilizadas para aproximar discretas y viceversa. Para situaciones en las cuales los valores posibles son altamente restringidos en su variabilidad, como por ejemplo en dados o cartas, calcular las probabilidades simplemente necesita de combinatoria enumerativa.

Teoría de números

La espiral de Ulam muestra aquí, en cada pixel negro, un número primo. Este diagrama muestra una posible pista sobre la distribución de los números primos.

La teoría de números principalmente tiene que ver con las propiedades de los números en general y, particularmente, de los enteros. Tiene aplicaciones en la criptografía, criptoanálisis y criptología, particularmente en lo que refiere a números primos. Otros aspectos de la teoría de números incluye la teoría geométrica de números. En la teoría analítica de números, también se utilizan técnicas de matemática continua.

Álgebra

Las estructuras algebraicas ocurren discreta y continuamente. Como ejemplos de álgebras discretas están: el álgebra booleana, utilizada en circuitos digitales y programación, álgebra relacional, utilizada en bases de datos; grupos, finitos y discretos, así como anillos y campos son importantes en la teoría de códigos.

Cálculo de diferencias finitas

Una función definida en un intervalo de enteros se llama sucesión. Una sucesión puede ser una finita o infinita. Tal función discreta puede ser definida explícitamente por una lista (si su dominio es finito), o por una fórmula para su término n-esimo, o también puede ser dada implícitamente por una relación de recurrencia o ecuación de diferencia. Las ecuaciones de diferencia son similares a las ecuaciones diferenciales pero se reemplazan las derivadas tomando la diferencia entre términos adyacentes y pueden ser utilizadas para aproximar ecuaciones diferenciales. Muchas interrogantes y métodos de las ecuaciones diferenciales tienen sus contrapartes para ecuaciones de diferencias.

Geometría discreta

La geometría computacional aplica algoritmos a representaciones de objetos geométricos.

La geometría discreta y la geometría combinatoria tratan las propiedades combinatorias de colecciones discretas de objetos geométricos. Un antiguo tópico en la geometría discreta es el recubrimiento del plano. La geometría computacional aplica algoritmos a problemas geométricos.

Topología

Si bien la topología general es el campo de las matemáticas que formaliza y generaliza la noción intuitiva de "deformación continua" de los objetos, o el proceso de límite, da paso a muchos tópicos discretos. Esto puede ser atribuido en parte a la atención que se le da a los invariantes topológicos, que toman, por lo general, valores discretos. Entre sus ramas de estudio se encuentran la topología combinatoria, topología de grafos, topología computacional y topología algebraica, entre otros.

Investigación Operativa

Diagramas PERT como este, proveen técnicas de administración de negocios basados en teoría de grafos.

La investigación operativa es una rama de las matemáticas consistente en el uso de modelos matemáticos, estadística y algoritmos con objeto de realizar un proceso de toma de decisiones prácticas para negocios y otras áreas. Estos problemas pueden ser, por ejemplo, la repartición de recursos para maximizar ingresos, o agendar actividades para minimizar riesgos. Técnicas propias de la investigación de operaciones incluyen programación lineal y otras áreas de optimización, teoría de colas, algoritmos de planificación, análisis de redes. La investigación de operaciones también incluye tópicos continuos como procesos de Markov de tiempo continuo, optimización de procesos, martingalas de tiempo continuo, etc.

Teoría de juegos, teoría de la decisión, teoría de utilidad

Matriz de ganancias del dilema del prisionero, un ejemplo común de juego. Un jugador elige una fila y el otro una columna; el par resultante dicta sus ganancias.

La teoría de la decisión trata fundamentalmente con identificar los valores, incertidumbres y otros factores relevantes en una decisión, su racionalidad y la decisión óptima resultante.

La teoría de utilidades es sobre medidas de la relativa satisfacción económica proveniente del consumo de algún bien o servicio.

La teoría de juegos trata con las situaciones donde el éxito depende de las decisiones de otros, lo cual hace elegir el mejor curso de acción más complejo. Tópicos incluyen la Teoría de subasta y la división justa.

La teoría de decisión social estudia las elecciones.

Discretización

La discretización busca transformar modelos y ecuaciones continuos en sus contrapartes discretas,​ usualmente para hacer cálculos más fácilmente utilizando aproximaciones. El análisis numérico es un importante ejemplo.

Véase también

• álgebra lineal – el estudio de funciones lineales relacionadas.
• algoritmia – el estudio de métodos de cálculos.
• combinatoria
• investigación de operaciones
• lógica – el estudio del razonamiento
• probabilidad y cadenas de Markov
• teorías de la computabilidad y de la complejidad - que tratan sobre la viabilidad y límites de los algoritmos
• teoría de conjuntos – estudio de colecciones de objetos
• teoría de grafos
• teoría de la información
• teoría de números
• topología algebraica

Bibliografía

• Biggs, Norman L. (2002). Discrete Mathematics. Oxford University Press. ISBN 978-0-19-850717-8. 
• Dwyer, John (2010). An Introduction to Discrete Mathematics for Business & Computing. ISBN 978-1-907934-00-1. 
• Epp, Susanna S. (4 de agosto de 2010). Discrete Mathematics With Applications. Thomson Brooks/Cole. ISBN 978-0-495-39132-6. 
• Graham, Ronald; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (2nd edición). Addison–Wesley. ISBN 0-201-55802-5. 
• Grimaldi, Ralph P. (2004). Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. ISBN 978-0-201-72634-3. 
• Knuth, Donald E. (2011). The Art of Computer Programming. 1–4a Boxed Set. Addison-Wesley. ISBN 978-0-321-75104-1. 
• Matoušek, Jiří; Nešetřil, Jaroslav (1998). Discrete Mathematics. Oxford University Press. ISBN 978-0-19-850208-1. 
• Obrenic, Bojana (2003). Practice Problems in Discrete Mathematics. Prentice Hall. ISBN 978-0-13-045803-2. 
• Rosen, Kenneth H.; Michaels, John G. (2000). Hand Book of Discrete and Combinatorial Mathematics. CRC Press. ISBN 978-0-8493-0149-0. 
• Rosen, Kenneth H. (2007). Discrete Mathematics: And Its Applications. McGraw-Hill. ISBN 978-0-07-288008-3. 
• Simpson, Andrew (2002). Discrete Mathematics by Example. McGraw-Hill. ISBN 978-0-07-709840-7. 

Enlaces externos

• matemáticas discretas Archivado el 29 de agosto de 2011 en Wayback Machine. (en inglés)

• Datos: Q121416
• Multimedia: Discrete mathematics / Q121416