• ES Español
• EN English

3.3. Matemática Discreta y Combinatoria (DMC)

Esta área cubre la matemática de las estructuras finitas y contables, incluyendo la enumeración combinatoria, la teoría de grafos, la optimización discreta y los fundamentos lógicos de la informática. Es fundamental para el diseño de algoritmos, los lenguajes formales, los sistemas de tipos y la teoría de compiladores.

Área de Conocimiento (KA)	CS Core	KA Core
3.3.1 Combinatoria Enumerativa	Electivo
3.3.2 Teoría de Grafos	Electivo
3.3.3 Optimización Discreta	Electivo
3.3.4 Lógica Matemática y Teoría de Conjuntos	Electivo

3.3.1. DMC/Combinatoria Enumerativa ↑ Volver arriba

Conteo sistemático de estructuras discretas mediante biyecciones, recurrencias, funciones generadoras y el principio de inclusión-exclusión.
Temas:
Core

• Principios básicos de conteo: permutaciones, combinaciones y el teorema del binomio
• Principio de inclusión-exclusión y aplicaciones a desarreglos y la función totiente de Euler
• Funciones generadoras ordinarias y exponenciales; resolución de recurrencias
• Particiones de enteros, tableaux de Young y la fórmula de la longitud del gancho

Aprendizaje esperado (Learning Outcomes):
Core:

1. Aplicar los principios básicos de conteo y la inclusión-exclusión a problemas de enumeración [Familiarizarse]
2. Construir funciones generadoras ordinarias y exponenciales para enumerar estructuras combinatorias [Usar]
3. Derivar fórmulas cerradas para sucesiones combinatorias mediante biyecciones y recurrencias [Evaluar]

3.3.2. DMC/Teoría de Grafos ↑ Volver arriba

Estructura y propiedades de los grafos: conectividad, coloraciones, emparejamientos, planaridad y teoría espectral de grafos, con aplicaciones a redes y algoritmos.
Temas:
Core

• Grafos: definiciones, isomorfismo, sucesiones de grados, árboles y árboles de expansión
• Conectividad, Teorema de Menger y flujos en redes (flujo máximo-corte mínimo)
• Emparejamientos (Teorema de Hall), coloraciones de grafos y el polinomio cromático
• Grafos planos, fórmula de Euler, Teorema de Kuratowski y el teorema de los cuatro colores
• Matrices de adyacencia y laplaciana, valores propios y grafos expansores

Aprendizaje esperado (Learning Outcomes):
Core:

1. Identificar propiedades estructurales de grafos (conectividad, planaridad, bipartición) y aplicar la fórmula de Euler [Familiarizarse]
2. Aplicar el Teorema de Hall y algoritmos de flujo en redes a problemas de emparejamiento y enrutamiento [Usar]
3. Analizar el espectro de un grafo para acotar su número cromático y sus propiedades de conectividad [Evaluar]

3.3.3. DMC/Optimización Discreta ↑ Volver arriba

Programación entera, flujos en redes, matroidesTEORIA, algoritmos de emparejamiento y la teoría de NP-completitud, fundamental para el diseño de algoritmos en computación.
Temas:
Core

• Programación lineal entera: ramificación y acotación, planos de corte y matrices totalmente unimodulares
• Algoritmos de flujo en redes: caminos más cortos, flujo máximo, flujo de costo mínimo
• Teoría de matroidesTEORIA: conjuntos independientes, algoritmo greedy e intersección de matroidesTEORIA
• Teoría de complejidad: P vs. NP, NP-completitud y reducciones
• Algoritmos de aproximación y el esquema de aproximación en tiempo polinomial (PTAS)

Aprendizaje esperado (Learning Outcomes):
Core:

1. Explicar la relación entre las relajaciones de programación lineal y las cotas de programación entera [Familiarizarse]
2. Aplicar algoritmos de flujo en redes y matroidesTEORIA para resolver problemas de optimización combinatoria [Usar]
3. Demostrar la NP-completitud de un problema combinatorio mediante reducción polinomial [Evaluar]

3.3.4. DMC/Lógica Matemática y Teoría de Conjuntos ↑ Volver arriba

Lógica proposicional y de primer orden, sistemas de prueba, teoremas de Gödel y computabilidad, que forman el fundamento lógico de los lenguajes de programación y la verificación formal.
Temas:
Core

• Lógica proposicional: sintaxis, semántica, satisfacibilidad y resolución
• Lógica de primer orden: modelos, corrección y el Teorema de Completitud de Gödel
• Teoremas de Incompletitud de Gödel y sus implicaciones para los sistemas formales
• Teoría axiomática de conjuntos (ZFC): ordinales, cardinales y el axioma de elección
• Computabilidad: máquinas de Turing, decidibilidad y el problema de la parada

Aprendizaje esperado (Learning Outcomes):
Core:

1. Enunciar los Teoremas de Completitud e Incompletitud de Gödel y explicar su importancia para la computación [Familiarizarse]
2. Construir pruebas formales en lógica de primer orden y determinar la satisfacibilidad de fórmulas [Usar]
3. Analizar la indecidibilidad de problemas mediante reducción al problema de la parada [Evaluar]