Matemática Discreta

Acerca de este curso

Matemática Discreta proporciona el lenguaje y las herramientas que sustentan la informática teórica y gran parte de la optimización moderna. Cubre lógica, conteo y combinatoria, estructuras algebraicas finitas, grafos y redes, recurrencias y funciones generadoras, autómatas y lenguajes regulares, probabilidad discreta y nociones de diseños y códigos.

Las lecciones son breves y autocontenidas, adaptadas al formato en vídeo y al estudio guiado. Cada una introduce la idea clave, muestra la técnica y la aplica a problemas tipo. El objetivo es consolidar una base sólida en matemática discreta que prepare al estudiante para asignaturas de informática, ciencia de datos y optimización.

Dominar el razonamiento lógico y los métodos de demostración más usados (inducción, contradicción).
Aplicar técnicas de conteo, combinatoria y recurrencias a problemas de enumeración y análisis de algoritmos.
Trabajar con aritmética modular y teoría elemental de números para aplicaciones criptográficas.
Modelar problemas con grafos y resolver tareas de caminos, emparejamientos y flujos.
Entender autómatas finitos y lenguajes regulares como base de procesado de cadenas y compiladores.
Usar probabilidad discreta, invariantes y técnicas estructurales en la resolución de problemas no rutinarios.

Contenido del curso

Módulo 1: Fundamentos, técnicas de demostración y conteo básico
Puesta a punto del lenguaje matemático discreto y métodos de prueba más usados en informática.

Lección 1.1: Lógica proposicional: conectivas, tablas de verdad, equivalencias
Lección 1.2: Reglas de inferencia y pruebas: directa, contrarrecíproca y contradicción
Lección 1.3: Inducción matemática y variantes (fuerte, estructural)
Lección 1.4: Principios de conteo: suma, producto y principio del complemento

Módulo 2: Conjuntos, funciones y relaciones
La “gramática” del discreto: estructuras básicas para modelar datos, restricciones y estados.

Módulo 3: Álgebra booleana y lógica de predicados
De proposiciones a predicados; álgebra de Boole para diseño lógico.

Módulo 4: Combinatoria elemental
Herramientas de recuento que alimentan probabilidad, análisis de algoritmos y criptografía.

Módulo 5: Recurrencias y funciones generadoras
Modelos discretos en tiempo: cómo se resuelven y analizan.

Módulo 6: Aritmética modular y teoría elemental de números
Núcleo aritmético para hashing, firmas y protocolos.

Módulo 7: Grafos — fundamentos
El lenguaje de redes: nodos, aristas y propiedades básicas.

Módulo 8: Grafos — temas clásicos
Problemas históricos y algoritmos estructurales.

Módulo 9: Emparejamientos y flujos en redes
Modelos de asignación y transporte con grandes aplicaciones en ingeniería.

Módulo 10: Estructuras ordenadas, retículos y cerraduras
De los órdenes a los sistemas de implicaciones y dependencias.

Módulo 11: Autómatas finitos y lenguajes regulares (puente CS)
Parte habitual en discretas para Informática: modelos computacionales mínimos.

Módulo 12: Probabilidad discreta básica (conexiones combinatorias)
Probabilidad en espacios finitos apoyada en técnicas de conteo.

Módulo 13: Diseños combinatorios y códigos (intro)
Cuando el recuento se vuelve estructura: bloques, equilibrios y distancia.

Módulo 14: Técnicas de invariantes y métodos potenciales
Estrategias transversales para problemas no rutinarios.

Módulo 15: Introducción a la complejidad combinatoria
Crecimiento de funciones y costes “discretos” a nivel conceptual.

Acerca de este curso

¿Qué aprenderás?

Contenido del curso

Módulo 1: Fundamentos, técnicas de demostración y conteo básico Puesta a punto del lenguaje matemático discreto y métodos de prueba más usados en informática.

Lección 1.1: Lógica proposicional: conectivas, tablas de verdad, equivalencias

Lección 1.2: Reglas de inferencia y pruebas: directa, contrarrecíproca y contradicción

Lección 1.3: Inducción matemática y variantes (fuerte, estructural)

Lección 1.4: Principios de conteo: suma, producto y principio del complemento

Módulo 2: Conjuntos, funciones y relaciones La “gramática” del discreto: estructuras básicas para modelar datos, restricciones y estados.

Lección 2.1: Conjuntos y operaciones; particiones

Lección 2.2: Funciones: inyectivas, sobreyectivas, biyectivas; aplicaciones a conteo

Lección 2.3: Relaciones binarias: propiedades, matrices y grafos de relaciones

Lección 2.4: Relaciones de equivalencia y órdenes parciales; diagramas de Hasse

Módulo 3: Álgebra booleana y lógica de predicados De proposiciones a predicados; álgebra de Boole para diseño lógico.

Lección 3.1: Cuantificadores y equivalencias lógicas de primer orden

Lección 3.2: Normalización (CNF/DNF) y satisfacibilidad (visión básica)

Lección 3.3: Álgebra de Boole: axiomas, dualidad, simplificación

Lección 3.4: Funciones booleanas y mapas de Karnaugh (nociones)

Módulo 4: Combinatoria elemental Herramientas de recuento que alimentan probabilidad, análisis de algoritmos y criptografía.

