Matemáticas Discretas

📚 Resumen del Contenido

Un curso introductorio de matemáticas discretas para estudiantes de matemáticas e informática. Cubre temas fundamentales como lógica, conjuntos, técnicas de demostración, algoritmos, teoría de números, combinatoria, teoría de grafos y autómatas. El curso enfatiza el razonamiento matemático y las habilidades de resolución de problemas necesarias para estudios avanzados en informática.

Domina la lógica y las estructuras que forman la base de la informática.

Autor: Richard Johnsonbaugh

Agradecimientos: Revisores incluyendo Venkata Dinavahi, Matthew Elsey, Christophe Giraud-Carrier, Yevgeniy Kovchegov, Filix Maisch, Tyler McMillen, Christopher Storm, Donald Vestal y Guanghua Zhao. Apoyo del personal de Pearson: Deirdre Lynch, Jeff Weidenaar, Lauren Morse y otros.

🎯 Objetivos de Aprendizaje

1. Realizar operaciones sobre conjuntos, incluyendo diferencias y complementos, y verificar identidades de conjuntos usando diagramas de Venn y el Teorema 1.1.22.
2. Construir y evaluar tablas de verdad para proposiciones que involucran negación, disyunción y enunciados condicionales.
3. Aplicar reglas de inferencia y razonamiento deductivo para determinar la validez de argumentos lógicos.
4. Definir y aplicar componentes de un sistema matemático, incluyendo axiomas, definiciones y teoremas.
5. Construir pruebas directas, pruebas por contradicción y pruebas por casos para proposiciones algebraicas y teóricas de conjuntos.
6. Utilizar el Principio de Inducción Matemática e Inducción Fuerte para probar identidades, propiedades de divisibilidad y corrección algorítmica.
7. Definir y clasificar funciones (inyectivas, sobreyectivas, biyectivas) y realizar operaciones como composición e inversión.
8. Aplicar notación de sucesiones, concatenación de cadenas y reglas recursivas para modelar conjuntos de datos discretos.
9. Analizar relaciones binarias respecto a propiedades como reflexividad, simetría y transitividad utilizando tanto diagramas dirigidos como representaciones matriciales.
10. Definir un algoritmo y verificar sus siete propiedades esenciales (Entrada, Salida, Precisión, Determinismo, Finitud, Correctitud y Generalidad).

🔹 Lección 1: Fundamentos de la Lógica y la Teoría de Conjuntos

Descripción general: Esta lección establece los bloques fundamentales de las matemáticas discretas, centrándose en la manipulación rigurosa de conjuntos y las estructuras formales de la lógica. Los estudiantes avanzarán desde operaciones y identidades de conjuntos hasta la construcción de argumentos lógicos, la evaluación de proposiciones condicionales y el análisis de cuantificadores anidados. Estos conceptos proporcionan el marco esencial para el diseño de algoritmos, la teoría de bases de datos y la verificación formal en informática e ingeniería.

Resultados de Aprendizaje:

• Realizar operaciones sobre conjuntos, incluyendo diferencias y complementos, y verificar identidades de conjuntos usando diagramas de Venn y el Teorema 1.1.22.
• Construir y evaluar tablas de verdad para proposiciones que involucran negación, disyunción y enunciados condicionales.
• Aplicar reglas de inferencia y razonamiento deductivo para determinar la validez de argumentos lógicos.

🔹 Lección 2: Técnicas de Demostración Matemáticas

Descripción general: Esta lección abarca los métodos formales utilizados para establecer la validez de enunciados matemáticos y el rigor lógico requerido en informática y matemáticas. Los estudiantes pasarán desde sistemas matemáticos fundamentales y pruebas directas hasta técnicas sofisticadas como pruebas por resolución, inducción matemática (incluyendo inducción fuerte) y la aplicación de invariantes de bucle en la verificación algorítmica.

Resultados de Aprendizaje:

• Definir y aplicar componentes de un sistema matemático, incluyendo axiomas, definiciones y teoremas.
• Construir pruebas directas, pruebas por contradicción y pruebas por casos para proposiciones algebraicas y teóricas de conjuntos.
• Utilizar el Principio de Inducción Matemática e Inducción Fuerte para probar identidades, propiedades de divisibilidad y corrección algorítmica.

🔹 Lección 3: Funciones, Sucesiones y Relaciones

Descripción general: Esta lección cubre las estructuras matemáticas fundamentales utilizadas para modelar datos y procesos en informática. Avanzará desde la definición de funciones y sus diferentes tipos (inyectivas, sobreyectivas, biyectivas) hasta el estudio de sucesiones, cadenas y las propiedades formales de las relaciones binarias. Los estudiantes explorarán aplicaciones prácticas como funciones hash, dígitos de control ISBN, programación de tareas mediante órdenes parciales y la representación de relaciones mediante matrices y bases de datos.

