3.3. 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.

3.3.1. DMC/Combinatoria Enumerativa

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

Aprendizaje esperado (Learning Outcomes):
Core:

1.

Aplicar principios básicos de conteo e 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 de forma cerrada para sucesiones combinatorias usando biyecciones e inversión de Möbius [Evaluar]

3.3.2. DMC/Teoría de Grafos

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:

1.

Identificar propiedades estructurales de grafos (conectividad, planaridad, bipartitud) y aplicar la fórmula de Euler [Familiarizarse]

2.

Aplicar el teorema de matrimonio 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

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:

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 de matroides 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

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:

1.

Enunciar los teoremas de completitud y primer teorema de incompletitud de Gödel y explicar su significado [Familiarizarse]

2.

Construir demostraciones 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]