Lección 4.1: Permutaciones y combinaciones; variaciones con/sin repetición

Lección 4.2: Binomio de Newton e identidades combinatorias básicas

Lección 4.3: Principio del palomar (Dirichlet) y aplicaciones

Lección 4.4: Inclusión–exclusión y problemas típicos

Módulo 5: Recurrencias y funciones generadoras Modelos discretos en tiempo: cómo se resuelven y analizan.

Lección 5.1: Recurrencias lineales con coeficientes constantes

Lección 5.2: Método de coeficientes indeterminados (casos típicos)

Lección 5.3: Recurrencias no homogéneas; cambios de variable

Lección 5.4: Funciones generadoras ordinarias: idea y ejemplos clásicos

Módulo 6: Aritmética modular y teoría elemental de números Núcleo aritmético para hashing, firmas y protocolos.

Lección 6.1: Divisibilidad, algoritmo de Euclides y Bézout

Lección 6.2: Congruencias, clases mod n, inversos y teoremas chinos

Lección 6.3: Potenciación rápida; pequeño teorema de Fermat y Euler-Fermat

Lección 6.4: Aplicaciones: pseudoprimalidad y criptografía (visión introductoria)

Módulo 7: Grafos — fundamentos El lenguaje de redes: nodos, aristas y propiedades básicas.

Lección 7.1: Definiciones: grado, subgrafos, isomorfismo; grafos especiales

Lección 7.2: Caminos, ciclos, conectividad y componentes

Lección 7.3: Árboles: propiedades, recorridos (BFS/DFS) y codificación de Prüfer

Lección 7.4: Árboles generadores mínimos (Kruskal/Prim) y aplicaciones

Módulo 8: Grafos — temas clásicos Problemas históricos y algoritmos estructurales.

Lección 8.1: Euler vs. Hamilton: caracterizaciones y heurísticas

Lección 8.2: Planaridad: teoremas de Kuratowski y de Euler (ideas)

Lección 8.3: Coloreado de grafos y número cromático; aplicaciones

Lección 8.4: Caminos mínimos (Dijkstra, Bellman-Ford) y cierre transitivo

Módulo 9: Emparejamientos y flujos en redes Modelos de asignación y transporte con grandes aplicaciones en ingeniería.

Lección 9.1: Emparejamientos: bipartitos, algoritmo de Kuhn (visión operativa)

Lección 9.2: Cubrimientos y dualidades básicas

Lección 9.3: Flujos máximos y cortes mínimos (Ford–Fulkerson/Edmonds–Karp)

Lección 9.4: Aplicaciones: asignación, rutas, scheduling simple

Módulo 10: Estructuras ordenadas, retículos y cerraduras De los órdenes a los sistemas de implicaciones y dependencias.

Lección 10.1: Posets: cadenas, antichains, elementos extremos

Lección 10.2: Retículos y operaciones ∧/∨; ejemplos (subconjuntos, divisores)

Lección 10.3: Sistemas de cerradura y operadores de cierre

Lección 10.4: Aplicaciones a bases de datos y dependencias (visión conceptual)

Módulo 11: Autómatas finitos y lenguajes regulares (puente CS) Parte habitual en discretas para Informática: modelos computacionales mínimos.

Lección 11.1: Autómatas finitos deterministas y no deterministas; equivalencia

Lección 11.2: Expresiones regulares y lema de bombeo (idea)

Lección 11.3: Minimización de DFA; particiones y cambios de base de estados

Lección 11.4: Aplicaciones: validación de patrones y lexical analysis

Módulo 12: Probabilidad discreta básica (conexiones combinatorias) Probabilidad en espacios finitos apoyada en técnicas de conteo.

Lección 12.1: Experimentos discretos, sucesos y probabilidad de Laplace

Lección 12.2: Variables aleatorias discretas y esperanza

Lección 12.3: Distribuciones clásicas (Bernoulli, Binomial, Geométrica, Poisson)

Lección 12.4: Desigualdades sencillas y líneas maestras de concentración

Módulo 13: Diseños combinatorios y códigos (intro) Cuando el recuento se vuelve estructura: bloques, equilibrios y distancia.

Lección 13.1: Diseños de bloques balanceados (idea)

Lección 13.2: Códigos lineales: distancia de Hamming y capacidad de corrección

Lección 13.3: Matrices generadoras y de control; síndrome

Lección 13.4: Ejemplos: Hamming y Reed–Solomon (nivel introductorio)

Módulo 14: Técnicas de invariantes y métodos potenciales Estrategias transversales para problemas no rutinarios.

Lección 14.1: Paridad, invariantes y monovariantes

Lección 14.2: Estrategias de acotación y extremalidad

Lección 14.3: Construcciones inductivas y recursivas

Lección 14.4: Taller de resolución de problemas combinatorios

Módulo 15: Introducción a la complejidad combinatoria Crecimiento de funciones y costes “discretos” a nivel conceptual.

Lección 15.1: Notación O, Ω, Θ y comparaciones asintóticas elementales

Lección 15.2: Contajes explosivos: factoriales, exponenciales y particiones

Lección 15.3: Reducciones muy básicas vía conteo

Lección 15.4: Discusión: límites de lo algorítmico en problemas discretos

Resources