Hispanopedia Wiki
Articulo de referencia

matemáticas discretas

Los gráficos como estos se encuentran entre los objetos estudiados por las matemáticas discretas, por sus interesantes propiedades matemáticas , su utilidad como modelos de prob...

Hispanopedia WikiContenido en espanolLectura gratuita
Los gráficos como estos se encuentran entre los objetos estudiados por las matemáticas discretas, por sus interesantes propiedades matemáticas , su utilidad como modelos de problemas del mundo real y su importancia en el desarrollo de algoritmos informáticos .

Las matemáticas discretas son el estudio de estructuras matemáticas que pueden considerarse "discretas" (de forma análoga a las variables discretas , que tienen una correspondencia biyectiva con los números naturales ), en lugar de "continuas" (de forma análoga a las funciones continuas ). Los objetos estudiados en matemáticas discretas incluyen números enteros , grafos y enunciados lógicos . [ 1 ] [ 2 ] [ 3 ] Por el contrario, las matemáticas discretas excluyen temas de las "matemáticas continuas" , como los números reales , el cálculo o la geometría euclidiana . Los objetos discretos a menudo pueden enumerarse mediante números enteros ; más formalmente, las matemáticas discretas se han caracterizado como la rama de las matemáticas que se ocupa de conjuntos numerables [ 4 ] (conjuntos finitos o conjuntos con la misma cardinalidad que los números naturales). Sin embargo, no existe una definición exacta del término "matemáticas discretas". [ 5 ]

El conjunto de objetos estudiados en matemáticas discretas puede ser finito o infinito. El término matemáticas finitas se aplica a veces a partes del campo de las matemáticas discretas que tratan con conjuntos finitos, en particular aquellas áreas relevantes para los negocios.

La investigación en matemáticas discretas aumentó en la segunda mitad del siglo XX, en parte debido al desarrollo de las computadoras digitales , que operan en pasos discretos y almacenan datos en bits discretos. Los conceptos y la notación de las matemáticas discretas son útiles para estudiar y describir objetos y problemas en diversas ramas de la informática , como algoritmos , lenguajes de programación , criptografía , demostración automática de teoremas y desarrollo de software . A su vez, las implementaciones informáticas son fundamentales para aplicar ideas de las matemáticas discretas a problemas del mundo real.

Si bien los principales objetos de estudio en matemáticas discretas son objetos discretos, también se suelen emplear métodos analíticos de las matemáticas "continuas".

En los planes de estudio universitarios, las matemáticas discretas aparecieron en la década de 1980, inicialmente como un curso de apoyo a la informática; su contenido era algo desordenado en aquel entonces. Posteriormente, el plan de estudios se ha desarrollado en conjunto con los esfuerzos de la ACM y la MAA hasta convertirse en un curso que básicamente busca desarrollar la madurez matemática en los estudiantes de primer año; por lo tanto, hoy en día también es un requisito previo para los estudiantes de matemáticas en algunas universidades. [ 6 ] [ 7 ] También han aparecido algunos libros de texto de matemáticas discretas para el nivel de bachillerato. [ 8 ] En este nivel, las matemáticas discretas a veces se consideran un curso preparatorio, como el precálculo en este sentido. [ 9 ]

El Premio Fulkerson se otorga a los trabajos más destacados en matemáticas discretas.

Temas

informática teórica

La complejidad estudia el tiempo que tardan los algoritmos , como esta rutina de ordenación .
La geometría computacional aplica algoritmos informáticos a las representaciones de objetos geométricos .

