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.1 2​ 3​ 4​ ​

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 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 La complejidad estudia el tiempo
de procesos se usan para modelar sistemas de cálculo, y los métodos en el cual un algoritmo se ejecuta.
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
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 Los códigos mostrados
inferencia, como también de la consistencia, solidez y completitud. Por aquí son una manera de
ejemplo, en la mayoría de los sistemas en la lógica, la ley de Peirce, representar una palabra
(((P→Q)→P)→P) es un teorema. En lógica clásica, puede ser fácilmente en teoría de la
información, como
verificado con una tabla de verdad. El estudio de las demostraciones
también para algoritmos
matemáticas es particularmente importante en lógica y tiene aplicaciones en
de proceso de
la demostración automática de teoremas y verificación formal de software. información.

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 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.5 ​ 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 La teoría de grafos se relaciona
continuas pueden ser utilizadas para aproximar discretas y viceversa. estrechamente con la Teoría de
Para situaciones en las cuales los valores posibles son altamente grupos. Este grafo de un
restringidos en su variabilidad, como por ejemplo en dados o cartas, tetraedro truncado está
relacionado con el grupo
calcular las probabilidades simplemente necesita de combinatoria
alternado A4.
enumerativa.

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, también se utilizan
técnicas de matemática continua.

Álgebra
Las estructuras algebraicas ocurren discreta y continuamente. Como La espiral de Ulam muestra
ejemplos de álgebras discretas están: el álgebra booleana, utilizada en aquí, en cada pixel negro, un
circuitos digitales y programación, álgebra relacional, utilizada en número primo. Este diagrama
bases de datos; grupos, finitos y discretos, así como anillos y campos muestra una posible pista sobre
la distribución de los números
son importantes en la teoría de códigos.
primos.

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 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.
La geometría
computacional aplica
Investigación Operativa algoritmos a
representaciones de
La investigación operativa es una rama de las matemáticas consistente en el objetos geométricos.
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
Diagramas PERT como
procesos de Markov de tiempo continuo, optimización de procesos,
este, proveen técnicas
martingalas de tiempo continuo, etc. de administración de
negocios basados en
teoría de grafos.
Teoría de juegos, teoría de la decisión, teoría de utilidad
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. Matriz de ganancias del dilema del
prisionero, un ejemplo común de juego.
La teoría de juegos trata con las situaciones donde el éxito Un jugador elige una fila y el otro una
depende de las decisiones de otros, lo cual hace elegir el columna; el par resultante dicta sus
ganancias.
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,6
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

Referencias
1. Weisstein, Eric W. «Matemática discreta» (http://mathworld.wolfram.com/DiscreteMathemati
cs.html). En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
2. Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
3. Franklin, James (2017). «Discrete and continuous: a fundamental dichotomy in
mathematics» (https://scholarship.claremont.edu/jhm/vol7/iss2/18/). Journal of Humanistic
Mathematics 7 (2): 355-378. S2CID 6945363 (https://api.semanticscholar.org/CorpusID:6945363).
doi:10.5642/jhummath.201702.18 (https://dx.doi.org/10.5642%2Fjhummath.201702.18). Consultado el 30
de junio de 2021.
4. «Discrete Structures: What is Discrete Math?» (https://cse.buffalo.edu/~rapaport/191/S09/w
hatisdiscmath.html). cse.buffalo.edu. Consultado el 16 de noviembre de 2018.
5. Graphs on Surfaces (http://jhupbooks.press.jhu.edu/ecom/MasterServlet/GetItemDetailsHan
dler?iN=9780801866890&qty=1&viewMode=1&loggedIN=false&JavaScript=y), Bojan Mohar
and Carsten Thomassen, Johns Hopkins University press, 2001
6. http://ccc.inaoep.mx/~emorales/Cursos/KDD/node155.html Archivado (https://web.archive.or
g/web/20100430205320/http://ccc.inaoep.mx/~emorales/Cursos/KDD/node155.html) el 30
de abril de 2010 en Wayback Machine. Discretización de Valores

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 (https://
archive.org/details/concretemathemat0000grah) (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 (https://archive.org/deta
ils/isbn_9780130458032). Prentice Hall. ISBN 978-0-13-045803-2.
Rosen, Kenneth H.; Michaels, John G. (2000). Hand Book of Discrete and Combinatorial
Mathematics (https://archive.org/details/isbn_9780849301490). 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 (https://archive.org/details/discr
etemathemat0000simp). McGraw-Hill. ISBN 978-0-07-709840-7.

Enlaces externos
matemáticas discretas (http://archives.math.utk.edu/topics/discreteMath.html) Archivado (htt
ps://web.archive.org/web/20110829184228/http://archives.math.utk.edu/topics/discreteMat
h.html) el 29 de agosto de 2011 en Wayback Machine. (en inglés)

Obtenido de «https://es.wikipedia.org/w/index.php?title=Matemática_discreta&oldid=167382880»