- (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 (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.
- (números y notaciones)
- (sumatorias y productorias)
- (principios del buen orden)
- (def 1: menor elemento; def 2: bien ordenado)
- (principio del buen orden)
(ejm)
(ejm: algoritmo de la división)
- (principio de inducción matemática)
- (primer principio de inducción: principio de inducción simple)
- (principio de inducción matemático generalizado)
- (segundo principio de inducción: principio de inducción fuerte)
(ejm)
- (variante del principio de inducción fuerte 1)
- (variante del principio de inducción fuerte 2)
- (PIM y PBO)
- (conjuntos)
(ejm)
(def 1: conjunto vacio; def 2: inclusión)
(propiedades de la inclusión; def 3: conjunto de partes)
(operaciones entre conjuntos)
(propiedades de conjuntos)
(tamaño de un conjunto)
(producto cartesiano)
- (relaciones)
(def 8: composición; def 9: relación inversa)
(def 10: reflexiva; def 11: simétrica; def 12: transitiva; def 13: antisimétrica)
(ejm)
- (funciones)
- (función)
- (definiciones)
(ejm)
- (propiedades)
- (def 14: inyectiva; def 15: sobreyectiva; def 16: biyectiva)
(ejm)
- (composición de funciones)
(propiedades)
- (def 17: inversa a derecha; def 18: inversa a izquierda; def 19: función inversa)
(ejm)
(propiedades)
- (relación de equivalencia; relación de orden parcial y total, ordenamiento por inclusión parcial y total)
- (relación de equivalencia)
- (relación de equivalencia)
(ejm 1)
(ejm 2)
- (clase de equivalencia y conjunto cociente)
- (def: clase de equivalencia; def: conjunto cociente)
(ejm)
- (propiedades)
- (relación de orden parcial y total)
- (relación de orden parcial)
- (relación de orden total o lineal)
- (proposición)
(ejm)
- (elementos minimales y maximales; diagrama de Hasse; ordenamiento lineal; ordenamiento por inclusión parcial y total)
- (elementos minimales y maximales)
- (def)
- (diagrama de Hasse)
- (ordenamiento por inclusión)
- (def: encaje)
(ejm)
- (teorema)
- (diagrama de Hasse de (2^x, C))
- (obs)
- (independencia sobre un conjunto ordenado)
- (def: independiente)
- (def: cadena; teorema)
- (conteo combinatorio)
- (proposición 1)
- (proposición 2)
- (proposición 3)
- (proposición 4)
- (permutaciones)
- (def 1: permutación)
(ejm)
- (teorema 1)
- (combinaciones)
- (def 2: coeficiente binomial)
- (def 3)
- (proposición 5)
- (propiedades)
- (teorema 2, 3)
- (ejemplo clásico usando el coeficiente binomial)
(ejm)
- (teorema 4: teorema binomial)
- (coeficiente binomial)
- (teorema 1: teorema binomial)
- (proposición 1)
- (coeficiente multinomial)
- (¿cómo ordenar elementos de un conjunto cuando uno de sus elementos se pire? ejemplo)
- (proposición 2: caso general)
- (lema 1: )
- (teorema 2: teorema multinomial)
(ejm)
- (estimación función factorial)
- (primeras estimaciones)
(n! está más cerca de 2^n-1 o de n^n)
- (teorema 3)
- (teorema 4)
- (teorema 5: fórmula de Stirling)
- (estimaciones de los coeficientes binomiales, fórmula de Stirling, principio del Palomar)
- (estimación de los coeficientes binomiales)
- (introducción)
- (teorema)
- (proposición)
- (estimación usando una relación de equivalencia)
- (fórmula de Stirling)
- (fórmula de Stirling)
- (estimación del coeficiente binomial usando Stirling)
- (teorema)
- (principio del Palomar)
- (principio del Palomar)
- (consecuencias)
- (principio de inclusión y exclusión, álgebra de boole, funciones booleanas)
- (principio de inclusión y exclusión)
- (resultados previos)
- (proposición 1, 2)
- (teorema: principio de inclusión-exclusión)
(ejm)
- (teorema: fórmula del indicador)
- (álgebra de boole)
- (funciones booleanas)
- ()
(
conjuntos)
(ejm)
(def 1: conjunto vacio; def 2: inclusión)
(propiedades de la inclusión; def 3: conjunto de partes)
(operaciones entre conjuntos)
(propiedades de conjuntos)
(tamaño de un conjunto)
(producto cartesiano)
(
relaciones)
(def 8: composición; def 9: relación inversa)
(def 10: reflexiva; def 11: simétrica; def 12: transitiva; def 13: antisimétrica)
(ejm)
(
funciones)
(función)
(definiciones)
(ejm)
(propiedades)
(def 14: inyectiva; def 15: sobreyectiva; def 16: biyectiva)
(ejm)
(composición de funciones)
(propiedades)
(def 17: inversa a derecha; def 18: inversa a izquierda; def 19: función inversa)
(ejm)
(propiedades)
(elementos minimales y maximales; diagrama de Hasse; ordenamiento lineal; ordenamiento por inclusión parcial y total)
(elementos minimales y maximales)(def)
(diagrama de Hasse)
(teorema)
(ordenamiento por inclusión)(def: encaje)
(ejm)
(teorema)
(diagrama de Hasse de (2^x, C))
(independencia sobre un conjunto ordenado)(def: independiente)
(def; teorema)
(estimaciones de los coeficientes binomiales, fórmula de Stirling, principio del Palomar)
(introducción)
(teorema)
(proposición)
(estimación usando una relación de equivalencia)
(fórmula de Stirling)
(estimación del coeficiente binomial usando Stirling)
(teorema)
(principio del Palomar)
(consecuencias)
(ejm 1)
(ejm 2)
(números y notaciones)
(sumatorias y productorias)
(principios del buen orden)
(principio del buen orden)
(ejm)
(ejm: algoritmo de la división)
(principio de inducción matemática)
(principio de inducción simple)
(principio de inducción matemático generalizado)
(principio de inducción fuerte)
(ejm)
(variante del principio de inducción fuerte 1)
(variante del principio de inducción fuerte 2)
(PIM y PBO)
(conjuntos)
(ejm)
(def 1: conjunto vacio; def 2: inclusión)
(propiedades de la inclusión; def 3: conjunto de partes)
(operaciones entre conjuntos)
(propiedades de conjuntos)
(tamaño de un conjunto)
(producto cartesiano)
(relaciones)
(def 8: composición; def 9: relación inversa)
(def 10: reflexiva; def 11: simétrica; def 12: transitiva; def 13: antisimétrica)
(ejm)
(funciones)
(función)
(definiciones)
(ejm)
(propiedades)
(def 14: inyectiva; def 15: sobreyectiva; def 16: biyectiva)
(ejm)
(composición de funciones)
(propiedades)
(def 17: inversa a derecha; def 18: inversa a izquierda; def 19: función inversa)
(ejm)
(propiedades)
(relación de equivalencia; relación de orden parcial y total, ordenamiento por inclusión parcial y total)
(relación de equivalencia)
(ejm 1)
(ejm 2)
(clase de equivalencia y conjunto cociente)
(ejm)
(propiedades)
(relación de orden parcial)
(relación de orden total o lineal)
(proposición)
(ejm)
(elementos minimales y maximales; diagrama de Hasse; ordenamiento lineal; ordenamiento por inclusión parcial y total)
(elementos minimales y maximales)(def)
(diagrama de Hasse)
(teorema)
(ordenamiento por inclusión)(def: encaje)
(ejm)
(teorema)
(diagrama de Hasse de (2^x, C))
(independencia sobre un conjunto ordenado)(def: independiente)
(def; teorema)
(conteo combinatorio)
(proposición 1)
(proposición 2)
(proposición 3)
(proposición 4)
(permutaciones)
(def 1: permutación)
(ejm)
(teorema 1)
(combinaciones)
(coeficientes binomiales)(def 2: coeficiente binomial)
(def 3)
(proposición 5)
(propiedades)(teorema 2, 3)
(ejemplo clásico usando el coeficiente binomial)
(ejm)
(teorema 4: teorema binomial)
(coeficiente binomial)
(teorema 1: teorema binomial)
(proposición 1)
(coeficiente multinomial)
(¿cómo ordenar elementos de un conjunto cuando uno de sus elementos se pire? ejemplo)
(proposición 2: caso general)
(lema 1: )
(teorema 2: teorema multinomial)
(ejm)
(estimación función factorial)
(primeras estimaciones)
(n! está más cerca de 2^n-1 o de n^n)
(teorema 3)
(teorema 4)
(teorema 5: fórmula de Stirling)
(estimaciones de los coeficientes binomiales, fórmula de Stirling, principio del Palomar)
(introducción)
(teorema)
(proposición)
(estimación usando una relación de equivalencia)
(fórmula de Stirling)
(estimación del coeficiente binomial usando Stirling)
(teorema)
(principio del Palomar)
(consecuencias)
(principio de inclusión y exclusión, álgebra de boole, funciones booleanas)
(resultados previos)(proposición 1, 2)
(teorema: principio de inclusión-exclusión)
(ejm)
(fórmula del indicador)(teorema)
(álgebra de boole)(def)
(teorema)
(funciones booleanas)
(ejm 1)
(ejm 2)
No hay comentarios.:
Publicar un comentario