Saltar al contenido ForoHackers

Matemática discreta: por dónde empezar

Matemática discreta
#3136 · · Citar · Denunciar

La matemática discreta es la matemática de las cosas contables: enteros, conjuntos, enunciados lógicos, grafos y estructuras finitas. Las computadoras trabajan justo con eso, así que es el lenguaje de trabajo de los algoritmos, la criptografía, las bases de datos y las demostraciones. También enseña el hábito de enunciar una afirmación con precisión y demostrarla.

Conceptos clave

  • Lógica y demostración: implicaciones, cuantificadores, prueba directa, por contradicción e inducción.
  • Conjuntos, relaciones y funciones: el vocabulario para describir cualquier estructura, incluidas las relaciones de equivalencia y los órdenes.
  • Teoría de números: divisibilidad, primos, máximo común divisor y aritmética modular, la base del hashing y de la criptografía.
  • Conteo y recurrencias: cuántos objetos hay, y cómo se define una sucesión a sí misma.
  • Grafos y árboles: el modelo básico de las cosas conectadas.

Vocabulario

  • Inducción: demostrar un caso base y que cada caso implica el siguiente, para cubrir todos los números naturales.
  • Congruencia: dos enteros son congruentes módulo n cuando n divide su diferencia.
  • Biyección: un emparejamiento uno a uno entre dos conjuntos, usado para comparar tamaños.
  • Orden parcial: una relación reflexiva, antisimétrica y transitiva, como «divide a».

Qué estudiar, en orden

  1. Lógica proposicional y tablas de verdad; luego escribe demostraciones por contradicción y por inducción.
  2. Conjuntos, funciones y relaciones, y comprueba relaciones de equivalencia en código.
  3. Aritmética modular: implementa el algoritmo de Euclides y la exponenciación modular.
  4. Conteo: permutaciones, combinaciones, el principio del palomar y recurrencias resueltas a mano.
  5. Lo básico de grafos, y luego un proyecto pequeño que use varias de estas ideas, como un RSA de juguete.

Etiquetas relacionadas

#combinatorics #graph-theory #logic #cryptography #algorithms

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder