¿Qué es la matemática discreta y por qué es tan importante para la informática?

Las matemáticas discretas, al menos tal como las aprendí, son una colección de técnicas y algoritmos relevantes para todo tipo de cosas que a menudo debe hacer al programar:

  • Trabajar con gráficos, es decir, colecciones de nodos y aristas. ¿Cómo encuentras la forma más rápida de cruzar la ciudad? ¿Cómo puede conducir por un vecindario para entregar papeles, asegurándose de conducir en cada carretera exactamente una vez? ¿Cuánta agua puede entregar una tubería complicada a todas las casas conectadas a ella? ¿Cuál es el cuello de botella para que Fed-ex entregue paquetes en todo el mundo? Todo esto se puede resolver con la teoría de grafos.
  • Teoría de la complejidad: dadas tres formas de resolver un problema, ¿cuál funcionará más rápido? Esto es más difícil de entender de lo que parece.
  • Problemas en los que necesita clasificar objetos y verificar su membresía: ¿es un tipo de pato? ¿un perro? ¿Cuántas criaturas hay en cada categoría? La teoría de conjuntos le brinda una forma de trabajar con este tipo de preguntas.

Hay mucho más, pero estos son algunos de los aspectos más destacados.

He tomado muchos cursos de informática durante el año. El más útil fue, sin lugar a dudas, las matemáticas discretas. Es el único curso con contenido poco intuitivo que era directamente aplicable al trabajo en la industria.

Bueno, eso y tal vez la introducción a los algoritmos, y la introducción a la programación.

La matemática discreta es muy simple en realidad. Simplemente significa que solo estamos hablando de números enteros, o más exactamente, cosas que se pueden contar.

Entonces 0, 1, 2 y 3 son parte de matemáticas discretas. Lo mismo ocurre con -1, -2, -3 y así sucesivamente. ¿Qué tal 1.3, 36.9, -9.99 o 3.14? Bueno, no existen cuando se habla de matemáticas discretas. Simplemente son ignorados. Esto realmente hace que las matemáticas sean mucho más fáciles.

Ejemplo
Digamos que desea sumar todo lo que existe entre 0 y 5.

En matemáticas continuas (lo opuesto a discreto), el cálculo sería así:

[matemáticas] \ displaystyle \ int_0 ^ 5 x \, dx = \ left [\ frac {1} {2} * x ^ 2 \ right] _0 ^ 5 = \ frac {5 ^ 2} {2} -0 = 12.5 [/matemáticas]

En matemáticas discretas, el cálculo equivalente sería así:

[matemáticas] \ displaystyle \ sum_ {i = 0} ^ {4} x_i = 0 + 1 + 2 + 3 + 4 = 10 [/ matemáticas]

Como puede ver, este último es mucho más simple. Simplemente sumas todos los números.

Gráficamente, equivaldría a esto, donde la suma continua es el área debajo de la línea roja, mientras que la suma discreta es el área debajo de la línea azul.

Otra función continua (onda sinusoidal) puede verse así:

… mientras que una función discreta (onda cuadrada) podría verse así:

Puedo decirte que las matemáticas detrás de la última es mucho más simple.

¿Por qué es importante para la informática?
En el mundo de las computadoras, toda la información se almacena en bits, unidades de información que pueden tomar el valor de 0 o 1. No es como en la naturaleza, donde algo puede tomar todos los valores entre 0 y 1 también. En cambio, todo es binario.

Dado que los bits son los componentes básicos de todo lo que sucede en el software de la computadora, todo se vuelve discreto. Por ejemplo, el disco duro de la computadora portátil que estoy usando ahora puede almacenar 1 845 074 329 600 bits de información. No 1 845 074 329 599.99, sino exactamente ese número. No puedes tener medio poquito.

El estudio de algoritmos también está firmemente en el mundo discreto. Un algoritmo es una lista paso a paso de instrucciones para la computadora y es lo que hace posible los programas de computadora. Al determinar cuánto tiempo necesita ejecutar un algoritmo, cuenta el número de operaciones que necesita realizar. Observe el recuento de palabras. De nuevo, matemáticas discretas.

Las matemáticas discretas son la base de la informática. No le creas a nadie que te diga lo contrario.

Respuesta simple: la computadora es una máquina matemática discreta.

