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 encargan 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, grafosy sentencias de lógica.1
Mientras que el cálculo infinitesimal está fundado en los números reales que no
son numerables, la matemática discreta es la base de todo lo relacionado con
los números naturales o conjuntos numerables.
Son fundamentales para la ciencia de la computación,
porque sólo son computables las funciones de conjuntos numerables.
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.
Índice
Historia[editar]
Las matemáticas discretas han
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ödelde 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 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íatuvo 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[editar]
Informática
teórica[editar]
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 computabilidadestudia 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[editar]
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[editar]
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[editar]
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[editar]
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 generadoras para describir los resultados, la
combinatoria analítica se enfoca en obtenerfó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 ypolinomios 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.
Teoría de grafos[editar]
La teoría de grafos se relaciona estrechamente con la Teoría de grupos.
Este grafo de un tetraedro truncado está relacionado con elgrupo 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[editar]
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[editar]
La espiral de Ulam muestra aquí, en cada pixel negro, unnúmero primo. Este diagrama muestra una
posible pista sobre ladistribució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[editar]
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[editar]
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[editar]
La geometría
computacional aplicaalgoritmos 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[editar]
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 de
operaciones[editar]
Diagramas PERTcomo
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 incluyenprogramació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[editar]
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.
Discretización[editar]
La discretización busca
transformar modelos y ecuaciones continuos en sus contrapartes discretas,3 usualmente
para hacer cálculos más fácilmente utilizando aproximaciones. El análisis
numérico es un importante ejemplo.
