En este curso se estudian estructuras y modelos matemáticos básicos necesarios en el diseño de algoritmos y solución de problemas computacionales.
Enfrentar al estudiante a problemas de ciencias de la computación y la informática para que comprenda y aplique modelos de matemáticas discretas para la solución eficaz y eficiente de dichos problemas.
Durante este curso el estudiante desarrollará habilidades para:
- Identificar un modelo matemático que corresponda a la resolución de un problema.
- Aplicar modelos de matemáticas discretas para resolver problemas computacionales.
- Comprender y realizar pruebas matemáticas para desarrollar el pensamiento lógicomatemático.
| Objetivo específico | Eje temático | Desglose |
|---|---|---|
| 1,2,3 | Introducción | Definicion de matemática discreta y sus principales temas. Utilidad en la solución de problemas. Tipos de problemas que pueden ser resueltos usando matemáticas discretas. |
| 1,2,3 | Teoría de números | Divisibilidad y divisores, números primos y compuestos, el teorema de la división, residuos y equivalencia modular, divisores comunes, máximo común divisor (mcd), primos relativos, factorización única. Cálculo del mcd, algoritmo de Euclides, mcd(a,b) como combinación lineal de a y b, algoritmo del cálculo de los coeficientes lineales del mcd. Aritmética modular. Congruencia modular. Ecuaciones lineales modulares. Potencias de un elemento, teorema del resto chino, solución de sistemas de congruencias, algoritmo eficiente para la exponenciación modular. Cifrados simétricos y asimétricos. Operación y correctitud RSA (Rivest, Shamir y Adleman). |
| 1,2,3 | Conteo | Ejemplos de motivación. Regla de la suma y del producto. El principio del palomar. Permutaciones y combinaciones. |
| 1,2,3 | Recursividad y relaciones de recurrencia | Funciones recursivas y su aplicación a la computación. Solución de relaciones de recurrencia lineales homogéneas y no homogéneas. Solución de relaciones de recurrencia no lineales. |
| 1,2,3 | Grafos y árboles | Grafos dirigidos y no dirigidos y su aplicación en la resolución de diversos tipos de problemas. Algoritmos para grafos (algoritmos de recorrido en anchura primero, en profundidad primero, algoritmo de Dijkstra y Floyd, árbol de mínimo costo y algoritmos de Prim y Kruskal, caminosy circuitos de Euler, caminos y circuitos de Hamilton de menor costo, isomorfismo). |
| 1,2,3 | Álgebra booleana y circuitos lógicos | Algebra booleana, dualidad, orden y expresiones booleanas. Representación gráfica de compuertas lógicas y circuitos lógicos. Expresiones booleanas minimales, minit´erminos, implicantes, mapas de Karnaugh. Circuitos minimales AND-OR. |
[1] K. Rosen. ((Discrete Mathematics and Its Applications)). McGraw-Hill (2012).
[2] B. Kolman. ((Discrete Mathematical Structures)). Prentice Hall (1996).
[3] S. Lipschutz. ((Discrete Mathematics)). McGraw-Hill (2007).
[4] L. Lovasz. ((Discrete Mathematics: Elementary and Beyond)). Springer-Verlag (2003).
Este no es un documento oficial. Documentos oficiales se entregan en la secretaría de la escuela.