Este es el resultado de usar binario para representar todos los números. Los enteros son solo un paso al siguiente. Los números de coma flotante usan los mismos números binarios (como los utilizados por las representaciones enteras), pero con un giro: un pequeño número binario es un exponente, y otro número binario representa una fracción entre 0..1. Dado que los números de coma flotante se representan en forma de registro, la fracción no es secuencial, excepto cuando el exponente es 0. Cada paso después de eso omite valores … otra representación discreta encima de una representación discreta.

A continuación, cualquier algoritmo implementado en una computadora solo se puede realizar en pasos discretos: no existe una función continua.

Ahora, si tienes suerte (o mala suerte según tu propia opinión) y tienes la oportunidad de trabajar con computadoras analógicas, todas las apuestas están canceladas. Estas SON funciones continuas, y se implementan como funciones continuas. Y pueden ser un poco delicados con la computación: demasiado calor / frío y no funcionan. Caliéntalos y cambian los valores. Algunos tienen circuitos de compensación para ayudar (otra función continua) pero son difíciles de calibrar y requieren una recalibración bastante frecuente o los resultados serán “incorrectos”. El cálculo puede ir bien, pero los resultados pueden no tener sentido.

Una cosa que descubrirá es que una computadora analógica es muchas veces más rápida que una computadora digital y utiliza muchas menos partes para realizar el mismo cálculo. Lamentablemente, debe volver a cablear la computadora analógica para cada aplicación.

Como último punto … Una computadora digital es en realidad una computadora analógica cuidadosamente diseñada para simular una computadora digital … (que es en parte por qué el sobrecalentamiento / overclocking de un sistema puede causar fallas: la simulación analógica se rompe). Si miras lo suficientemente cerca incluso en el reloj (un alcance de rendimiento muy alto) verás que incluso el reloj de la computadora es una señal analógica …

¿Qué es la matemática discreta? Tiene algunas buenas palabras para describir lo que son las matemáticas discretas. Como dice el enlace antes mencionado, no es realmente su propia rama como, por ejemplo, álgebra o geometría. Es un conjunto (bastante adecuado) de ramas que tienen en común que tratan con objetos / estructuras discretas, en lugar de continuas.

En caso de que no lo supiera, discreto generalmente significa contable, como en manzanas (analógicamente hablando), en lugar de continuo, como en (desde una perspectiva macro) agua.

Las situaciones en las que los temas de matemáticas discretas ayudan a encontrar una solución incluyen lo siguiente:

  • ¿Cuántos números de ocho dígitos hay que contienen un cinco y un seis?
  • ¿Cuál es el número más pequeño de compuertas NAND que necesita para implementar un circuito lógico con la respuesta de salida de una tabla de verdad dada?
  • Dibuja un gráfico de cuadrícula de 5 × 5. ¿Cuántas aristas tiene el gráfico de cuadrícula n × n?

Estos son solo algunos problemas misceláneos que se encuentran entre los muchos temas bajo la carpa amplia que es la matemática discreta.

Para responder a su tercera pregunta sobre la relevancia para TI, creo que sería útil tener conocimiento sobre las tasas de crecimiento de las funciones (análisis Big- [math] O [/ math]) si estuviera diseñando un algoritmo para resolver un problema. O si estaba desarrollando una red altamente distribuida, quizás algunos temas de la teoría de gráficos lo ayudarían a descubrir la ruta más corta que un proceso en un nodo es desde un proceso en otro nodo.

¡Espero que ayude!

Los cursos de Matemática discreta comenzaron hace unas décadas cuando el uso de la computadora se hizo común. Las universidades descubrieron que la secuencia matemática típica que conduce a cursos de cálculo no cubría suficientemente las matemáticas que necesitan los informáticos. Entonces reunieron los temas matemáticos adicionales necesarios en un curso, ahora llamado Matemática discreta.

La secuencia de cálculo se ocupó bastante bien de las funciones de valor real. Pero no se ocupó de muchas matemáticas aparte de las matemáticas de los números reales. Como los números reales son continuos, esto dejó principalmente áreas de matemáticas que trataban con conjuntos de valores discretos en lugar de continuos.

Por ejemplo, la lógica trata con dos valores, verdadero y falso. La teoría de números trata con números naturales o enteros. Aquí hay algunos temas cubiertos en Matemática discreta, y algunos ejemplos en cuanto a su importancia:

1) Lógica. Se utiliza en pruebas para mostrar que un paso se sigue del paso anterior. La lógica se usa en la programación de langusages, e incluso hay un lenguaje de programación cuyo propósito principal es tratar con la lógica: Prolog. Sorprendentemente, las puertas lógicas se utilizan en el hardware de todas las computadoras modernas.