La informática teórica abarca áreas de las matemáticas discretas relevantes para la computación. Se basa en gran medida en la teoría de grafos y la lógica matemática . Dentro de la informática teórica se incluye el estudio de algoritmos y estructuras de datos. La computabilidad estudia lo que se puede computar en principio y está estrechamente relacionada con la lógica, mientras que la complejidad estudia el tiempo, el espacio y otros recursos que consumen los cálculos. La teoría de autómatas y la teoría de lenguajes formales están estrechamente relacionadas con la computabilidad. Las redes de Petri y las álgebras de procesos se utilizan para modelar sistemas informáticos, y los métodos de las matemáticas discretas se utilizan para analizar circuitos electrónicos VLSI . La geometría computacional aplica algoritmos a problemas geométricos y representaciones de objetos geométricos , mientras que el análisis de imágenes por computadora los aplica a representaciones de imágenes. La informática teórica también incluye el estudio de diversos temas de computación continua.

teoría de la información

Los códigos ASCII de la palabra "Wikipedia", que se muestran aquí en binario , proporcionan una forma de representar la palabra en la teoría de la información , así como para los algoritmos de procesamiento de información .

La teoría de la información se centra en la cuantificación de la información . Está estrechamente relacionada con la teoría de la codificación , que se utiliza para diseñar métodos eficientes y fiables de transmisión y almacenamiento de datos. La teoría de la información también abarca temas como las señales analógicas , la codificación analógica y el cifrado analógico .

Lógica

La lógica estudia los principios del razonamiento y la inferencia válidos , así como la consistencia , la solidez y la completitud . Por ejemplo, en la mayoría de los sistemas lógicos (pero no en la lógica intuicionista ), la ley de Peirce ((( P → Q )→ P )→ P ) es un teorema. En la lógica clásica, se puede verificar fácilmente con una tabla de verdad . El estudio de la demostración matemática es particularmente importante en lógica y ha dado lugar a la demostración automatizada de teoremas y la verificación formal de software.

Las fórmulas lógicas son estructuras discretas, al igual que las demostraciones , que forman árboles finitos [ 10 ] o, más generalmente, estructuras de grafos acíclicos dirigidos [ 11 ] [ 12 ] (donde cada paso de inferencia combina una o más ramas de premisas para dar una única conclusión). Los valores de verdad de las fórmulas lógicas suelen formar un conjunto finito, generalmente restringido a dos valores: verdadero y falso , pero la lógica también puede ser de valor continuo, por ejemplo, la lógica difusa . También se han estudiado conceptos como árboles de demostración infinitos o árboles de derivación infinitos, [ 13 ] por ejemplo, la lógica infinitaria .

teoría de conjuntos

La teoría de conjuntos es la rama de las matemáticas que estudia los conjuntos , que son colecciones de objetos, como {azul, blanco, rojo} o el conjunto (infinito) de todos los números primos . Los conjuntos parcialmente ordenados y los conjuntos con otras relaciones tienen aplicaciones en diversas áreas.

En matemáticas discretas, los conjuntos numerables (incluidos los conjuntos finitos ) son el foco principal. El inicio de la teoría de conjuntos como rama de las matemáticas suele estar marcado por el trabajo de Georg Cantor , quien distinguió entre diferentes tipos de conjuntos infinitos , motivado por el estudio de las series trigonométricas. El desarrollo posterior de la teoría de conjuntos infinitos queda fuera del ámbito de las matemáticas discretas. De hecho, los trabajos contemporáneos en teoría descriptiva de conjuntos hacen un uso extensivo de las matemáticas continuas tradicionales.

Combinatoria

La combinatoria estudia las formas en que las estructuras discretas pueden combinarse o disponerse. La combinatoria enumerativa se concentra en contar el número de ciertos objetos combinatorios; por ejemplo, la vía dodecafónica proporciona un marco unificado para contar permutaciones , combinaciones y particiones . La combinatoria analítica se ocupa de la enumeración (es decir, determinar el número) de estructuras combinatorias utilizando herramientas del análisis complejo y la teoría de la probabilidad . A diferencia de la combinatoria enumerativa, que utiliza fórmulas combinatorias explícitas y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo obtener fórmulas asintóticas . La combinatoria topológica se ocupa del uso de técnicas de la topología y la topología algebraica / topología combinatoria en combinatoria . La teoría del diseño es un estudio de diseños combinatorios , que son colecciones de subconjuntos con ciertas propiedades de intersección . La teoría de particiones estudia varios problemas de enumeración y asintóticos relacionados con particiones enteras , y está estrechamente relacionada con las q-series , las funciones especiales y los polinomios ortogonales . Originalmente parte de la teoría de números y el análisis , la teoría de particiones ahora se considera parte de la combinatoria o un campo independiente. La teoría del orden es el estudio de conjuntos parcialmente ordenados , tanto finitos como infinitos.

