MATEMÁTICAS DISCRETAS
|
Objetivo:
Brindar un cuerpo
de conocimientos formales, esencialmente vinculados con la filosofía y
disciplina computacionales. Proporcionar técnicas para planteamiento y
resolución de problemas de conteo y enumeración.
1 Lógica y conjuntos
MA21 Lógica proposicional. Sustitución textual
y el concepto de igualdad. Expresiones booleanas. Igualdad y equivalencia. Satisfacibilidad,
validez y dualidad. Teoremas de negación, inequivalencia, falso, disyunción,
conjunción e implicación. Otros métodos de demostración:
modus ponens; modus tollens; suposición del antecedente; demostración
por casos; demostración por contradicción; demostración
por contrapositivo. Aplicaciones
MA22 Lógica de predicados. Cuantificación. Sintaxis
e interpretación de la cuantificación. Reglas de manipulación.
Rangos. Cuantificación universal. Cuantificación existencial.
Predicados y programación: precondiciones y postcondiciones; invariantes.
MA23 Conjuntos. Teoría de conjuntos. Descripción de
conjuntos y membresía. Predicados para la membresía. Lógica
de predicados y membresía. Operaciones sobre conjuntos. Teoremas relativos
a las operaciones sobre conjuntos. Unión e intersección de familias
de conjuntos. El axioma de elección. Paradojas y conjuntos mal definidos.
2 Combinatoria
MA24 Análisis combinatorio. Inducción y recursión.
Ordenaciones, permutaciones y combinaciones. Teorema del binomio. Coeficientes
binomiales. Principio de inclusión y exclusión. Teoría
de conteo. Funciones generadoras. Relaciones de recurrencia.
3 Relaciones y grafos
MA25 Relaciones. Relaciones binarias y operaciones sobre
ellas. Propiedades reflexiva, simétrica, transitiva y antisimétrica
de relaciones binarias. Cerraduras simétrica, reflexiva y transitiva.
Órdenes parciales. Conjuntos finitos parcialmente ordenados (lattices).
Relación uno a uno entre las relaciones de equivalencia y las particiones
en clases de equivalencia.
MA26 Gráficas. Gráficas simples. Isomorfismo entre
gráficas. Matrices de incidencia y adyacencia. Subgráficas. Grado
de un vértice. Trayectorias y conexidad. Gráficas planas, planares
y duales. Ciclos. Recorrido de Euler. Ciclos hamiltonianos. Apareamientos. Coloración
de aristas y vértices. Números cromáticos.
MA27 Árboles. Definición. Aristas de corte. Vértices
de corte. Conexidad. Profundidad. Recorridos. Árboles balanceados. Aplicaciones.
Árboles como fundamentación matemática de estructuras de
datos.
|
|
| |
