PROFILBARU.COM

A matemática discreta é unha área das matemáticas encargadas do estudo dos conxuntos discretos: finitos ou infinitos numerables.

En oposición ás matemáticas continuas, que se encargan do estudo de conceptos como a continuidade e o cambio continuo, as matemáticas discretas estudan estruturas cuxos elementos poden contarse un por un separadamente. É dicir, os procesos en matemáticas discretas son contables, por exemplo, os números enteiros, grafos e sentenzas de lóxica.^[1]

Mentres que o cálculo infinitesimal está fundado nos números reais que non son numerables, a matemática discreta é a base de todo o relacionado cos números naturais ou conxuntos numerables.

Son fundamentais para a ciencia da computación, porque só son computables as funcións de conxuntos numerables.

A clave na matemática discreta é que non é posible manexar as ideas de proximidade ou límite e suavidade nas curvas, como se pode no cálculo. Por exemplo, en matemática discreta unha incógnita pode ser 2 ou 3, pero nunca se aproximará a 3 pola esquerda con 2.9, 2.99, 2.999 etc. As gráficas en matemáticas discretas veñen dadas por un conxunto finito de puntos que se poden contar por separado; é dicir, as súas variables son discretas ou dixitais, mentres que as gráficas en cálculo son trazos continuos de rectas ou curvas; é dicir, as súas variables son continuas ou analóxicas.

Historia

A matemática discreta viron un gran número de problemas difíciles de resolver. En teoría dos grafos, moita da investigación realizada nos seus inicios foi motivada por intentos para probar o teorema das catro cores, o cal foi probado máis de cen anos despois da súa descrición inicial. O problema das pontes de Königsberg, un problema clásico do prolífico Leonhard Euler.

En lóxica, o segundo problema da lista de problemas abertos de David Hilbert, era probar que os axiomas da aritmética son consistentes. O segundo teorema de Gödel da incompletitude probou en 1931 que isto non é posible, polo menos dentro da aritmética en si. O décimo problema de Hilbert era determinar se un polinomio diofantiano con coeficientes enteiros dado ten unha solución enteira. En 1970, Yuri Matiyasevich probou que isto é imposible de facer.

A necesidade de descifrar códigos alemáns na segunda guerra mundial deu paso a avances na criptografía e a ciencia computacional teórica, co primeiro computador electrónico, dixital e programable desenvolvido en Inglaterra. Ao mesmo tempo, requirimentos militares motivaron avances na investigación operativa. A guerra fría tivo significancia na criptografía, e mantívoa vixente, co que se realizaron avances na criptografía asimétrica.

Actualmente, un dos problemas abertos máis famosos na teoría da informática é o problema das clases de complexidade "P = NP". O Clay Mathematics Institute ofreceu un premio dun millón de dólares para a primeira demostración correcta, xunto con premios para seis problemas máis.

Tópicos na matemática discreta

Teoría da información

A teoría da información vese involucrada na cuantificación da información. Relacionada con isto está a teoría de codificación, que se emprega para deseñar métodos de transmisión e almacenamento de datos eficientes e confiables. A teoría da información tamén inclúe tópicos continuos tales como sinais análogos, codificación análoga e cifrado análogo.

Lóxica

As fórmulas lóxicas son estruturas discretas, como o son as demostracións, que forman árbores finitos, ou máis xeralmente, estruturas de grafos acíclicos (en cada paso de inferencia combinando unha ou máis ramas de premisas para dar unha soa conclusión). As táboas de verdade de fórmulas lóxicas usualmente forman un conxunto finito, xeralmente restrinxido a dous valores: verdadeiro e falso, pero a lóxica pode ter valores continuos, por exemplo na lóxica difusa. Os conceptos como árbores de demostracións ou derivacións infinitas tamén foron estudados, por exemplo na lóxica proposicional infinitaria.

Teoría de conxuntos

