4.4. Matemáticas Discretas y Combinatoria (DMC)

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.

Tabla 4.4: Lista de KUs del área de Matemáticas Discretas y Combinatoria.

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:

  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]

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:

  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]

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:

  1. Enunciar el teorema de Turán y aplicarlo para acotar el número de aristas en un grafo libre de \(K_r\) [Familiarizarse]
  2. Aplicar el método probabilístico y el Lema Local de Lovász para demostrar la existencia de estructuras combinatorias [Usar]
  3. 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:

  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]

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:

  1. Definir un BIBD y verificar que una configuración dada satisface sus parámetros [Familiarizarse]
  2. Construir un diseño balanceado o cuadrados latinos ortogonales para un conjunto de parámetros dado [Usar]
  3. 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:

  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]

¿Encontraste una errata, un curso desactualizado, un enlace roto, o tienes una sugerencia? Cuéntanos.

Escanea para abrir en tu teléfono