Yachakaj: CM2H1 MATEMÁTICA DISCRETA

a) Preparación
Problemas ligados a la matemática discreta. Notaciones comunes. Inducción matemática. Funciones y relaciones. Relaciones de equivalencia y de orden parcial.
b) Conteo (teoría + ejercicios)
Funciones y subconjuntos. Permutaciones y factoriales. Coeficientes binomiales. Comparación asintótica de funciones: las notaciones O, o. Estimados de la función factorial y los coeficientes binomiales. El principio de inclusión-exclusión.
c) Grafos (teoría + ejercicios)
Noción de grafo; isomorfismo. Subgrafos, componentes, matriz de adyacencia. Secuencia de grados de un grafo. Grafos eulerianos. 2-conectividad.
d) Árboles
Definición y caracterizaciones. Isomorfismo de árboles. Árboles de expansión de un grafo. El problema del árbol de expansión mínima. El número de árboles de expansión mínima.
e) Graficando grafos en el plano
Graficando en el plano y otras superficies. Ciclos en grafos planares. Fórmula de Euler. Coloreando mapas: el problema de los cuatro colores.
f) Enteros, divisores, primalidad (teoría + ejercicios)
Divisibilidad de enteros. Factorización en primos. El algoritmo de Euclides. Congruencias. Aritmética modular. Elementos invertibles módulo n. El pequeño teorema de Fermat. Descubriendo números compuestos.
g) Criptografía (teoría + ejercicios)
Un método de criptografía simétrica. La propuesta de Diffie y Hellman. El método RSA. El problema del logaritmo discreto.