A teoría de conxuntos é a rama da matemática que estuda conxuntos matemáticos, os cales son coleccións de obxectos, tales como {azul, branco, vermello} ou o conxunto infinito de todos os números primos. Os conxuntos parcialmente ordenados e os conxuntos con outras relacións teñen aplicación en moitas áreas.

Na matemática discreta, os conxuntos numerables (incluíndo os conxuntos finitos) son o principal obxecto de estudo. O inicio da teoría de conxuntos xeralmente relaciónase co traballo de Georg Cantor, facendo distinción entre diferentes tipos de conxuntos infinitos, motivado polo estudo das series trigonométricas. O desenvolvemento máis profundo na teoría de conxuntos infinitos está fóra do alcance da matemática discreta. De feito, o traballo contemporáneo en teoría descritiva de conxuntos fai uso extenso do uso da matemática continua tradicional.

Combinatoria

A combinatoria é a rama da matemática que estuda coleccións finitas de obxectos que poden ser combinados ou ordenados.

A combinatoria enumerativa ocúpase, en particular, do "reconto" dos obxectos de devanditas coleccións.

Teoría dos grafos

A teoría dos grafos é o estudo de grafos e a teoría de redes. Xeralmente é considerada parte da combinatoria, pero evolucionou pola súa banda o suficiente como para ser considerada unha materia por si mesma.^[2] A teoría dos grafos ten extensas aplicacións en todas as áreas da matemática e a ciencia. Existen tamén grafos continuos.

Teoría dos números

A teoría dos números principalmente ten que ver coas propiedades dos números en xeral e, particularmente, dos enteiros. Ten aplicacións na criptografía, criptoanálise e criptoloxía, particularmente no que refire a números primos. Outros aspectos da teoría dos números inclúen a teoría xeométrica de números. Na teoría analítica de números, tamén se utilizan técnicas de matemática continua.

Álxebra

As estruturas alxébricas ocorren discreta e continuamente. Como exemplos de álxebras discretas están: a álxebra de Boole, utilizada en circuítos dixitais e programación, a álxebra relacional, utilizada en bases de datos; os grupos, finitos e discretos, así como os aneis e os campos son importantes na teoría de códigos.

Cálculo de diferenzas finitas

Unha función definida nun intervalo de enteiros chámase secuencia. Unha secuencia pode ser finita ou infinita. Tal función discreta pode ser definida explicitamente por unha lista (se o seu dominio é finito), ou por unha fórmula para o seu termo n-esimo, ou tamén pode ser dada implicitamente por unha relación de recorrencia ou ecuación de diferenza. As ecuacións de diferenza son similares ás ecuacións diferenciais pero substitúense as derivadas tomando a diferenza entre termos adxacentes e poden ser utilizadas para aproximar ecuacións diferenciais. Moitas interrogantes e métodos das ecuacións diferenciais teñen as súas contrapartes para ecuacións de diferenzas.

Xeometría

A xeometría discreta e a xeometría combinatoria tratan as propiedades combinatorias de coleccións discretas de obxectos xeométricos. Un antigo tópico na xeometría discreta é o recubrimento do plano. A xeometría computacional aplica algoritmos a problemas xeométricos.

Investigación operativa

A investigación operativa é unha rama das matemáticas consistente no uso de modelos matemáticos, estatística e algoritmos co obxecto de realizar un proceso de toma de decisións prácticas para negocios e outras áreas. Estes problemas poden ser, por exemplo, a repartición de recursos para maximizar ingresos, ou agendar actividades para minimizar riscos. Técnicas propias da investigación de operacións inclúen programación linear e outras áreas de optimización, teoría de colas, algoritmos de planificación, análise de redes. A investigación de operacións tamén inclúe tópicos continuos como procesos de Markov de tempo continuo, optimización de procesos, martingalas de tempo continuo etc.

Discretización

A discretización busca transformar modelos e ecuacións continuos nas súas contrapartes discretas, usualmente para facer cálculos máis facilmente utilizando aproximacións.^[3] A análise numérica é un importante exemplo.