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
- Lógica proposicional y tablas de verdad; luego escribe demostraciones por contradicción y por inducción.
- Conjuntos, funciones y relaciones, y comprueba relaciones de equivalencia en código.
- Aritmética modular: implementa el algoritmo de Euclides y la exponenciación modular.
- Conteo: permutaciones, combinaciones, el principio del palomar y recurrencias resueltas a mano.
- 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