teoría de grafos

La teoría de grafos tiene estrechos vínculos con la teoría de grupos . Este grafo tetraédrico truncado está relacionado con el grupo alternante A 4 .

La teoría de grafos, el estudio de grafos y redes , a menudo se considera parte de la combinatoria, pero ha crecido lo suficiente y se ha diferenciado lo suficiente, con su propio tipo de problemas, como para ser considerada una disciplina independiente. [ 14 ] Los grafos son uno de los principales objetos de estudio en matemáticas discretas. Se encuentran entre los modelos más comunes de estructuras tanto naturales como artificiales. Pueden modelar muchos tipos de relaciones y dinámicas de procesos en sistemas físicos, biológicos y sociales. En informática, pueden representar redes de comunicación, organización de datos, dispositivos computacionales, el flujo de computación, etc. En matemáticas, son útiles en geometría y ciertas partes de la topología , por ejemplo, la teoría de nudos . La teoría algebraica de grafos tiene estrechos vínculos con la teoría de grupos y la teoría topológica de grafos tiene estrechos vínculos con la topología . También existen grafos continuos ; sin embargo, en su mayor parte, la investigación en teoría de grafos se enmarca dentro del ámbito de las matemáticas discretas.

teoría de números

La espiral de números de Ulam, donde los píxeles negros representan los números primos . Este diagrama sugiere patrones en la distribución de los números primos.

La teoría de números se ocupa de las propiedades de los números en general, en particular de los enteros . Tiene aplicaciones en criptografía y criptoanálisis , especialmente en lo que respecta a la aritmética modular , las ecuaciones diofánticas , las congruencias lineales y cuadráticas, los números primos y las pruebas de primalidad . Otros aspectos discretos de la teoría de números incluyen la geometría de los números . En la teoría analítica de números , también se utilizan técnicas de las matemáticas continuas. Temas que van más allá de los objetos discretos incluyen los números trascendentales , la aproximación diofántica , el análisis p-ádico y los cuerpos de funciones .

Estructuras algebraicas

Las estructuras algebraicas se presentan tanto como ejemplos discretos como continuos. Las álgebras discretas incluyen: el álgebra booleana, utilizada en puertas lógicas y programación; el álgebra relacional, utilizada en bases de datos ; las versiones discretas y finitas de grupos , anillos y cuerpos son importantes en la teoría de la codificación algebraica ; los semigrupos y monoides discretos aparecen en la teoría de los lenguajes formales .

Análogos discretos de las matemáticas continuas

En matemáticas continuas existen muchos conceptos y teorías que tienen versiones discretas, como el cálculo discreto , las transformadas de Fourier discretas , la geometría discreta , los logaritmos discretos , la geometría diferencial discreta , el cálculo exterior discreto , la teoría de Morse discreta , la optimización discreta , la teoría de la probabilidad discreta , la distribución de probabilidad discreta , las ecuaciones en diferencias , los sistemas dinámicos discretos y las medidas vectoriales discretas  .

Cálculo de diferencias finitas, análisis discreto y cálculo discreto.

