CM2H1 MATEMÁTICA DISCRETA

---

• (Prácticas y exámenes)
• (Bibliografía)
• Matemática discreta y sus aplicaciones (5ta ed.). Rosen Kenneth.
• 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.

---

(números y notaciones)(principios del buen orden)(principio de inducción matemática)(PIM y PBO)

(conjuntos)(relaciones)(funciones)

(relación de equivalencia; relación de orden parcial y total, ordenamiento por inclusión parcial y total)

(elementos minimales y maximales; diagrama de Hasse; ordenamiento lineal; ordenamiento por inclusión parcial y total)

(conteo combinatorio)(permutaciones)(combinaciones)

(coeficiente binomial)

(estimaciones de los coeficientes binomiales, fórmula de Stirling, principio de Palomar)

(principio de inclusión y exclusión, álgebra de boole, funciones booleanas)

(grafos)(grafos importantes)(grafos isomorfos)(subgrafos)(conexidad)

(distancia de grafos)(matriz de adyacencia)(score de un grafo)

(grafos eurelianos; grafos eurelianos dirigidos; principio del Palomar)

(grafos 2-conexo; operaciones en grafo; grafos libres de triángulos)

(árboles)(isomorfismo de árboles)

(codificando los árboles)

(árbol de expansión de un grafo; noción del árbol de expansión mínima)

(algoritmo de Kruskal; algoritmo Dijkstra)

(grafos planares)(ciclos en grafos planares)

(fórmula de Euler)(coloración de mapas)

(algoritmo de la división; MCD y MCM; teorema fundamental de la aritmética)

(teorema del chino resto)(los enteros módulo n)

(pequeño teorema de Fermat)(teorema de Wilson)(teorema de Euler)

(orden)(raíces primitivas)

(logaritmo discreto; propiedades; ejemplos)

(residuos cuadráticos)(símbolo de Legendre)(ley de reciprocidad cuadrática)

(criptografía)(tipos de cifrado)

(cifrados poligráficos)(autocifrados)

(cifrado de Vernam)(RSA)

---