2) Teoría de conjuntos. Esta es una teoría inesperadamente complicada, dado que pensamos principalmente en un conjunto como una colección sin clasificar de objetos únicos. ¿Qué tiene de difícil eso? No lo creerías si te lo dijera. Un tema divertido e importante en la teoría de conjuntos es que algunos conjuntos infinitos son más grandes que otros.

3) Combinatoria (básicamente contando). ¿Sabes contar? Si es así, si tengo una clase de 50 estudiantes, ¿de cuántas maneras puedo elegir 5 de ellos para ayudarme a mover una mesa? Si eso es fácil para ti, prueba esto. McDonalds tiene 50 artículos en su menú. ¿Cuántos pedidos de comida con 8 artículos hay? (Tenga en cuenta que la repetición está permitida aquí. Por ejemplo, puede obtener 5 McRibs y 3 papas fritas grandes. Una comida perfecta).

4) Relaciones de recurrencia y recursividad. La recursión es un tema fascinante, y su importancia en matemáticas no puede ser exagerada. Aquí hay una pregunta simple que se expresa más fácilmente usando una relación de recurrencia. La vida media del cesio 137 es de 30 años. Si comienzas con 1 Kg. de cesio-137, ¿cuánto quedará después de 1000 años?

5) Teoría de grafos. Se pueden modelar tantos aspectos de la vida real con gráficos que los expertos en teoría de gráficos generalmente se centran en unas pocas áreas. Aquí hay una pregunta importante que puede ser respondida por la teoría de grafos. Dadas 20 ciudades, y la distancia entre ellas, ¿cuál es la ruta más corta de una de las ciudades a otra? Un problema fácil de entender. No es tan simple de resolver.

6) Teoría del árbol. ¿Sabía que los archivos y carpetas en su unidad C: se pueden modelar con un árbol? ¿O que un árbol de búsqueda binario puede encontrar un valor en una estructura ordenada con 1 billón de elementos antes de que pueda parpadear?


Entonces, en muchos sentidos, las Matemáticas Discretas apuntalan casi todos los aspectos de la Informática.

En pocas palabras, las matemáticas discretas son el estudio de números racionales, a menudo solo considerando números enteros y no fracciones. En contraste, el análisis real, la rama de las matemáticas que incluye (la mayoría de las formas de) cálculo, incluye números irracionales como pi, e y la raíz cuadrada de 2.

Las computadoras actualmente usan una representación binaria para todo, es decir, cada número está de alguna manera representado por combinaciones de 1s y 0s. Incluso un flotante binario (al menos la implementación de IEEE, el Dr. Gustavson tiene una idea interesante sobre una nueva forma de representar flotadores) es una forma de un número racional.

Como ejemplo, si aproximo pi como 3.14, ya no estoy usando el número irracional en mis cálculos. En cambio, estoy usando el número racional 314 / 1,000 en mis cálculos. Si bien hay algunos códigos que realizan cálculos simbólicos (como Sage, Maple o Mathematica), la mayoría de las veces, cuando una computadora realiza cálculos, la computadora necesita cambiar un número irracional al número racional más cercano que pueda almacenarse en la memoria asignado para mantener un número.

En tus clases de matemáticas discretas de pregrado también tendrás la oportunidad de aprender sobre la prueba matemática formal. Ninguna otra clase de pregrado típica pasará tanto tiempo en la prueba matemática, ciertamente no ninguna de las clases menores de matemáticas que requieren muchas especialidades (como CS, física o química). Este tipo de pensamiento es muy beneficioso para aprender a programar y para resolver problemas en general, ya que este tipo de pensamiento te obliga a pasar tiempo diferenciando lo que sabes de lo que crees que es el caso. A partir de ahí, puedes hacer un trabajo y ver si puedes convertir lo que piensas en algo que sabes.

Las matemáticas discretas no solo son populares en informática sino también en electrónica digital, en las áreas de cifrado / descifrado más relacionadas con la criptografía, el cálculo de la probabilidad y cualquier campo relacionado con las combinaciones de números binarios / contables.

Matemáticas continuas: –

Las matemáticas continuas básicamente tratan con números reales y, por eso, consisten en un conjunto infinito de números sin ningún punto de ruptura involucrado, lo que hace que sea bastante tedioso a veces calcular la probabilidad o cualquier combinación particular mediante un enfoque normal. Las funciones continuas se basan en la idea de descripción topológica.

La representación de una función continua se ve así: –

(Fuente de la imagen: Google)

