- ES Español (Latinoamérica)

- EN English

4.4. Matemáticas Discretas y Combinatoria (DMC)
Esta área cubre las matemáticas de estructuras finitas y numerables, incluyendo la enumeración combinatoria, la teoría de grafos, la optimización discreta y los fundamentos lógicos de las matemáticas. Sustenta la informática teórica, la investigación de operaciones y la ciencia de datos moderna.
| Área de Conocimiento (KA) | Core Tier1 | Core Tier2 |
4.4.1 Combinatoria Enumerativa | 1 | 1 |
4.4.2 Teoría de Grafos | 1 | 1 |
4.4.3 Combinatoria Extremal y Probabilística | Electivo | |
4.4.4 Optimización Discreta | 1 | 1 |
4.4.5 Teoría de Diseños y Códigos Combinatorios | Electivo | |
4.4.6 Lógica Matemática y Teoría de Conjuntos | 1 | 1 |
4.4.1. DMC/Combinatoria Enumerativa (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba
Conteo sistemático de estructuras discretas mediante biyecciones, recursiones, 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, tablas de Young y la fórmula de la longitud del gancho
- Demostraciones biyectivas e inversión de Möbius en conjuntos parcialmente ordenados
Aprendizaje esperado (Learning Outcomes):
Core:
- Aplicar principios básicos de conteo e inclusión-exclusión a problemas de enumeración [Familiarizarse]
- Construir funciones generadoras ordinarias y exponenciales para enumerar estructuras combinatorias [Usar]
- Derivar fórmulas de forma cerrada para sucesiones combinatorias usando biyecciones e inversión de Möbius [Evaluar]
4.4.2. DMC/Teoría de Grafos (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba
Estructura y propiedades de grafos: conectividad, coloraciones, emparejamientos, planaridad y teoría espectral de grafos.
Temas:
Core
- Grafos: definiciones, isomorfismo, sucesiones de grados, árboles y árboles generadores
- 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 planares, fórmula de Euler, teorema de Kuratowski y el teorema de los cuatro colores
- Matrices de adyacencia y laplaciana, valores propios y grafos expandidores
Aprendizaje esperado (Learning Outcomes):
Core:
- Identificar propiedades estructurales de grafos (conectividad, planaridad, bipartitud) y aplicar la fórmula de Euler [Familiarizarse]
- Aplicar el teorema de matrimonio de Hall y algoritmos de flujo en redes a problemas de emparejamiento y enrutamiento [Usar]
- Analizar el espectro de un grafo para acotar su número cromático y sus propiedades de conectividad [Evaluar]
4.4.3. DMC/Combinatoria Extremal y Probabilística ↑ Volver arriba
Problemas extremales en grafos y sistemas de conjuntos, el método probabilístico y grafos aleatorios.
Temas:
Non Core
- Problemas de tipo Turán: teorema de Turán y teorema de Kruskal-Katona
- El método probabilístico: métodos del primer y segundo momento, Lema Local de Lovász
- Grafos aleatorios de Erdős-Rényi: fenómenos de umbral y estructura de componentes
- Teoría de Ramsey: números de Ramsey, teorema de van der Waerden y Hales-Jewett
- Métodos algebraicos en combinatoria: método polinomial y teorema de Chevalley-Warning
Aprendizaje esperado (Learning Outcomes):
NonCore:
- Enunciar el teorema de Turán y aplicarlo para acotar el número de aristas en un grafo libre de \(K_r\) [Familiarizarse]
- Aplicar el método probabilístico y el Lema Local de Lovász para demostrar la existencia de estructuras combinatorias [Usar]
- Analizar fenómenos de umbral en grafos aleatorios de Erdős-Rényi usando métodos del primer y segundo momento [Evaluar]
4.4.4. DMC/Optimización Discreta (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba
Programación entera, flujos en redes, matroides, algoritmos de emparejamiento y teoría de NP-completitud.
Temas:
Core
- Programación lineal entera: ramificación y acotamiento, 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 matroides: conjuntos independientes, algoritmo voraz e intersección de matroides
- Teoría de complejidad: P vs. NP, NP-completitud y reducciones
- Algoritmos de aproximación y esquema de aproximación polinomial (PTAS)
Aprendizaje esperado (Learning Outcomes):
Core:
- Explicar la relación entre las relajaciones de programación lineal y las cotas de programación entera [Familiarizarse]
- Aplicar algoritmos de flujo en redes y de matroides para resolver problemas de optimización combinatoria [Usar]
- Demostrar la NP-completitud de un problema combinatorio mediante reducción polinomial [Evaluar]
4.4.5. DMC/Teoría de Diseños y Códigos Combinatorios ↑ Volver arriba
Diseños combinatorios, cuadrados latinos, geometrías finitas y sus conexiones con los códigos correctores de errores.
Temas:
Non Core
- Diseños de bloques: diseños de bloques incompletos balanceados (BIBD), desigualdad de Fisher y diseños simétricos
- Cuadrados latinos, ortogonalidad y aplicaciones al diseño experimental
- Planos proyectivos y afines finitos; conexión con diseños combinatorios
- Matrices de Hadamard y sus aplicaciones en codificación y procesamiento de señales
- Conexiones entre diseños combinatorios y códigos lineales (Hamming, Golay)
Aprendizaje esperado (Learning Outcomes):
NonCore:
- Definir un BIBD y verificar que una configuración dada satisface sus parámetros [Familiarizarse]
- Construir un diseño balanceado o cuadrados latinos ortogonales para un conjunto de parámetros dado [Usar]
- Relacionar la estructura de un diseño combinatorio con la matriz de verificación de paridad de un código lineal correspondiente [Evaluar]
4.4.6. DMC/Lógica Matemática y Teoría de Conjuntos (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba
Lógica proposicional y de primer orden, sistemas de demostración, teoremas de completitud e incompletitud de Gödel y teoría axiomática de conjuntos.
Temas:
Core
- Lógica proposicional: sintaxis, semántica, satisfacibilidad y resolución
- Lógica de primer orden: modelos, corrección y 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:
- Enunciar los teoremas de completitud y primer teorema de incompletitud de Gödel y explicar su significado [Familiarizarse]
- Construir demostraciones formales en lógica de primer orden y determinar la satisfacibilidad de fórmulas [Usar]
- Analizar la indecidibilidad de problemas mediante reducción al problema de la parada [Evaluar]