En cálculo discreto y cálculo de diferencias finitas , una función definida en un intervalo de los enteros se denomina generalmente secuencia . Una secuencia puede ser una secuencia finita de una fuente de datos o una secuencia infinita de un sistema dinámico discreto . Dicha función discreta puede definirse explícitamente mediante una lista (si su dominio es finito), o mediante una fórmula para su término general, o puede darse implícitamente mediante una relación de recurrencia o una ecuación de diferencias . Las ecuaciones de diferencias son similares a las ecuaciones diferenciales , pero sustituyen la diferenciación por la diferencia entre términos adyacentes; pueden utilizarse para aproximar ecuaciones diferenciales o (más frecuentemente) estudiarse por sí mismas. Muchas cuestiones y métodos relacionados con las ecuaciones diferenciales tienen contrapartes para las ecuaciones de diferencias. Por ejemplo, donde existen transformadas integrales en el análisis armónico para estudiar funciones continuas o señales analógicas, existen transformadas discretas para funciones discretas o señales digitales. Además de los espacios métricos discretos , existen espacios topológicos discretos más generales , espacios métricos finitos , espacios topológicos finitos .

El cálculo de escalas temporales unifica la teoría de ecuaciones en diferencias con la de ecuaciones diferenciales , y tiene aplicaciones en campos que requieren el modelado simultáneo de datos discretos y continuos. Otra forma de modelar esta situación es mediante el concepto de sistemas dinámicos híbridos .

Geometría discreta

La geometría discreta y la geometría combinatoria tratan sobre las propiedades combinatorias de colecciones discretas de objetos geométricos. Un tema recurrente en la geometría discreta es el teselado del plano .

En geometría algebraica , el concepto de curva puede extenderse a geometrías discretas tomando los espectros de anillos de polinomios sobre cuerpos finitos como modelos de los espacios afines sobre ese cuerpo, y dejando que subvariedades o espectros de otros anillos proporcionen las curvas que se encuentran en ese espacio. Aunque el espacio en el que aparecen las curvas tiene un número finito de puntos, las curvas no son tanto conjuntos de puntos como análogos de curvas en entornos continuos. Por ejemplo, cada punto de la formaV(incógnita−do)⊂Especulación⁡K[incógnita]=A1{\displaystyle V(xc)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}paraK{\displaystyle K}un campo puede estudiarse comoEspeculación⁡K[incógnita]/(incógnita−do)≅Especulación⁡K{\displaystyle \operatorname {Spec} K[x]/(xc)\cong \operatorname {Spec} K}, un punto, o como el espectroEspeculación⁡K[incógnita](incógnita−do){\displaystyle \operatorname {Spec} K[x]_{(xc)}}del anillo local en (xc) , un punto junto con un entorno a su alrededor. Las variedades algebraicas también tienen una noción bien definida de espacio tangente llamado espacio tangente de Zariski , lo que hace que muchas características del cálculo sean aplicables incluso en entornos finitos.

Modelado discreto

En matemáticas aplicadas , el modelado discreto es el análogo discreto del modelado continuo . En el modelado discreto, se ajustan fórmulas discretas a los datos . Un método común en este tipo de modelado es el uso de relaciones de recurrencia . La discretización se refiere al proceso de transformar modelos y ecuaciones continuos en sus equivalentes discretos, a menudo con el fin de simplificar los cálculos mediante aproximaciones. El análisis numérico constituye un ejemplo importante.

Desafíos

Gran parte de la investigación en teoría de grafos se motivó por intentos de demostrar que todos los mapas, como este, pueden colorearse usando solo cuatro colores de manera que ninguna área del mismo color comparta una arista. Kenneth Appel y Wolfgang Haken lo demostraron en 1976. [ 15 ]

La historia de las matemáticas discretas ha involucrado una serie de problemas desafiantes que han centrado la atención en áreas específicas del campo. En la teoría de grafos, gran parte de la investigación estuvo motivada por los intentos de demostrar el teorema de los cuatro colores , enunciado por primera vez en 1852, pero no demostrado hasta 1976 (por Kenneth Appel y Wolfgang Haken, con una considerable ayuda informática). [ 15 ]

