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.

Contenido

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

Artículo principal: Ciencia computacional 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

Artículo principal: 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

Artículo principal: Lógica matematica

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

Artículo principal: 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

Artículo principal: 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

Artículo principal: 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.
Artículo principal: Teoría de números

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

Artículo principal: Álgebra abstracta

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

Artículo principal: Diferencia finita

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 computacional aplica algoritmos a representaciones de objetos geométricos.
Artículo principal: Geometría discreta

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

Artículo principal: 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

Artículo principal: 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

Referencias

  1. Definición, Wolfram
  2. Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, John Hopkins University press, 2001
  3. http://ccc.inaoep.mx/~emorales/Cursos/KDD/node155.html Discretización de Valores

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Matemática discreta — Saltar a navegación, búsqueda Matemática discreta es la parte 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 encarga del estudio de conceptos como… …   Wikipedia Español

  • Algoritmo de Euclides — El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además… …   Wikipedia Español

  • Historia de la matemática — Página del Compendio de cálculo por el método de completado y balanceado de Muhammad ibn Mūsā al Khwārizmī (820 d.C.) La historia de las matemáticas es el área de estudio que abarca las investigaciones sobre los orígenes de los descubrimi …   Wikipedia Español

  • Programas de álgebra computacional — Anexo:Programas de álgebra computacional Saltar a navegación, búsqueda La siguiente es una lista de sistemas algebraicos de cómputo o sistemas de álgebra computacional, (CAS, del inglés computer algebra system), dentro de ellos se encuentran… …   Wikipedia Español

  • Anexo:Programas de álgebra computacional — La siguiente es una lista de sistemas algebraicos de cómputo o sistemas de álgebra computacional, (CAS, del inglés computer algebra system), dentro de ellos se encuentran programas propietarios y de código abierto (software libre): Contenido 1… …   Wikipedia Español

  • Matemática aplicada — Saltar a navegación, búsqueda El término matemáticas aplicadas se refiere a todos aquellos métodos y herramientas matemáticas que pueden ser utilizados en el análisis o solución de problemas pertenecientes al área de las ciencias aplicadas o… …   Wikipedia Español

  • Sucesión de Fibonacci — Gráfica de la sucesión de Fibonacci hasta f10 En matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales: La sucesión inicia con …   Wikipedia Español

  • Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… …   Wikipedia Español

  • Número real — Diferentes clases de números reales. Recta real …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.