Resultados de Aprendizaje:

• Definir y clasificar funciones (inyectivas, sobreyectivas, biyectivas) y realizar operaciones como composición e inversión.
• Aplicar notación de sucesiones, concatenación de cadenas y reglas recursivas para modelar conjuntos de datos discretos.
• Analizar relaciones binarias respecto a propiedades como reflexividad, simetría y transitividad utilizando tanto diagramas dirigidos como representaciones matriciales.

🔹 Lección 4: Análisis de Algoritmos y Complejidad

Descripción general: Esta lección abarca la definición fundamental y propiedades de los algoritmos, su implementación en búsquedas y ordenamientos (específicamente Búsqueda de Texto y Ordenamiento por Inserción), y los marcos matemáticos rigurosos utilizados para analizar su eficiencia. Los estudiantes explorarán notaciones asintóticas, tasas de crecimiento de funciones y los mecanismos de resolución recursiva de problemas, incluyendo estrategias de divide y vencerás como el embaldosado de tableros y secuencias basadas en Fibonacci.

Resultados de Aprendizaje:

• Definir un algoritmo y verificar sus siete propiedades esenciales (Entrada, Salida, Precisión, Determinismo, Finitud, Correctitud y Generalidad).
• Aplicar notaciones Big-O, Omega y Theta para expresar la complejidad temporal y espacial de los algoritmos.
• Analizar escenarios de mejor caso, peor caso y promedio usando técnicas como la división repetida y el ordenamiento polinomial.

🔹 Lección 5: Introducción a la Teoría de Números y la Criptografía

Descripción general: Esta lección explora los principios fundamentales de la teoría de números, desde las propiedades básicas de divisores y primos hasta los algoritmos complejos que sustentan las comunicaciones seguras modernas. Los estudiantes dominarán los mecanismos matemáticos del máximo común divisor (MCD), conversiones de base y exponenciación modular para comprender e implementar el sistema criptográfico RSA de clave pública.

Resultados de Aprendizaje:

• Definir y aplicar los conceptos de divisibilidad, primalidad y el Teorema Fundamental de la Aritmética.
• Realizar conversiones eficientes entre sistemas numéricos decimal, binario y hexadecimal.
• Ejecutar el Algoritmo de Euclides y su forma extendida para hallar MCDs y combinaciones lineales (sa + tb).

🔹 Lección 6: Métodos de Conteo y Probabilidad Discreta

Descripción general: Esta lección explora las técnicas fundamentales para contar estructuras finitas y la aplicación de estas técnicas a la probabilidad discreta. Los estudiantes avanzarán desde principios básicos de suma y multiplicación hasta conceptos avanzados como números de Catalan, números de Stirling y el Teorema del Binomio. La lección concluye con el Principio del Palomar y sus diversas formas, proporcionando un marco riguroso para probar la existencia de configuraciones específicas en sistemas discretos.

Resultados de Aprendizaje:

• Aplicar los Principios de Suma, Multiplicación y Exclusión-Inclusión para resolver problemas complejos de conteo.
• Diferenciar entre y calcular permutaciones y combinaciones, incluyendo casos con objetos idénticos y repeticiones.
• Utilizar algoritmos generadores de permutaciones y combinaciones en orden lexicográfico.

🔹 Lección 7: Relaciones de Recurrencia

Descripción general: Esta lección explora la teoría y aplicación de las relaciones de recurrencia en matemáticas e informática. Los estudiantes aprenderán a resolver estas relaciones mediante iteración y ecuaciones características tanto para formas homogéneas como no homogéneas. Además, la lección demuestra cómo las relaciones de recurrencia son herramientas esenciales para analizar la complejidad temporal de algoritmos recursivos como el Ordenamiento por Selección, la Búsqueda Binaria y el Ordenamiento por Mezcla.

Resultados de Aprendizaje:

• Resolver relaciones de recurrencia usando el Método de Iteración y Ecuaciones Características (para raíces distintas y iguales).
• Modelar y resolver problemas matemáticos clásicos, incluyendo la Torre de Hanoi, la Secuencia de Fibonacci (Razón Áurea) y desordenamientos.
• Analizar la complejidad temporal del peor caso de algoritmos recursivos usando relaciones de recurrencia.

🔹 Lección 8: Teoría de Grafos y Algoritmos de Camino Más Corto