En lógica , el segundo problema de la lista de problemas abiertos de David Hilbert , presentada en 1900, consistía en demostrar la consistencia de los axiomas de la aritmética . El segundo teorema de incompletitud de Gödel , demostrado en 1931, mostró que esto no era posible, al menos no dentro de la aritmética misma. El décimo problema de Hilbert consistía en determinar si una ecuación diofántica polinómica dada con coeficientes enteros tiene una solución entera. En 1970, Yuri Matiyasevich demostró que esto no era posible .

La necesidad de descifrar los códigos alemanes en la Segunda Guerra Mundial impulsó avances en criptografía y ciencias de la computación teórica , con el desarrollo del primer ordenador electrónico digital programable en Bletchley Park, Inglaterra , bajo la dirección de Alan Turing y su obra fundamental, Sobre los números computables . [ 16 ] La Guerra Fría hizo que la criptografía siguiera siendo importante, desarrollándose avances fundamentales como la criptografía de clave pública en las décadas siguientes. La industria de las telecomunicaciones también ha motivado avances en matemáticas discretas, particularmente en teoría de grafos y teoría de la información . La verificación formal de enunciados en lógica ha sido necesaria para el desarrollo de software de sistemas críticos para la seguridad , y los avances en la demostración automatizada de teoremas han sido impulsados ​​por esta necesidad.

La geometría computacional ha sido una parte importante de los gráficos por computadora incorporados en los videojuegos modernos y las herramientas de diseño asistido por computadora .

Varios campos de las matemáticas discretas, en particular la informática teórica, la teoría de grafos y la combinatoria , son importantes para abordar los desafiantes problemas bioinformáticos asociados con la comprensión del árbol de la vida . [ 17 ]

Actualmente, uno de los problemas abiertos más famosos en la informática teórica es el problema P = NP , que involucra la relación entre las clases de complejidad P y NP . El Instituto Clay de Matemáticas ha ofrecido un premio de 1 millón de dólares estadounidenses por la primera demostración correcta, junto con premios para otros seis problemas matemáticos . [ 18 ]

Véase también

Referencias

  1. ↑ Richard Johnsonbaugh , Matemáticas Discretas , Prentice Hall, 2008.
  2. ↑ Franklin, James (2017). "Discreto y continuo: una dicotomía fundamental en matemáticas" (PDF) . Journal of Humanistic Mathematics . 7 (2): 355– 378. doi : 10.5642/jhummath.201702.18 . S2CID 6945363. Recuperado el 30 de junio de 2021 . 
  3. ↑ "Estructuras discretas: ¿Qué son las matemáticas discretas?" . cse.buffalo.edu . Consultado el 16 de noviembre de 2018 .
  4. ↑ Biggs, Norman L. (2002), Matemáticas discretas , Oxford Science Publications (2.ª ed.), The Clarendon Press Oxford University Press, p. 89, ISBN   9780198507178, MR 1078626 , Las matemáticas discretas son la rama de las matemáticas en la que tratamos cuestiones que involucran conjuntos finitos o infinitos numerables. 
  5. ↑ Hopkins, Brian, ed. (2009). Recursos para la enseñanza de las matemáticas discretas: proyectos para el aula, módulos de historia y artículos . Asociación Matemática de América. ISBN 978-0-88385-184-5.
  6. ↑ Levasseur, Ken; Doerr, Al. Estructuras discretas aplicadas . pág. 8. 
  7. ↑ Geoffrey Howson, Albert, ed. (1988). Las matemáticas como materia de servicio . Cambridge University Press. págs. 77–78 . ISBN  978-0-521-35395-3.
  8. ↑ Rosenstein, Joseph G. Matemáticas discretas en las escuelas . Sociedad Matemática Americana. pág. 323. ISBN  978-0-8218-8578-9.
  9. ↑ "UCSMP" . uchicago.edu .
  10. ↑ Troelstra, AS; Schwichtenberg, H. (27 de julio de 2000). Teoría básica de la demostración . Cambridge University Press. pág. 186. ISBN  978-0-521-77911-1.
  11. ↑ Buss, Samuel R. (1998). Manual de teoría de la demostración . Elsevier. pág. 13. ISBN  978-0-444-89840-1.
  12. ↑ Baader, Franz; Brewka, Gerhard; Eiter, Thomas (16 de octubre de 2001). KI 2001: Avances en Inteligencia Artificial: Conferencia Conjunta Germano-Austríaca sobre IA, Viena, Austria, 19-21 de septiembre de 2001. Actas . Springer. pág. 325. ISBN  978-3-540-42612-7.
  13. ↑ Brotherston, J.; Bornat, R.; Calcagno, C. (enero de 2008). "Pruebas cíclicas de terminación de programas en lógica de separación". ACM SIGPLAN Notices . 43 (1): 101– 112. doi : 10.1145/1328897.1328453 .
  14. ↑ Mohar, Bojan ; Thomassen, Carsten (2001). Graphs on Surfaces . Johns Hopkins University Press. ISBN 978-0-8018-6689-0OCLC 45102952​​ 
  15. 1 2 Wilson, Robin (2002). Cuatro colores bastan . Londres: Penguin Books. ISBN 978-0-691-11533-7.
  16. ↑ Hodges, Andrew (1992). Alan Turing: El enigma . Random House .
  17. ↑ Hodkinson, Trevor R.; Parnell, John AN (2007). Reconstrucción del árbol de la vida: taxonomía y sistemática de taxones grandes y ricos en especies . CRC Press. pág. 97. ISBN  978-0-8493-9579-6.
  18. ↑ "Problemas del Premio del Milenio" . 24 de mayo de 2000. Consultado el 12 de enero de 2008 .

