- Matemáticas discretas
-
Las matemáticas discretas son un área de las matemáticas encargadas del estudio de los conjuntos discretos: finitos o infinitos numerables. En oposición a las matemáticas continuas, que se encarga del estudio de conceptos como la continuidad y el cambio continuo, la matemáticas discretas estudian estructuras cuyos elementos pueden contarse uno por uno separadamente. Es decir, los procesos en matemáticas discretas son contables, como por ejemplo, los números enteros, grafos y sentencias de lógica.[1]
Mientras que el cálculo infinitesimal es primordial en el estudio de procesos analógicos, la matemática discreta es la base de todo lo relacionado con los procesos digitales, y por tanto, se constituye en parte fundamental de la ciencia de la computación, una de las ramas de estudio impartidas en los estudios de Ingeniería Informática.
La clave en matemáticas discretas es que no es posible manejar las ideas de proximidad o límite y suavidad en las curvas, como se puede en el cálculo. Por ejemplo, en matemáticas discretas una incógnita puede ser 2 ó 3, pero nunca se aproximará a 3 por la izquierda con 2.9, 2.99, 2.999, etc. Las gráficas en matemáticas discretas 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 historia de las matemáticas discretas 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.
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 burlar códigos Alemanes en la Segunda Guerra Mundial dio paso a avances en la criptografía y la ciencia computacional teórica, con el primer computador electrónico, 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, manteniéndola vigente, realizándose 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 demora en hacer computaciones. La teoría de autómatas y los lenguajes formales se relacionan de manera cercana con la computabilidad. Las redes de Petri y álgebra de procesos se usan para modelar sistemas computacionales, y 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 a 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álogas, codificación análoga y cifrado análogo.
Lógica
La lógica es el estudio de los principios del razonamiento valido 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 demostraciónes, 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 explicitas y funciones generadoras 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 A4.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 si misma.[2] 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 serian 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 numero primo. Este diagrama muestra una posible pista sobre la distribucion 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, técnicas de matemática continua también son utilizadas.
Á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 secuencia. Una secuencia 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
La geometría discreta y 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 es el campo de las matemáticas que formaliza y generaliza la noción intuitiva de "deformación continua" de los objetos, da a 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. Ramas de esta hay, por ejemplo: topología combinatoria, topología de grafos, topología computacional.
Investigación de operaciones
Diagramas PERT como este, proveen técnicas de administración de negocios basados en teoría de grafos.La investigación de operaciones 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.
Discretizacion
La discretización busca transformar modelos y ecuaciones continuos en sus contrapartes discretas,[3] usualmente para hacer cálculos mas fácilmente utilizando aproximaciones. El análisis numérico es un importante ejemplo.
Véase también
- Lógica – el estudio del razonamiento
- Teoría de conjuntos – estudio de colecciones de objetos
- Teoría de números
- Combinatoria
- Teoría de grafos
- Algoritmia – el estudio de métodos de cálculos.
- Teoría de la información
- Teorías de la Computabilidad y complejidad - que tratan sobre la viabilidad y límites de los algoritmos.
- Probabilidad y Cadenas de Markov
- Álgebra lineal – el estudio de funciones lineales relacionadas.
- http://archives.math.utk.edu/topics/discreteMath.html (en inglés)
- Topología algebraica
- Investigación de operaciones
Referencias
- ↑ Definición, Wolfram
- ↑ Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, John Hopkins University press, 2001
- ↑ http://ccc.inaoep.mx/~emorales/Cursos/KDD/node155.html Discretización de Valores
Categorías:- Matemáticas discretas
- Terminología matemática
Wikimedia foundation. 2010.