Ahora en la función anterior hay un número incontable de puntos y, por lo tanto, es difícil sacar una conclusión con respecto a cualquier tipo de probabilidad para un cierto punto.

Matemáticas discretas:-

La matemática discreta o la matemática finita básicamente trata con números distintos o con un número contable de puntos. La ingeniería informática tiene que lidiar con programas, codificación, estructura de árbol donde no es útil traer el concepto de función continua ya que necesitamos muestrear los valores en cada intervalo correspondiente a la lista ordenada de valores.

Por ejemplo:-

Tomemos el ejemplo de la criptografía de claves AES de 256 bits en la que se basa en el algoritmo Rijindael. Ahora, para cada clave privada, hay un conjunto completo de procesos que comienzan desde texto plano a texto cifrado que se basa en cifrado asimétrico. Aquí necesitamos matemáticas discretas porque estamos manejo de combinaciones binarias relacionadas con la matriz S donde el uso de matemáticas continuas es limitado.

Las matemáticas discretas básicamente se ocupan del enfoque de la teoría de grafos donde hay un número finito de puntos.

La representación gráfica de una función discreta se da a continuación:

(Fuente de la imagen: Google)

Matemática discreta está muy relacionada con la informática. Informática teórica, la base de nuestro campo a menudo se considera un subcampo de las matemáticas discretas. La informática se basa en la lógica y en numerosas, si no la mayoría, áreas de matemáticas discretas utilizadas en el campo. Por ejemplo, la teoría de grafos, la combinatoria, la optimización discreta, la teoría de números, la lógica matemática, la teoría de probabilidad discreta, entre muchas otras, son fundamentales para la informática.

Casi me resulta extraño separar los dos. Las matemáticas discretas son un punto de ramificación para la informática, por lo que sirven como una columna vertebral fundamental para comprenderlo.

Los campos de la informática correspondientes a sus respectivos campos de matemática discreta dependen, por supuesto, de las áreas de matemática discreta que esté viendo. Podemos dividir las matemáticas discretas en varios subcampos y ver los consecuentes temas de CS:

  • Lógica

La lógica se usa en gran medida en el diseño de arquitectura de computadoras (puertas lógicas). La deducción lógica se usa en todas partes, desde la IA (Todos los hombres son mortales, Sócrates es un hombre, por lo tanto, Sócrates es mortal), para controlar la teoría y en todas partes donde se deben hacer inferencias.

  • Teoría de grafos

Lo primero que me viene a la mente relacionado con CS son las redes sociales, por ejemplo, Twitter, Facebook. Una gran parte de la teoría de gráficos está buscando conexiones entre nodos. ¿Alguna vez usó la herramienta de “amigos sugeridos” de Facebook? Esto se basa en la teoría de grafos. El número de amigos mutuos entre usted y otra persona es el número de nodos (personas) que tienen bordes conectados a ambos (amigos de ambos).

La matemática discreta es la rama de la matemática que trata con objetos que solo pueden asumir valores distintos y separados. Por lo tanto, el término “matemáticas discretas” se usa en contraste con “matemáticas continuas”, que es la rama de las matemáticas que trata con objetos que pueden variar sin problemas (y que incluye, por ejemplo, el cálculo). Mientras que los objetos discretos a menudo pueden caracterizarse por enteros, los objetos continuos requieren números reales.

El estudio de cómo los objetos discretos se combinan entre sí y las probabilidades de varios resultados se conoce como combinatoria. Otros campos de las matemáticas que se consideran parte de las matemáticas discretas incluyen la teoría de grafos y la teoría de la computación. Los temas de teoría de números como las congruencias y las relaciones de recurrencia también se consideran parte de las matemáticas discretas.

El estudio de temas en matemáticas discretas generalmente incluye el estudio de algoritmos, sus implementaciones y eficiencias. Las matemáticas discretas son el lenguaje matemático de la informática y, como tal, su importancia ha aumentado dramáticamente en las últimas décadas.

El pensamiento discreto es esencialmente el conjunto fundamental de pensamientos detrás de gran parte de la CS. Las estructuras de datos y los algoritmos se basan en ellos muy, muy fuertemente.

Tienes condicionales, gráficos, conjuntos, lógica, casi todo lo que te permite pensar en CS desde una máquina Turing hasta arriba.

Muchos de estos son temas con mucho más terreno que cubrir que una sola clase, pero Discrete hace un buen trabajo al brindarle los fundamentos y establece las bases para una gran cantidad de comp. También creo que las matemáticas discretas (si puede llamarlas matemáticas) se correlacionan más directamente con CS y es un curso de muestra bastante fácil de probar si desea ver si tiene aptitud para CS.

