Skip to the content ForoHackers
Log inJoin

Matemática discreta: por dónde empezar

Discrete mathematics
#630 · Ophuscado · · Report

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

Log in or join to reply.