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 
  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 
  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 
  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 
  Un método de criptografía simétrica. La propuesta de Diffie y Hellman. El método RSA. El problema del logaritmo discreto.

---