La matemática discreta es la rama de las matemáticas que se ocupa de conjuntos finitos de valores (de ahí la parte “discreta” del nombre), en lugar de las funciones continuas que estudia el cálculo.

Las matemáticas discretas tienden a centrarse en cosas como el razonamiento matemático, las pruebas, la teoría de grafos, los árboles n-arios, solo por nombrar algunas cosas. Es indispensable para la informática desde un punto de vista teórico.

Debido a que las computadoras son sistemas discretos, y las matemáticas discretas es el estudio de sistemas discretos.

Es una rama de las Matemáticas que se enfoca en estudiar estructuras matemáticas que son de naturaleza discreta (distinta y separada) en lugar de continua (p. Ej. Trigonometría, cálculo). Los objetos en Matemática discreta varían en formas fijas, por ejemplo, lógica y son diferentes a los objetos en Matemática no discreta para, por ejemplo, una curva sinusoidal que varía continuamente.

Enlazar:
Matemáticas discretas

Me gradué en física teórica. Comencé en “física nuclear” y terminé con “física teórica” ​​(“nuclear” se volvió bastante impopular).

Al mismo tiempo, fui por un menor en “matemáticas”. Esto se convirtió en un menor en “matemáticas aplicadas”.

Eventualmente, iba a obtener un título en “Física teórica” ​​y un título de grado en “Ingeniería de software con énfasis en informática”.

El título de “matemática aplicada” era “gratis” debido a los requisitos del curso. Si tenías el grado SWE y la física, tenías las matemáticas para el grado de matemáticas. “¡Hurra! ¡Grado gratis!


Matemáticas discretas son muy necesarias para unos 15 grados de ciencias.


Puedes hablar sobre lo finito o lo infinito, pero es una cosa de A contra B. Yo (personalmente) llamaría al campo “matemáticas finitas”.

Si gana el premio Fulkerson, difiero a su criterio. Principalmente. Si estas buscando.

Si no, me burlo de ti.

En términos generales, las matemáticas discretas son el estudio de la aritmética de enteros (no solo realizar la aritmética, sino un metaestudio que profundiza en la teoría de conjuntos, etc.). Es importante para CS porque una gran cantidad de CS se reduce a contar cosas.

¿Qué pasaría si un avión tuviera solo 9 puntos? Ese sería un ejemplo de matemática discreta. Es útil en algunos algoritmos para la informática. Es particularmente adecuado para la informática, ya que la forma de expresión nativa de las computadoras consiste en solo 1 y 0.

La matemática discreta es la rama de la matemática relacionada con el conteo de cosas (p. Ej., Combinaciones, permutaciones, el teorema binomial, la cantidad de elementos en un conjunto mediante el principio de inclusión-exclusión, la generación de funciones, la cantidad de formas en que n elementos pueden dividirse en r contenedores sujetos a algunas restricciones).

Las computadoras realmente no manejan sistemas continuos. Incluso cuando se usan para calcular valores numéricos, usan aproximaciones finitas. Las computadoras realmente no calculan límites. Aplican algoritmos matemáticos que se sabe que convergen independientemente de cualquier aplicación informática.

Los datos con los que operan las computadoras son conjuntos finitos de valores discretos. Por lo tanto, las computadoras no realizan operaciones en objetos cardinales u ordinales infinitos.

Honestamente, estoy un poco irritado por la cantidad de veces que veo esta pregunta. Honestamente, ¿hay algo especialmente confuso sobre el artículo de Wikipedia sobre matemáticas discretas?

En términos generales, la informática es un subconjunto estricto de las matemáticas discretas.

Si desea ver cómo se utilizan las matemáticas discretas en informática, le recomiendo que tome una copia de Knuth The Art Of Computer Programming y eche un vistazo a la sección de preliminares.

Claro que esto podría ser bastante desafiante para alguien en la escuela secundaria.

Aquí hay otra forma más meta de ver la relación. Los programas de computadora son esencialmente cadenas de bits de 1 y 0. Puede preguntar cuántos posibles programas de computadora hay de 1000 bits. Una aplicación trivial de matemática discreta me dice que hay como máximo 2 ^ 1000 de estos programas, ya que hay exactamente esa cantidad de cadenas de bits de esa longitud y cada programa se asigna a una sola cadena de bits.

Espero que esto ayude