Matemáticas discretas

	Este artículo tiene referencias, pero necesita más para complementar su verificabilidad. Puedes colaborar agregando referencias a fuentes fiables como se indica aquí. El material sin fuentes fiables podría ser cuestionado y eliminado. Uso de esta plantilla: `{{Referencias adicionales\|t={{sust:CURRENTTIMESTAMP}}}}`

Las matemáticas discretas^[1] 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, grafos y sentencias de lógica.

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^[2] 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

null ocultar

Historia[editar código · 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ö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 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, 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 código · editar]

Informática teórica[editar código · editar]

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 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 código · editar]

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[editar código · editar]

Artículo principal: Lógica matemática

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 código · editar]

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^[3] 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 código · editar]

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 explícitas 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[editar código · editar]

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 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 si 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[editar código · editar]

Artículo principal: Distribuciones de variable discreta

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 código · editar]

Artículo principal: 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[editar código · editar]

Artículo principal: Álgebra abstracta

Las estructuras algebraicas ocurren discreta y continuamente. Como ejemplos de álgebras discretas están: el álgebra booleana^[4], 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 código · editar]

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[editar código · editar]

Artículo principal: 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[editar código · editar]

Artículo principal: 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 de operaciones[editar código · editar]

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[editar código · 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.

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

Discretización[editar código · editar]

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[editar código · editar]

á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

Referencias[editar código · editar]

Volver arriba↑ Weisstein, Eric W. «Matemáticas discretas». En Weisstein, Eric W. MathWorld (en inglés). Wolfram Research.
Volver arriba↑ Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001
Volver arriba↑ http://ccc.inaoep.mx/~emorales/Cursos/KDD/node155.html Discretización de Valores

Enlaces externos[editar código · editar]

matemáticas discretas (en inglés)

Categorías:

Menú de navegación

Leer
Editar código
Editar
Ver historial
Vigilar

Imprimir/exportar

Crear un libro
Descargar como PDF
Versión para imprimir

En otros proyectos

Wikimedia Commons

Herramientas

Lo que enlaza aquí
Cambios en enlazadas
Subir archivo
Páginas especiales
Enlace permanente
Información de la página
Elemento de Wikidata
Citar esta página

En otros idiomas

Editar enlaces

Se editó esta página por última vez el 1 abr 2017 a las 02:19.
El texto está disponible bajo la Licencia Creative Commons Atribución Compartir Igual 3.0; pueden aplicarse cláusulas adicionales. Al usar este sitio, usted acepta nuestros términos de uso y nuestra política de privacidad. Wikipedia® es una marca registrada de la Fundación Wikimedia, Inc., una organización sin ánimo de lucro.

↑ Malva Alberto, Ingrid Schwer, Yanina Fumero, Pamela Llop, María Chara (2009). Matemática Discreta. Editorial de la Universidad Tecnológica Nacional – edUTecNe. Consultado el 22 de mayo de 2017.
↑ «Números Naturales y Números Enteros». Universidad Tecnológica Nacional.
↑ UTN, Facultad Regional Buenos Aires. «Conjuntos Ordenados». Biblioteca Virtual.
↑ UTN, Facultad Regional Buenos Aires. «Álgebras Booleanas». Biblioteca Virtual.

[1] Malva Alberto, Ingrid Schwer, Yanina Fumero, Pamela Llop, María Chara (2009). Matemática Discreta. Editorial de la Universidad Tecnológica Nacional – edUTecNe. Consultado el 22 de mayo de 2017.

[2] «Números Naturales y Números Enteros». Universidad Tecnológica Nacional.

[3] UTN, Facultad Regional Buenos Aires. «Conjuntos Ordenados». Biblioteca Virtual.

[4] UTN, Facultad Regional Buenos Aires. «Álgebras Booleanas». Biblioteca Virtual.

[1]

[2]

[3]

[4]