Lecturas adicionales

  • Biggs, Norman L. (2002). Matemáticas Discretas . Oxford University Press. ISBN 978-0-19-850717-8.
  • Dwyer, John (2010). Introducción a las matemáticas discretas para los negocios y la informática . Algana Pub. ISBN 978-1-907934-00-1.
  • Epp, Susanna S. (4 de agosto de 2010). Matemáticas discretas con aplicaciones . Thomson Brooks/Cole. ISBN 978-0-495-39132-6.
  • Graham, Ronald ; Knuth, Donald E .; Patashnik, Oren (1994). Matemáticas concretas (2ª  ed.). Addison-Wesley. ISBN 0-201-55802-5.
  • Grimaldi, Ralph P. (2004). Matemáticas discretas y combinatorias: una introducción aplicada . Addison Wesley. ISBN 978-0-201-72634-3.
  • Knuth, Donald E. (2011). El arte de la programación informática . Vol.  1–4a. Edición en caja. Addison-Wesley. ISBN 978-0-321-75104-1.
  • Matoušek, Jiří ; Nešetřil, Jaroslav (1998). Matemáticas Discretas . Prensa de la Universidad de Oxford. ISBN 978-0-19-850208-1.
  • Obrenic, Bojana (2003). Problemas prácticos de matemáticas discretas . Prentice Hall. ISBN 978-0-13-045803-2.
  • Rosen, Kenneth H.; Michaels, John G. (2000). Manual de matemáticas discretas y combinatorias . CRC Press. ISBN 978-0-8493-0149-0.
  • Rosen, Kenneth H. (2007). Matemáticas discretas: y sus aplicaciones . McGraw-Hill. ISBN 978-0-07-288008-3.
  • Simpson, Andrew (2002). Matemáticas discretas mediante ejemplos . McGraw-Hill. ISBN 978-0-07-709840-7.
  • Matemáticas discretas. Archivado el 29/08/2011 en Wayback Machine , en los Archivos de Matemáticas de utk.edu, que proporciona enlaces a programas de estudio, tutoriales, programas, etc.
  • Iowa Central: Programa de Tecnologías Eléctricas. Matemáticas discretas para ingeniería eléctrica .