Descripción general: Esta lección explora los principios fundamentales de la Teoría de Grafos, desde definiciones básicas de grafos simples y ponderados hasta soluciones algorítmicas complejas para caminos más cortos e identificación de ciclos. Los estudiantes examinarán propiedades estructurales como planaridad, conectividad e isomorfismo, aplicando estos conceptos a problemas clásicos como el problema de los puentes de Königsberg, el Problema del Vendedor Viajero (TSP) y el rompecabezas Instant Insanity.

Resultados de Aprendizaje:

• Definir y diferenciar tipos de grafos, incluyendo simples, ponderados, completos, bipartitos y n-cubos.
• Analizar la conectividad del grafo para identificar ciclos de Euler, ciclos de Hamilton y determinar caminos más cortos usando el algoritmo de Dijkstra.
• Aplicar representaciones matriciales (adyacencia e incidencia) y invariantes de grafo para verificar isomorfismos y planaridad.

🔹 Lección 9: Árboles y Algoritmos de Búsqueda

Descripción general: Esta lección cubre las propiedades fundamentales, caracterizaciones y aplicaciones de los árboles en informática y matemáticas. Los estudiantes explorarán árboles raíz y binarios, algoritmos de árboles generadores (BFS/DFS), técnicas de optimización como el algoritmo de Prim para árboles generadores mínimos, y marcos de toma de decisiones incluyendo retroceso, ordenamientos por torneo y árboles de juego con el procedimiento minimax.

Resultados de Aprendizaje:

• Definir e identificar árboles raíz, sus niveles, altura y estructuras jerárquicas en sistemas del mundo real.
• Caracterizar árboles según conectividad, aciclicidad y relaciones entre aristas y vértices.
• Implementar y trazar algoritmos para árboles generadores (BFS, DFS), árboles generadores mínimos (Prim) y construcción de árboles binarios de búsqueda.

🔹 Lección 10: Modelos de Redes y Optimización de Flujo

Descripción general: Esta lección cubre la modelización matemática de redes de transporte, centrándose en cómo los recursos (flujo) se mueven a través de un grafo dirigido desde una fuente hacia un sumidero. Detalla las reglas de conservación de flujo, los pasos algorítmicos para maximizar el rendimiento, la relación entre cortes de red y capacidad de flujo, y la aplicación de estos principios para resolver problemas de emparejamiento en grafos bipartitos.

Resultados de Aprendizaje:

• Definir y verificar las propiedades de una red de transporte y asignaciones válidas de flujo.
• Ejecutar el Algoritmo de Flujo Máximo (Algoritmo 10.2.4) para encontrar el rendimiento óptimo.
• Aplicar el Teorema de Flujo Máximo - Corte Mínimo para probar la optimalidad del flujo mediante particiones de red.

🔹 Lección 11: Álgebra Booleana y Circuitos Lógicos

Descripción general: Esta lección explora los fundamentos matemáticos de la lógica digital, centrándose en cómo el álgebra booleano proporciona un lenguaje formal para diseñar y simplificar circuitos combinatorios. Los estudiantes aprenderán a traducir entre puertas lógicas, circuitos de conmutación y expresiones booleanas, aplicando finalmente estas herramientas para sintetizar funciones complejas y construir componentes aritméticos esenciales como sumadores y lógica de complemento a dos.

Resultados de Aprendizaje:

• Diseñar y analizar circuitos combinatorios usando puertas lógicas estándar (AND, OR, NOT) y configuraciones de conmutación.
• Aplicar las leyes del álgebra booleana y el Teorema Dual para probar equivalencia de circuitos y simplificar expresiones.
• Sintetizar funciones booleanas a partir de tablas de verdad en Forma Normal Disyuntiva (DNF) y Forma Normal Conjuntiva (CNF).

🔹 Lección 12: Autómatas, Gramáticas y Lenguajes Formales

Descripción general: Esta lección explora los fundamentos matemáticos de la computación, comenzando con circuitos secuenciales y máquinas de estado finito que modelan memoria interna mediante retardos de tiempo unitario. Cubre la definición formal y clasificación de gramáticas de estructura frase (Tipos 1, 2 y 3), la aplicación de la Forma Normal de Backus (BNF) y el uso especializado de gramáticas de Lindenmayer para generar fractales. Finalmente, establece la relación crítica entre autómatas de estado finito deterministas y no deterministas y los lenguajes formales que aceptan.

Resultados de Aprendizaje:

• Analizar y diseñar máquinas de estado finito (FSM) y autómatas (FSA/NFA) usando diagramas de transición y funciones de estado.
• Clasificar gramáticas dentro de la jerarquía de Chomsky y derivar cadenas usando reglas de producción y notación BNF.
• Modelar estructuras auto-similares como la nieve de von Koch usando gramáticas de Lindenmayer y reglas de reemplazo simultáneo.